Embalaje de contenedores de primera calidad

First-fit (FF) es un algoritmo en línea 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 modo que la suma de los tamaños de los elementos en cada contenedor sea como máximo la capacidad. Idealmente, nos gustaría utilizar la menor cantidad de contenedores posible, pero minimizar la cantidad de contenedores es un problema NP-hard. El algoritmo First-fit utiliza la siguiente heurística :

• Mantiene una lista de contenedores abiertos, que inicialmente está vacía.
• Cuando llegue un artículo, busque el primer contenedor en el que pueda caber el artículo, si hay alguno.
  • Si se encuentra dicho contenedor, el nuevo artículo se coloca dentro del mismo.
  • De lo contrario, se abre un nuevo contenedor y se coloca dentro el artículo que falta.

Relación de aproximación

Denotemos por FF(L) el número de bins utilizados por First-Fit, y por OPT(L) el número óptimo de bins posibles para la lista L. El análisis de FF(L) se realizó en varios pasos.

• El primer límite superior de FF fue demostrado por Ullman ^[1] en 1971. ${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +3}$
• En 1972, este límite superior fue mejorado por Garey, Graham y Ullman, ^[2] Johnson y Demers. ^[3] ${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +2}$
• En 1976, fue mejorado por Garey, Graham, Johnson, Yao y Chi-Chih ^[4] a , que es equivalente a debido a la integralidad de y . ${\displaystyle FF(L)\leq \lceil 1.7\mathrm {OPT} \rceil }$ ${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +0.9}$ ${\displaystyle FF(L)}$ ${\displaystyle \mathrm {OPT} }$
• La siguiente mejora, realizada por Xia y Tan ^[5] en 2010, redujo el límite a . ${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +0.7}$
• Finalmente, en 2013, Dósa y Sgall mejoraron este límite . ^[6] También presentan una lista de entrada de ejemplo , para la cual coincide con este límite. ${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$ ${\displaystyle L}$ ${\displaystyle FF(L)}$

A continuación explicamos la idea de la prueba.

Razón asintótica como máximo 2

Aquí hay una prueba de que la razón asintótica es como máximo 2. Si hay un contenedor FF con suma menor que 1/2, entonces el tamaño de todos los elementos restantes es mayor que 1/2, por lo que la suma de todos los contenedores siguientes es mayor que 1/2. Por lo tanto, todos los contenedores FF excepto como máximo uno tienen suma de al menos 1/2. Todos los contenedores óptimos tienen suma como máximo 1, por lo que la suma de todos los tamaños es como máximo OPT. Por lo tanto, el número de contenedores FF es como máximo 1+OPT/(1/2) = 2*OPT+1

Razón asintótica como máximo 1,75

Consideremos primero un caso especial en el que todos los tamaños de los elementos son como máximo 1/2. Si hay un contenedor FF con suma menor que 2/3, entonces el tamaño de todos los elementos restantes es mayor que 1/3. Dado que los tamaños son como máximo 1/2, todos los contenedores siguientes (excepto quizás el último) tienen al menos dos elementos y una suma mayor que 2/3. Por lo tanto, todos los contenedores FF excepto como máximo uno tienen una suma de al menos 2/3, y el número de contenedores FF es como máximo 2+OPT/(2/3) = 3/2*OPT+1.

Los elementos "problemáticos" son aquellos con un tamaño mayor a 1/2. Por lo tanto, para mejorar el análisis, vamos a otorgar a cada elemento mayor a 1/2 una bonificación de R. Definamos el peso de un elemento como su tamaño más su bonificación. Definamos el peso de un conjunto de elementos como la suma de los pesos de sus contenidos.

Ahora bien, el peso de cada contenedor FF con un elemento (excepto uno como máximo) es al menos 1/2+R, y el peso de cada contenedor FF con dos o más elementos (excepto uno como máximo) es 2/3. Si tomamos R=1/6, obtenemos que el peso de todos los contenedores FF es al menos 2/3.

Por otra parte, el peso de cada contenedor en el empaquetamiento óptimo es como máximo 1+R = 7/6, ya que cada uno de esos contenedores tiene como máximo un elemento mayor que 1/2. Por lo tanto, el peso total de todos los elementos es como máximo 7/6*OPT, y el número de contenedores FF es como máximo 2+(7/6*OPT/(2/3)) = 7/4*OPT+2.

Razón asintótica como máximo 1,7

La siguiente prueba está adaptada de ^{[6] : sec.1.2} Defina el peso de un elemento de entrada como el tamaño del elemento x alguna bonificación calculada de la siguiente manera:

${\displaystyle bonus(x):={\begin{cases}0&x\leq 1/6\\x/2-1/12&1/6<x<1/3\\1/12&1/3\leq x\leq 1/2\\1/3&1/2<x\end{cases}}}$

${\displaystyle weight(x):=x+bonus(x)}$.

La relación de aproximación asintótica se desprende de dos afirmaciones:

1. En el embalaje óptimo el peso de cada contenedor es como máximo 17/12;
2. En el embalaje First-Fit, el peso promedio de cada contenedor es al menos 5/6 = 10/12.

Por lo tanto, asintóticamente, el número de contenedores en el empaque FF debe ser como máximo 17/10 * OPT.

Para la reivindicación 1 , es suficiente probar que, para cualquier conjunto B con suma máxima de 1, bonus( B ) es máximo 5/12. En efecto:

• Si B no tiene ningún elemento mayor que 1/2, entonces tiene como máximo cinco elementos mayores que 1/6, y la bonificación de cada uno de ellos es como máximo 1/12;
• Si B tiene un elemento mayor que 1/2 pero ningún elemento en [1/3,1/2], entonces tiene lugar como máximo para dos elementos en (1/6,1/3), y la suma de sus bonificaciones es como máximo (1/2 / 2 - 1/6) = 1/12, por lo que la bonificación total es 4/12+1/12=5/12.
• Si B tiene un elemento mayor a 1/2 y un elemento en [1/3,1/2], entonces no tiene más espacio para elementos de tamaño mayor a 1/6, por lo que la bonificación total es nuevamente 4/12+1/12 = 5/12.

Por lo tanto, el peso de B es como máximo 1+5/12 = 17/12.

Para la reivindicación 2 , considere primero un contenedor FF B con un solo artículo.

• Si suma( B )<1/2, entonces - por la forma en que funciona FF - todos los elementos procesados ​​después de B deben ser mayores que 1/2 (de lo contrario, se habrían insertado en B ). Por lo tanto, hay como máximo un contenedor FF con suma<1/2.
• Consideremos ahora todos los demás contenedores B con un solo elemento con suma ( B ) > 1/2. Para todos estos contenedores, peso ( B ) > 1/2 + 1/3 = 5/6.

Consideremos ahora los contenedores FF B con dos o más artículos.

• Si suma( B )<2/3, entonces - por la forma en que funciona FF - todos los elementos procesados ​​después de B deben ser mayores que 1/3 (de lo contrario se habrían insertado en B ). Por lo tanto, todos los contenedores siguientes con dos o más elementos son mayores que 2/3. Por lo tanto, hay como máximo un contenedor FF con dos o más elementos y suma<2/3.
• Consideremos ahora todos los demás contenedores con dos o más elementos y suma > 2/3. Denotemos estos como B[1],B[2],...B[k], por el orden en que se abren. Para cada i en 1,..., k , demostramos que la suma de B[i] más el bonus de B[i+1] es al menos 5/6: suma(B[i])+bonus(B[i+1]) ≥ 5/6. De hecho, si suma(B[i]) ≥ 5/6 entonces la desigualdad es trivial. De lo contrario, sea suma(B[i]) := 1 - x . Nótese que x está entre 1/6 y 2/6, ya que suma(B[i]) está entre 2/3 y 5/6. Como B[i+1] se abre después de B[i], B[i+1] contiene al menos dos elementos, digamos c 1 y c 2, que no caben en B[i], es decir: c1,c2 > 1-suma(B[i]) = x > 1/6. Entonces, la bonificación de cada uno de c1 y c2 es al menos x/2 - 1/12. Por lo tanto, la bonificación de B[i+1] es al menos x-1/6, por lo que suma(B[i]) + bonificación(B[i+1]) ≥ (1-x)+(x-1/6) = 5/6.
• Podemos aplicar la desigualdad anterior a pares sucesivos y obtener: suma(B[1]) + bono(B[2]) + suma(B[2]) + bono(B[3]) + ... + suma(B[k-1]) + bono(B[k]) ≥ 5/6*(k-1).

Por lo tanto, el peso total de todos los contenedores FF es al menos 5/6*(FF - 3) (donde restamos 3 para el contenedor de un solo elemento con suma < 1/2, el contenedor de dos elementos con suma < 2/3 y el k-1 de los contenedores de dos elementos con suma ≥ 2/3).

En total, obtenemos que 17/12*OPT ≥ 5/6*(FF-3), por lo que FF ≤ 17/10*OPT+3.

Dósa y Sgall ^[6] presentan un análisis más estricto que elimina el 3 y obtienen que FF ≤ 17/10*OPT.

Límite inferior

Existen casos en los que el límite de rendimiento de 1.7OPT es ajustado. El siguiente ejemplo se basa en ^{[7] [8]} La capacidad del contenedor es 101 y:

• La secuencia es: 6 (x7), 10 (x7), 16 (x3), 34 (x10), 51 (x10).
• El empaquetamiento óptimo contiene 10 contenedores: [51+34+16] (x3), [51+34+10+6] (x7). La suma de todos los contenedores es 101.
• El paquete First Fit contiene 17 contenedores: [6 (x7) + 10 (x5)], [10 (x2) + 16 (x3)], [34+34] (x5), [51] (x10).
  • Las sumas de los bins son: 92, 68, 68 (x5), 51 (x10).
  • Las recompensas (normalizadas a 101) son 0, 0, 16,8 (x5), 33,7 (x10).
  • Los pesos totales (normalizados a 101) son 92, 68, 84,8 (x5), 84,7 (x10). Se puede observar que casi todos los pesos están cerca de 101*5/6=84,1.

Rendimiento con tamaños de elementos divisibles

Un caso especial importante de empaquetamiento de bins 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 produce en la asignación de memoria en sistemas informáticos, donde los tamaños de los elementos son todos potencias de 2. Si los tamaños de los elementos son divisibles y, además, el tamaño de elemento más grande divide el tamaño de bin, entonces FF siempre encuentra un empaquetamiento óptimo. ^{[9] : Teoría 3}

Primer ajuste refinado

Refined-First-Fit (RFF) es otro algoritmo en línea para el empaquetamiento de bins , que mejora el algoritmo FF desarrollado anteriormente. Fue presentado por Andrew Chi-Chih Yao. ^[10]

El algoritmo

Los artículos se clasifican en cuatro clases, según sus tamaños (donde la capacidad del contenedor es 1):

• ${\displaystyle A}$-pieza-tamaño en . ${\displaystyle (1/2,1]}$
• ${\displaystyle B_{1}}$-pieza-tamaño en . ${\displaystyle (2/5,1/2]}$
• ${\displaystyle B_{2}}$-pieza-tamaño en . ${\displaystyle (1/3,2/5]}$
• ${\displaystyle X}$-pieza-tamaño en . ${\displaystyle (0,1/3]}$

Del mismo modo, los contenedores se clasifican en cuatro clases: 1, 2, 3 y 4.

Sea un entero fijo. El siguiente elemento se asigna a un contenedor en - ${\displaystyle m\in \{6,7,8,9\}}$ ${\displaystyle i\in L}$

• Clase 1, si es una pieza, ${\displaystyle i}$ ${\displaystyle A}$
• Clase 2, si es una pieza, ${\displaystyle i}$ ${\displaystyle B_{1}}$
• Clase 3, si es una pieza, pero no la pieza n -ésima vista hasta ahora, para cualquier entero . ${\displaystyle i}$ ${\displaystyle B_{2}}$ ${\displaystyle (mk)}$ ${\displaystyle B_{2}}$ ${\displaystyle k\geq 1}$
• Clase 1, si es la pieza th vista hasta ahora, ${\displaystyle i}$ ${\displaystyle (mk)}$ ${\displaystyle B_{2}}$
• Clase 4, si es una pieza. ${\displaystyle i}$ ${\displaystyle X}$

Una vez seleccionada la clase del artículo, se coloca dentro de los contenedores de esa clase utilizando el método de empaquetado de contenedores de primer ajuste.

Tenga en cuenta que RFF no es un algoritmo Any-Fit, ya que puede abrir un nuevo contenedor a pesar del hecho de que el elemento actual encaja dentro de un contenedor abierto (de otra clase).

Relación de aproximación

RFF tiene una garantía de aproximación de . Existe una familia de listas con para . ^[10] ${\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}$ ${\displaystyle L_{k}}$ ${\displaystyle RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3}$ ${\displaystyle \mathrm {OPT} (L)=6k+1}$

Véase también

• First-Fit-Decreasing (FFD) es la variante offline de First-Fit: acepta todos los elementos de entrada, los ordena por tamaño descendente y llama a First-Fit. Su razón de aproximación asintótica es mucho mejor: aproximadamente 1,222 en lugar de 1,7.

Implementaciones

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

Referencias

1. Ullman, JD (1971). "El rendimiento de un algoritmo de asignación de memoria". Informe técnico 100 Princeton Univ .
2. Garey, M. R; Graham, R. L; Ullman, JD (1972). "Análisis del peor caso de algoritmos de asignación de memoria". Actas del cuarto simposio anual de la ACM sobre teoría de la computación - STOC '72 . págs. 143–150. doi :10.1145/800152.804907. S2CID  26654056.
3. David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, MR Garey, Ronald L. Graham. Límites de rendimiento en el peor de los casos para algoritmos de empaquetamiento unidimensionales simples. SICOMP, volumen 3, número 4. 1974.
4. Garey, M. R; Graham, R. L; Johnson, D. S; Yao, Andrew Chi-Chih (1976). "Programación con recursos restringidos como empaquetamiento de contenedores generalizado". Journal of Combinatorial Theory, Serie A . 21 (3): 257–298. doi : 10.1016/0097-3165(76)90001-7 . ISSN  0097-3165.
5. Xia, Binzhou; Tan, Zhiyi (agosto de 2010). "Límites más estrictos del algoritmo First Fit para el problema de empaquetamiento de bins". Matemáticas Aplicadas Discretas . 158 (15): 1668–1675. doi : 10.1016/j.dam.2010.05.026 .
6. Dósa, György; Sgall, Jiri (2013). "Embalaje en contenedores First Fit: un análisis exhaustivo". 30º Simposio Internacional sobre Aspectos Teóricos de la Informática (STACS 2013) . 20 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 538–549. doi : 10.4230/LIPIcs.STACS.2013.538 .
7. Garey, MR; Graham, RL; Ullman, JD (1972-05-01). "Análisis del peor caso de algoritmos de asignación de memoria". Actas del cuarto simposio anual de la ACM sobre teoría de la computación - STOC '72 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 143–150. doi :10.1145/800152.804907. ISBN 978-1-4503-7457-6.S2CID26654056  .​
8. Johnson, DS; Demers, A.; Ullman, JD; Garey, MR; Graham, RL (diciembre de 1974). "Límites de rendimiento en el peor de los casos para algoritmos de empaquetamiento unidimensionales simples". Revista SIAM de Computación . 3 (4): 299–325. doi :10.1137/0203025. ISSN  0097-5397.
9. Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Empaquetado de contenedores con tamaños de elementos divisibles". Journal of Complexity . 3 (4): 406–428. doi :10.1016/0885-064X(87)90009-4. ISSN  0885-064X.
10. Yao, Andrew Chi-Chih (abril de 1980). "Nuevos algoritmos para el empaquetamiento de contenedores". Revista de la ACM . 27 (2): 207–227. doi : 10.1145/322186.322187 . S2CID  7903339.