Relleno de contenedores de ajuste siguiente

Next-fit-decreasing (NFD) 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 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 NFD utiliza la siguiente heurística :

Ordene los artículos del más grande al más pequeño.
Inicializa un contenedor vacío y llámalo "contenedor abierto".
Para cada artículo del pedido, verifique si cabe en el contenedor abierto:
- Si encaja, coloque el nuevo artículo dentro.
- De lo contrario, cierre el contenedor actual, abra uno nuevo y coloque el elemento actual dentro de él.

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

Límite superior de rendimiento

Baker y Coffman ^[1] demostraron que, para cada entero r , cuando el tamaño de todos los elementos es como máximo 1/ r , la relación de aproximación asintótica de RFD satisface

$R_{NFD}^{\infty }({\text{tamaño}}\leq 1/r)=h_{\infty }(r)$ ,

donde es una secuencia cuyos primeros elementos son aproximadamente 1,69103, 1,42312, 1,30238. En particular, tomar r = 1 implica que ${\ Displaystyle h _ {\ infty} (r)}$

$R_{NFD}^{\infty }=h_{\infty }(1)\aproximadamente 1,69103$ .

Posteriormente, la NFD también se analizó probabilísticamente. ^[2]

Variantes

Next-Fit empaqueta una lista y su inversa en la misma cantidad de contenedores. Por lo tanto, Next-Fit-Increasing tiene el mismo rendimiento que Next-Fit-Decreasing. ^[3]

Sin embargo, el método Next-Fit-Increasing funciona mejor cuando existen estructuras de costos generales. ^[4]

Referencias

^ Baker, BS; Coffman, Jr., EG (1981-06-01). "Un límite asintótico ajustado para el empaquetamiento de bins de ajuste siguiente decreciente". Revista SIAM sobre métodos algebraicos y discretos . 2 (2): 147–152. doi :10.1137/0602019. ISSN 0196-5212.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
^ Csirik, J.; Galambos, G.; Frenk, JBG; Frieze, AM; Rinnooy Kan, AHG (1986-11-01). "Un análisis probabilístico de la heurística de empaquetamiento de bins decreciente del siguiente ajuste". Operations Research Letters . 5 (5): 233–236. doi :10.1016/0167-6377(86)90013-1. hdl : 1765/11645 . ISSN 0167-6377.
^ 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.
^ Anily, Shoshana; Bramel, Julien; Simchi-Levi, David (1 de abril de 1994). "Análisis del peor caso de heurísticas para el problema de empaquetamiento de contenedores con estructuras de costos generales". Investigación de operaciones . 42 (2): 287–298. doi :10.1287/opre.42.2.287. ISSN 0030-364X.