Embalaje de contenedores armónicos

El empaquetamiento armónico de contenedores es una familia de algoritmos en línea para el empaquetamiento de contenedores . La entrada de un algoritmo de este tipo es una lista de elementos de diferentes tamaños. La 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.

Los algoritmos de empaquetamiento armónico se basan en dividir los elementos en categorías según sus tamaños, siguiendo una progresión armónica . Existen varias variantes de esta idea.

Armónico-a

El algoritmo Harmonic- k divide el intervalo de tamaños de manera armónica en partes para y de manera que . Un elemento se denomina -elemento si . ${\displaystyle (0,1]}$ ${\displaystyle k-1}$ ${\displaystyle I_{j}:=(1/(j+1),1/j]}$ ${\displaystyle 1\leq j<k}$ ${\displaystyle I_{k}:=(0,1/k]}$ ${\displaystyle \bigcup _{j=1}^{k}I_{j}=(0,1]}$ ${\displaystyle i\in L}$ ${\displaystyle I_{j}}$ ${\displaystyle s(i)\in I_{j}}$

El algoritmo divide el conjunto de contenedores vacíos en infinitas clases para , un tipo de contenedor para cada tipo de elemento. Un contenedor de tipo solo se utiliza para contenedores que contienen elementos de tipo . Cada contenedor de tipo para puede contener exactamente -elementos. El algoritmo ahora actúa de la siguiente manera: ${\displaystyle k}$ ${\displaystyle B_{j}}$ ${\displaystyle 1\leq j\leq k}$ ${\displaystyle B_{j}}$ ${\displaystyle j}$ ${\displaystyle B_{j}}$ ${\displaystyle 1\leq j<k}$ ${\displaystyle j}$ ${\displaystyle I_{j}}$

• Si el siguiente elemento es un -elemento para , el elemento se coloca en el primer contenedor (el único abierto) que contiene menos de piezas o abre uno nuevo si no existe dicho contenedor. ${\displaystyle i\in L}$ ${\displaystyle I_{j}}$ ${\displaystyle 1\leq j<k}$ ${\displaystyle B_{j}}$ ${\displaystyle j}$
• Si el siguiente elemento es un -item, el algoritmo lo coloca en los contenedores de tipo usando Next-Fit. ${\displaystyle i\in L}$ ${\displaystyle I_{k}}$ ${\displaystyle B_{k}}$

Este algoritmo fue descrito por primera vez por Lee y Lee. ^[1] Tiene una complejidad temporal de donde n es el número de elementos de entrada. En cada paso, hay como máximo contenedores abiertos que pueden usarse potencialmente para colocar elementos, es decir, es un algoritmo de espacio acotado en k . ${\displaystyle {\mathcal {O}}(n\log(n))}$ ${\displaystyle k}$

Lee y Lee también estudiaron la razón de aproximación asintótica. Definieron una secuencia , para y demostraron que para se cumple que . Para se cumple que . Además, presentaron una familia de ejemplos del peor caso para eso ${\displaystyle \sigma _{1}:=1}$ ${\displaystyle \sigma _{i+1}:=\sigma _{i}(\sigma _{i}+1)}$ ${\displaystyle i\geq 1}$ ${\displaystyle \sigma _{l}<k<\sigma _{l+1}}$ ${\displaystyle R_{Hk}^{\infty }\leq \sum _{i=1}^{l}1/\sigma _{i}+k/(\sigma _{l+1}(k-1))}$ ${\displaystyle k\rightarrow \infty }$ ${\displaystyle R_{Hk}^{\infty }\approx 1.6910}$ ${\displaystyle R_{Hk}^{\infty }=\sum _{i=1}^{l}1/\sigma _{i}+k/(\sigma _{l+1}(k-1))}$

Armónico refinado (RH)

El algoritmo Refined-Harmonic combina ideas del algoritmo Harmonic-k con ideas de Refined-First-Fit . Coloca los elementos más grandes que los similares como en Refined-First-Fit, mientras que los elementos más pequeños se colocan utilizando Harmonic-k. La intuición de esta estrategia es reducir el enorme desperdicio de contenedores que contienen piezas que son solo más grandes que . ${\displaystyle 1/3}$ ${\displaystyle 1/2}$

El algoritmo clasifica los elementos en relación con los siguientes intervalos: , , , , , para , y . El algoritmo coloca los elementos como en Harmonic-k, mientras que sigue una estrategia diferente para los elementos en y . Hay cuatro posibilidades para empaquetar los elementos y los elementos en contenedores. ${\displaystyle I_{1}:=(59/96,1]}$ ${\displaystyle I_{a}:=(1/2,59/96]}$ ${\displaystyle I_{2}:=(37/96,1/2]}$ ${\displaystyle I_{b}:=(1/3,37/96]}$ ${\displaystyle I_{j}:=(1/(j+1),1/j]}$ ${\displaystyle j\in \{3,\dots ,k-1\}}$ ${\displaystyle I_{k}:=(0,1/k]}$ ${\displaystyle I_{j}}$ ${\displaystyle I_{a}}$ ${\displaystyle I_{b}}$ ${\displaystyle I_{a}}$ ${\displaystyle I_{b}}$

• Un -bin contiene sólo un -elemento. ${\displaystyle I_{a}}$ ${\displaystyle I_{a}}$
• Un -bin contiene sólo un -elemento. ${\displaystyle I_{b}}$ ${\displaystyle I_{b}}$
• Un -bin contiene un -item y un -item. ${\displaystyle I_{a}b}$ ${\displaystyle I_{a}}$ ${\displaystyle I_{b}}$
• Un -bin contiene dos -elementos. ${\displaystyle I_{b}b}$ ${\displaystyle I_{b}}$

Un -bin denota un contenedor que está designado para contener un segundo elemento. El algoritmo utiliza los números N_a, N_b, N_ab, N_bb y N_b' para contar la cantidad de contenedores correspondientes en la solución. Además, N_c = N_b + N_ab ${\displaystyle I_{b}'}$ ${\displaystyle I_{b}}$

Algoritmo armónico refinado-k para una lista L = (i_1, \dots i_n):1. N_a = N_b = N_ab = N_bb = N_b' = N_c = 02. Si i_j es una pieza I_k Luego usa el algoritmo Harmonic-k para empaquetarlo.3. de lo contrario, si i_j es un elemento I_a entonces si N_b != 1, luego empaqueta i_j en cualquier J_b-bin; N_b--; N_ab++; de lo contrario, coloque i_j en un nuevo contenedor (vacío); N_a++;4. de lo contrario, si i_j es un elemento I_b entonces si N_b' = 1 luego coloque i_j en el contenedor I_b'; N_b' = 0; N_bb++;5. de lo contrario si N_bb <= 3N_c Luego, coloque i_j en un nuevo contenedor y asígnele el nombre de contenedor I_b'; N_b' = 1 De lo contrario, si N_a != 0 luego coloque i_j en cualquier I_a-bin; N_a--; N_ab++;N_c++ de lo contrario, coloque i_j en un nuevo contenedor; N_b++;N_c++

Este algoritmo fue descrito por primera vez por Lee y Lee. ^[1] Demostraron que para se cumple que . ${\displaystyle k=20}$ ${\displaystyle R_{RH}^{\infty }\leq 373/228}$

Otras variantes

El armónico modificado (MH) tiene una relación asintótica . ^[2] ${\displaystyle R_{MH}^{\infty }\leq 538/33\approx 1.61562}$

El armónico modificado 2 (MH2) tiene una relación asintótica . ^[2] ${\displaystyle R_{MH2}^{\infty }\leq 239091/148304\approx 1.61217}$

El armónico + 1 (H+1) tiene una relación asintótica . ^[3] ${\displaystyle R_{H+1}^{\infty }\geq 1.59217}$

El armónico ++ (H++) tiene una relación asintótica ^[3] y . ^[3] ${\displaystyle R_{H++}^{\infty }\leq 1.58889}$ ${\displaystyle R_{H++}^{\infty }\geq 1.58333}$

Referencias

1. Lee, CC; Lee, DT (julio de 1985). "Un algoritmo simple de empaquetamiento de contenedores en línea". Revista de la ACM . 32 (3): 562–572. doi : 10.1145/3828.3833 . S2CID  15441740.
2. Ramanan, Prakash; Brown, Donna J; Lee, CC; Lee, DT (septiembre de 1989). "Empaquetado de contenedores en línea en tiempo lineal". Journal of Algorithms . 10 (3): 305–326. doi :10.1016/0196-6774(89)90031-X. hdl : 2142/74206 .
3. Seiden, Steven S. (2002). "Sobre el problema del empaquetamiento de contenedores en línea". Revista de la ACM . 49 (5): 640–671. doi :10.1145/585265.585269. S2CID  14164016.