Problema de contenedor

El problema del contenedor o el problema del embalaje del contenedor es un problema de optimización combinatoria basado en la siguiente pregunta:

• Dado: Un número de "contenedores" ( bin inglés ) del tamaño y un número de "objetos" con los pesos (tamaños) .${\ Displaystyle k \ in \ mathbb {N}}$ ${\ Displaystyle b \ in \ mathbb {N}}$${\ Displaystyle n \ in \ mathbb {N}}$${\ Displaystyle a_ {1}, a_ {2}, \ dotsc, a_ {n} \ \ leq \ b}$
• Pregunta: ¿Se pueden distribuir los "objetos" a los "contenedores" ( embalaje ) de tal manera que ninguno de los "contenedores" se desborde? Formalmente:${\ Displaystyle n}$${\ Displaystyle k}$

${\ Displaystyle \ existe \ f \ colon \ {1, \ dotsc, n \} \ to \ {1, \ dotsc, k \} {\ text {de modo que para todos}} j \ in \ {1, \ dotsc , k \} \ quad \ sum _ {f (i) = j} a_ {i} \ leq b {\ text {¿se aplica?}}}$

El problema de decisión descrito anteriormente es NP-completo ; el problema de optimización asociado - encontrar una asignación en la que se minimice el número de contenedores - es NP-difícil .

La formulación del problema del embalaje en contenedores que se da aquí es solo la motivación o la base para una gran cantidad de otros problemas de embalaje que juegan un papel importante en la industria del embalaje , entre otros .

Una definición formal algo más general describe el problema del embalaje en contenedores como la determinación de una partición y la asignación de un conjunto de objetos para que se cumpla una determinada condición o se minimice o maximice una función objetivo.

Se hace una distinción entre variantes en línea y fuera de línea, donde fuera de línea significa que todos los objetos se conocen de antemano. En el proceso online, se debe decidir inmediatamente en qué contenedor se embalará el objeto sin conocer los siguientes objetos.

Algoritmos

Dado que el empaquetado en contenedores es un problema NP-difícil, probablemente sea imposible de resolver en el tiempo de ejecución polinomial. El algoritmo de aproximación de Johnson First Fit Decreasing resuelve el problema en tiempo polinomial con una garantía de calidad asintótica de . ${\ Displaystyle 11 \ over 9}$

Sortiere die Objekte nach absteigendem Gewicht
Füge die Objekte der Reihe nach ein,
sodass jedes in den ersten Behälter gegeben wird, in dem noch genug Platz ist.
Falls in keinem der bereits geöffneten Behälter genügend Platz ist, öffne einen neuen.

El tiempo de ejecución es (tanto para ordenar como para insertar). Los mismos resultados también se aplican a Mejor ajuste decreciente . Un objeto no se inserta en el primer contenedor en el que cabe, sino en el contenedor en el que simplemente cabe (la capacidad restante se minimiza así). ${\ Displaystyle {\ mathcal {O}} (n \ cdot \ log n)}$

Con la variante en línea, no es posible clasificar los objetos por peso de antemano. Los algoritmos First Fit y Best Fit funcionan de forma análoga a los anteriores, pero sin clasificación previa. Ambos algoritmos tienen una garantía de calidad asintótica aguda de 1.7 y un tiempo de ejecución de . Best Fit busca el espacio libre más pequeño que todavía está disponible en todos los contenedores disponibles hasta ahora. ${\ Displaystyle {\ mathcal {O}} (n \ cdot \ log n)}$

El ingenuo algoritmo Next Fit empaqueta los objetos uno tras otro en el último contenedor abierto, si encajan. De lo contrario, el contenedor se cierra, se abre uno nuevo y el objeto actual se coloca en el contenedor vacío. La garantía de calidad asintótica es 2, el plazo . La ventaja de este algoritmo ingenuo es que solo se abre un contenedor a la vez (lo que puede ser una condición en el uso práctico). ${\ Displaystyle {\ mathcal {O}} (n)}$

literatura

• Bernhard Korte, Jens Vygen: Optimización combinatoria. Springer, Berlín Heidelberg 2008, ISBN 978-3-540-76918-7 , p. 485ff

enlaces web

• Optimización del embalaje de contenedores tridimensionales
• Artículo en el algoritmo de la semana.