Embalaje de contenedores de siguiente ajuste

Next-fit 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 next-fit utiliza la siguiente heurística :

• Mantiene un contenedor actual , que inicialmente está vacío.
• Cuando llega un artículo, se verifica si cabe en el contenedor actual.
  • Si cabe se coloca dentro.
  • De lo contrario, se cierra el contenedor actual, se abre uno nuevo y el próximo elemento se coloca dentro de este nuevo contenedor.

Next-Fit es un algoritmo de espacio acotado: solo requiere que haya un contenedor parcialmente lleno abierto en cualquier momento. El algoritmo fue estudiado por David S. Johnson en su tesis doctoral ^[1] en 1973.

Tiempo de ejecución

El tiempo de ejecución de NextFit se puede limitar mediante , donde es el número de elementos en la lista. ^[2] ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle n}$

Relación de aproximación

Denotemos por NF(L) el número de contenedores utilizados por NextFit, y por OPT(L) el número óptimo de contenedores posibles para la lista L.

Límite superior

Entonces, para cada lista , . La intuición de la prueba es la siguiente. El número de contenedores utilizados por este algoritmo no es más que el doble del número óptimo de contenedores. En otras palabras, es imposible que 2 contenedores estén como máximo medio llenos porque tal posibilidad implica que en algún momento, exactamente un contenedor estaba como máximo medio lleno y se abrió uno nuevo para acomodar un elemento de tamaño como máximo . Pero como el primero tiene al menos un espacio de , el algoritmo no abrirá un nuevo contenedor para ningún elemento cuyo tamaño sea como máximo . Solo después de que el contenedor se llena con más de o si llega un elemento con un tamaño mayor que , el algoritmo puede abrir un nuevo contenedor. Por lo tanto, si tenemos contenedores, al menos contenedores están más de la mitad llenos. Por lo tanto, . Como es un límite inferior del valor óptimo , obtenemos que y por lo tanto . ^{[3] : 74} ${\displaystyle L}$ ${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$ ${\displaystyle B/2}$ ${\displaystyle B/2}$ ${\displaystyle B/2}$ ${\displaystyle B/2}$ ${\displaystyle B/2}$ ${\displaystyle K}$ ${\displaystyle K-1}$ ${\displaystyle \sum _{i\in I}s(i)>{\tfrac {K-1}{2}}B}$ ${\displaystyle {\tfrac {\sum _{i\in I}s(i)}{B}}}$ ${\displaystyle \mathrm {OPT} }$ ${\displaystyle K-1<2\mathrm {OPT} }$ ${\displaystyle K\leq 2\mathrm {OPT} }$

Límite inferior

Para cada , existe una lista tal que y . ${\displaystyle N\in \mathbb {N} }$ ${\displaystyle L}$ ${\displaystyle \mathrm {OPT} (L)=N}$ ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$

La familia de listas para las que se cumple que está dada por con . La solución óptima para esta lista tiene contenedores que contienen dos elementos con tamaño y un contenedor con elementos con tamaño (es decir, contenedores totales), mientras que la solución generada por NF tiene contenedores con un elemento de tamaño y un elemento con tamaño . ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$ ${\displaystyle L:=\left({\frac {1}{2}},{\frac {1}{2(N-1)}},{\frac {1}{2}},{\frac {1}{2(N-1)}},\dots ,{\frac {1}{2}},{\frac {1}{2(N-1)}}\right)}$ ${\displaystyle |L|=4(N-1)}$ ${\displaystyle N-1}$ ${\displaystyle 1/2}$ ${\displaystyle 2(N-1)}$ ${\displaystyle 1/2(N-1)}$ ${\displaystyle N}$ ${\displaystyle 2(N-1)}$ ${\displaystyle 1/2}$ ${\displaystyle 1/(2(N-1))}$

Tamaño de elemento limitado

Si el tamaño máximo de un elemento es , entonces la razón de aproximación asintótica satisface: ${\displaystyle \alpha }$ ${\displaystyle R_{NF}^{\infty }}$

• ${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2}$para todos ; ${\displaystyle \alpha \geq 1/2}$
• ${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )}$Para todos . ${\displaystyle \alpha \leq 1/2}$

Otras propiedades

Next-Fit empaqueta una lista y su inversa en el mismo número de contenedores. ^[4]

Próximo-a-Ajuste (NkF)

Next-k-Fit es una variante de Next-Fit, pero en lugar de mantener solo un contenedor abierto, el algoritmo mantiene abiertos los últimos contenedores y elige el primer contenedor en el que encaja el artículo. ${\displaystyle k}$

Para , NkF ofrece resultados que son mejores en comparación con los resultados de NF, sin embargo, aumentar a valores constantes mayores que no mejora el algoritmo más en su comportamiento en el peor de los casos. Si el algoritmo es un algoritmo AlmostAnyFit y entonces . ^[1] ${\displaystyle k\geq 2}$ ${\displaystyle k}$ ${\displaystyle 2}$ ${\displaystyle A}$ ${\displaystyle m=\lfloor 1/\alpha \rfloor \geq 2}$ ${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{size}}\leq \alpha )=1+1/m}$

Véase también

• Next-fit-decreasing (NFD) es la variante offline de Next-Fit: acepta todos los elementos de entrada, los ordena por tamaño descendente y llama a Next-Fit. Su razón de aproximación asintótica es mucho mejor: menos de 1,7, en lugar de 2.

Referencias

1. Johnson, David S (1973). "Algoritmos de empaquetamiento de contenedores casi óptimos" (PDF) . Instituto Tecnológico de Massachusetts .
2. Suri, Subhash. "Bin Packing". Ciencias de la Computación de la UCSB . Consultado el 7 de octubre de 2021 .
3. Vazirani, Vijay V. (2003), Algoritmos de aproximación , Berlín: Springer, ISBN 3-540-65367-8
4. Fisher, David C. (1988-12-01). "Next-fit empaqueta una lista y su reverso en el mismo número de contenedores". Operations Research Letters . 7 (6): 291–293. doi :10.1016/0167-6377(88)90060-0. ISSN  0167-6377.