Empaquetado de contenedores con ajuste inicial decreciente

El algoritmo de ajuste decreciente (FFD) es un algoritmo para el empaquetamiento de contenedores . Su entrada es una lista de elementos de diferentes tamaños. Su salida es un empaquetamiento : una partición de los elementos en contenedores de capacidad fija, de manera que la suma de los tamaños de los elementos en cada contenedor sea como máximo igual a la capacidad. Idealmente, nos gustaría usar la menor cantidad de contenedores posible, pero minimizar el número de contenedores es un problema NP-difícil, por lo que utilizamos una heurística aproximadamente óptima .

Descripción

El algoritmo FFD funciona de la siguiente manera.

Ordena los artículos del más grande al más pequeño.
Abra un nuevo contenedor vacío, el contenedor n.° 1.
Para cada artículo, desde el más grande hasta el más pequeño, encuentre el primer contenedor en el que quepa el artículo, si es que existe alguno.
- Si encuentra un contenedor de este tipo, coloque el nuevo artículo en él.
- De lo contrario, abre un contenedor vacío y coloca el nuevo artículo dentro.

En resumen: FFD ordena los artículos por tamaño descendente y luego llama al empaquetamiento de contenedores de primer ajuste .

Una descripción equivalente del algoritmo FFD es la siguiente.

Ordena los artículos del más grande al más pequeño.
Mientras queden artículos:
- Abre un nuevo contenedor vacío.
- Para cada artículo, del más grande al más pequeño:
  - Si cabe en el contenedor actual, insértelo.

En la descripción estándar, recorremos los elementos una sola vez, pero mantenemos muchos contenedores abiertos. En la descripción equivalente, recorremos los elementos varias veces, pero mantenemos solo un contenedor abierto en cada iteración.

Análisis de rendimiento

El rendimiento de FFD se analizó en varias etapas. A continuación, $FFD(S,C)$ denota el número de contenedores utilizados por FFD para el conjunto de entrada S y la capacidad del contenedor C.

En 1973, DS Johnson demostró en su tesis doctoral ^{[ 1 ]} que $FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+4$ para cualquier instancia S y capacidad C.
En 1985, BS Backer ^{[ 2 ]} dio una demostración ligeramente más simple y mostró que la constante aditiva no es mayor que 3.
Yue Minyi ^{[ 3 ]} demostró que $FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+1$ en 1991 y, en 1997, mejoró este análisis para $FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+7/9$ junto con Li Rongheng. ^{[ 4 ]}
En 2007, György Dósa ^{[ 5 ]} demostró ser el líder $FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+6/9$ y presentó un ejemplo para el cual $FFD(S,C)=11/9\mathrm {OPT} (S,C)+6/9$ .

Ejemplo del peor de los casos

El ejemplo de límite inferior proporcionado por Dósa es el siguiente: Consideremos las dos configuraciones de contenedores:

$B_{1}:=\{1/2+\varepsilon ,1/4+\varepsilon ,1/4-2\varepsilon \}$ ;
$B_{2}:=\{1/4+2\varepsilon ,1/4+2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}$ .

Si hay 4 copias de $B_{1}$ y 2 copias de $B_{2}$ En la solución óptima, FFD calculará los siguientes intervalos:

4 contenedores con configuración $\{1/2+\varepsilon ,1/4+2\varepsilon \}$ ,
1 contenedor con configuración $\{1/4+\varepsilon ,1/4+\varepsilon ,1/4+\varepsilon \}$ ,
1 contenedor con configuración $\{1/4+\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}$ ,
1 contenedor con configuración $\{1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}$ ,
1 un contenedor final con configuración $\{1/4-2\varepsilon \}$ ,

Es decir, 8 contenedores en total, mientras que el óptimo tiene solo 6 contenedores. Por lo tanto, el límite superior es ajustado, porque $11/9\cdot 6+6/9=72/9=8$ .

Este ejemplo se puede extender a todos los tamaños de ${\text{OPT}}(S,C)$ : ^{[ 5 ]} en la configuración óptima hay 9 k +6 contenedores: 6 k +4 de tipo B ₁ y 3 k +2 de tipo B ₂ . Pero FFD necesita al menos 11 k +8 contenedores, que es ${\frac {11}{9}}(6k+4+3k+2)+{\frac {6}{9}}$ .

Rendimiento con tamaños de artículos divisibles

Un caso especial importante del empaquetamiento de contenedores es aquel en el que los tamaños de los elementos forman una secuencia divisible (también llamada factorizada ). Un caso especial de tamaños de elementos divisibles se da en la asignación de memoria en sistemas informáticos, donde los tamaños de los elementos son todos potencias de 2. En este caso, FFD siempre encuentra el empaquetamiento óptimo. ^{[ 6 ]}^{: Teorema 2}

Propiedades de monotonicidad

Contrariamente a la intuición, $FFD(S,C)$ no es una función monótona de C. ^{[ 7 ]}^{: Fig.4} De manera similar, $FFD(S,C)$ no es una función monótona de los tamaños de los elementos en S : es posible que un elemento se reduzca de tamaño, pero el número de contenedores aumente.

Sin embargo, el algoritmo FFD tiene una propiedad de "monotonicidad asintótica", definida de la siguiente manera. ^{[ 7 ]}^{: Lem.2.1}

Para cada instancia S y entero m , sea MinCap( S,m ) la capacidad más pequeña C tal que $OPT(S,C)\leq m$
Para cada entero m , sea MinRatio( m ) el ínfimo de los números r ≥ 1 tal que, para todos los conjuntos de entrada S , $FFD(S,r\cdot {\text{MinCap}}(S,m))\leq m$ . Esta es la cantidad en la que necesitamos "inflar" los contenedores para que FFD alcance el número óptimo de contenedores.
Entonces, para cada entrada S y para cada r ≥ MinRatio( m ), $FFD(S,r\cdot {\text{MinCap}}(S,m))\leq m$ Esto demuestra, en particular, que el ínfimo en la definición anterior puede ser reemplazado por mínimo.

Ejemplos

Por ejemplo, supongamos que la entrada es:

44, 24, 24, 22, 21, 17, 8, 8, 6, 6.

Con capacidad para 60 personas, FFD incluye 3 contenedores:

44, 8, 8;
24, 24, 6, 6;
22, 21, 17.

Pero con una capacidad de 61, FFD incluye 4 contenedores:

44, 17;
24, 24, 8;
22, 21, 8, 6;
6.

Esto se debe a que, con una capacidad de 61, el 17 cabe en el primer contenedor y, por lo tanto, bloquea el paso a los siguientes 8, 8.

Como otro ejemplo, ^{[ 8 ]}^{: Ex.5.1} supongamos que las entradas son: 51, 28, 28, 28, 27, 25, 12, 12, 10, 10, 10, 10, 10, 10, 10, 10. Con una capacidad de 75, FFD empaca 4 contenedores:

51, 12, 12
28, 28, 10
28, 27, 10, 10
25, 10, 10, 10, 10, 10

Pero con una capacidad de 76, necesita 5 contenedores:

51, 25
28, 28, 12
28, 27, 12
10, 10, 10, 10, 10, 10, 10
10

Consideremos el ejemplo anterior con una capacidad de 60. Si el 17 se convierte en 16, entonces el empaque resultante es:

44, 16;
24, 24, 8;
22, 21, 8, 6;
6.

Primer ajuste decreciente modificado

El método de ajuste decreciente modificado (MFFD) ^{[ 9 ]} mejora el método FFD para elementos de más de la mitad de un contenedor, clasificando los elementos por tamaño en cuatro clases: grande, mediano, pequeño y diminuto, que corresponden a elementos con un tamaño > 1/2 contenedor, > 1/3 contenedor, > 1/6 contenedor y elementos más pequeños, respectivamente. Luego, procede a través de cinco fases:

Asigne un contenedor para cada artículo grande, ordenados del más grande al más pequeño.
Avanza por los contenedores. En cada uno: si el artículo mediano más pequeño que queda no cabe, salta este contenedor. De lo contrario, coloca el artículo mediano más grande que quepa.
Retroceda por los contenedores que no contengan un artículo mediano. En cada uno: si los dos artículos pequeños restantes más pequeños no caben, omita este contenedor. De lo contrario, coloque el artículo pequeño restante más pequeño y el artículo pequeño restante más grande que sí quepan.
Continúa avanzando por todos los contenedores. Si el artículo más pequeño que queda de cualquier tamaño no cabe, salta este contenedor. De lo contrario, coloca el artículo más grande que quepa y quédate en este contenedor.
Utilice FFD para empaquetar los artículos restantes en nuevos contenedores.

Este algoritmo fue estudiado por primera vez por Johnson y Garey ^{[ 9 ]} en 1985, donde demostraron que $MFFD(S,C)\leq (71/60)\mathrm {OPT} (S,C)+(31/6)$ . Esta cota fue mejorada en el año 1995 por Yue y Zhang ^{[ 10 ]} quienes demostraron que $MFFD(S,C)\leq (71/60)\mathrm {OPT} (S,C)+1$ .

Otras variantes

El algoritmo de ajuste óptimo decreciente (BFD) es muy similar al algoritmo de ajuste óptimo (FFD), con la diferencia de que, una vez ordenada la lista, se procesa mediante el método de empaquetamiento de contenedores de ajuste óptimo . Su razón de aproximación asintótica es la misma que la del FFD: 11/9.

Implementaciones

Python: El paquete prtpy contiene una implementación de first-fit decreciente .

Véase también

Algoritmo Multifit : un algoritmo para la planificación de máquinas idénticas que utiliza FFD como subrutina.

Referencias

↑ Johnson, David S (1973). "Algoritmos de empaquetamiento de contenedores casi óptimos" (PDF) . Instituto Tecnológico de Massachusetts .
↑ Baker, Brenda S. (1985). "Una nueva prueba para el algoritmo de empaquetamiento de contenedores decreciente de primer ajuste". J. Algorithms . 6 (1): 49– 70. doi : 10.1016/0196-6774(85)90018-5 .
^ Yue, Minyi (octubre de 1991). "Una prueba simple de la desigualdad FFD (L) ≤ 11/9 OPT (L) + 1, ∀L para el algoritmo de empaquetado en contenedores FFD". Acta Mathematicae Applicatae Sínica . 7 (4): 321– 331. doi : 10.1007/BF02009683 . S2CID 189915733 .
↑ Li, Rongheng; Yue, Minyi (agosto de 1997). "La prueba de FFD(L) < -OPT(L) + 7/9". Chinese Science Bulletin . 42 (15): 1262– 1265. Bibcode : 1997ChSBu..42.1262L . doi : 10.1007/BF02882754 . S2CID 93280100 .
1 2 Dósa, György (2007). "El límite ajustado del algoritmo de empaquetamiento de contenedores decreciente de primer ajuste es FFD(I) ≤ 11/9OPT(I) + 6/9". En Chen Bo; Mike Paterson; Zhang Guochuan (eds.). Combinatoria, algoritmos, metodologías probabilísticas y experimentales . Primer Simposio Internacional, ESCAPE 2007, Hangzhou, China, 7-9 de abril de 2007. Lecture Notes in Computer Science. Vol. 4614. pp. 1-11 . doi : 10.1007/978-3-540-74450-4_1 . ISBN 978-3-540-74449-8.
↑ Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Empaquetado de contenedores con tamaños de artículos divisibles" . Journal of Complexity . 3 (4): 406– 428. doi : 10.1016/0885-064X(87)90009-4 . ISSN 0885-064X .
1 2 Coffman, EG Jr.; Garey, MR; Johnson, DS (1978-02-01). "Una aplicación del empaquetamiento de contenedores a la planificación de multiprocesadores" . SIAM Journal on Computing . 7 (1): 1– 17. doi : 10.1137/0207001 . ISSN 0097-5397 .
↑ Huang, Xin; Lu, Pinyan (18 de julio de 2021). «Un marco algorítmico para aproximar la asignación de tareas domésticas mediante la distribución maximin» . Actas de la 22.ª Conferencia ACM sobre Economía y Computación . EC '21. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 630–631 . arXiv : 1907.04505 . doi : 10.1145/3465456.3467555 . ISBN 978-1-4503-8554-1. S2CID 195874333 .
1 2 Johnson, David S; Garey, Michael R (octubre de 1985). "Un teorema 7160 para el empaquetamiento de contenedores" . Journal of Complexity . 1 (1): 65– 106. doi : 10.1016/0885-064X(85)90022-6 .
↑ Yue, Minyi; Zhang, Lei (julio de 1995). "Una demostración simple de la desigualdad MFFD(L) ≤ 71/60 OPT(L) + 1,L para el algoritmo de empaquetamiento de contenedores MFFD". Acta Mathematicae Applicatae Sinica . 11 (3): 318– 330. doi : 10.1007/BF02011198 . S2CID 118263129 .

[johnson73-1] Johnson, David S (1973). "Algoritmos de empaquetamiento de contenedores casi óptimos" (PDF) . Instituto Tecnológico de Massachusetts .

[Backer85-2] Baker, Brenda S. (1985). "Una nueva prueba para el algoritmo de empaquetamiento de contenedores decreciente de primer ajuste". J. Algorithms . 6 (1): 49– 70. doi : 10.1016/0196-6774(85)90018-5 .

[3] Yue, Minyi (octubre de 1991). "Una prueba simple de la desigualdad FFD (L) ≤ 11/9 OPT (L) + 1, ∀L para el algoritmo de empaquetado en contenedores FFD". Acta Mathematicae Applicatae Sínica . 7 (4): 321– 331. doi : 10.1007/BF02009683 . S2CID 189915733 .

[4] Li, Rongheng; Yue, Minyi (agosto de 1997). "La prueba de FFD(L) < -OPT(L) + 7/9". Chinese Science Bulletin . 42 (15): 1262– 1265. Bibcode : 1997ChSBu..42.1262L . doi : 10.1007/BF02882754 . S2CID 93280100 .

[Dosa07-5] 1 2 Dósa, György (2007). "El límite ajustado del algoritmo de empaquetamiento de contenedores decreciente de primer ajuste es FFD(I) ≤ 11/9OPT(I) + 6/9". En Chen Bo; Mike Paterson; Zhang Guochuan (eds.). Combinatoria, algoritmos, metodologías probabilísticas y experimentales . Primer Simposio Internacional, ESCAPE 2007, Hangzhou, China, 7-9 de abril de 2007. Lecture Notes in Computer Science. Vol. 4614. pp. 1-11 . doi : 10.1007/978-3-540-74450-4_1 . ISBN 978-3-540-74449-8.

[6] Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Empaquetado de contenedores con tamaños de artículos divisibles" . Journal of Complexity . 3 (4): 406– 428. doi : 10.1016/0885-064X(87)90009-4 . ISSN 0885-064X .

[:0-7] 1 2 Coffman, EG Jr.; Garey, MR; Johnson, DS (1978-02-01). "Una aplicación del empaquetamiento de contenedores a la planificación de multiprocesadores" . SIAM Journal on Computing . 7 (1): 1– 17. doi : 10.1137/0207001 . ISSN 0097-5397 .

[:3-8] Huang, Xin; Lu, Pinyan (18 de julio de 2021). «Un marco algorítmico para aproximar la asignación de tareas domésticas mediante la distribución maximin» . Actas de la 22.ª Conferencia ACM sobre Economía y Computación . EC '21. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 630–631 . arXiv : 1907.04505 . doi : 10.1145/3465456.3467555 . ISBN 978-1-4503-8554-1. S2CID 195874333 .

[JohnsonGarey19852-9] 1 2 Johnson, David S; Garey, Michael R (octubre de 1985). "Un teorema 7160 para el empaquetamiento de contenedores" . Journal of Complexity . 1 (1): 65– 106. doi : 10.1016/0885-064X(85)90022-6 .

[YueZhang19952-10] Yue, Minyi; Zhang, Lei (julio de 1995). "Una demostración simple de la desigualdad MFFD(L) ≤ 71/60 OPT(L) + 1,L para el algoritmo de empaquetamiento de contenedores MFFD". Acta Mathematicae Applicatae Sinica . 11 (3): 318– 330. doi : 10.1007/BF02011198 . S2CID 118263129 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 9 ]

[ 10 ]