Problema de embalaje del contenedor

Problema matemático y computacional.

El problema del embalaje en contenedores ^{[1] [2] [3] [4]} es un problema de optimización , en el que artículos de diferentes tamaños deben empaquetarse en un número finito de contenedores o contenedores, cada uno de una capacidad determinada fija, de manera que Minimiza el número de contenedores utilizados. El problema tiene muchas aplicaciones, como llenar contenedores, cargar camiones con limitaciones de capacidad de peso, crear copias de seguridad de archivos en medios y mapeo tecnológico en el diseño de chips semiconductores FPGA .

Computacionalmente, el problema es NP-difícil , y el problema de decisión correspondiente , decidir si los artículos pueden caber en un número específico de contenedores, es NP-completo . A pesar de su dureza en el peor de los casos, se pueden producir soluciones óptimas para instancias muy grandes del problema con algoritmos sofisticados. Además, existen muchos algoritmos de aproximación . Por ejemplo, el algoritmo de primer ajuste proporciona una solución rápida pero a menudo no óptima, que implica colocar cada artículo en el primer contenedor en el que encajará. Requiere Θ ( n  log  n ) tiempo, donde n es el número de artículos a empacar. El algoritmo se puede hacer mucho más efectivo clasificando primero la lista de elementos en orden decreciente (a veces conocido como algoritmo decreciente de primer ajuste), aunque esto aún no garantiza una solución óptima y, para listas más largas, puede aumentar el tiempo de ejecución del algoritmo. Sin embargo, se sabe que siempre existe al menos un orden de elementos que permite que el primer ajuste produzca una solución óptima. ^[5]

Hay muchas variaciones de este problema, como empaque 2D, empaque lineal, empaque por peso, empaque por costo, etc. El problema del embalaje del contenedor también puede verse como un caso especial del problema del material de corte . Cuando el número de contenedores se restringe a 1 y cada artículo se caracteriza tanto por un volumen como por un valor, el problema de maximizar el valor de los artículos que pueden caber en el contenedor se conoce como problema de la mochila .

Una variante del embalaje en contenedores que ocurre en la práctica es cuando los artículos pueden compartir espacio cuando se empaquetan en un contenedor. Específicamente, un conjunto de artículos podría ocupar menos espacio cuando se empaquetan juntos que la suma de sus tamaños individuales. Esta variante se conoce como empaquetado de VM ^[6] ya que cuando las máquinas virtuales (VM) se empaquetan en un servidor, su requisito de memoria total podría disminuir debido a que las páginas compartidas por las VM solo necesitan almacenarse una vez. Si los artículos pueden compartir espacio de manera arbitraria, el problema del embalaje del contenedor es difícil incluso de aproximarse. Sin embargo, si el espacio compartido encaja en una jerarquía, como es el caso de la memoria compartida en máquinas virtuales, el problema del empaquetado de contenedores se puede aproximar de manera eficiente.

Otra variante de embalaje en contenedores que resulta interesante en la práctica es el llamado embalaje en contenedores en línea . Aquí los artículos de diferente volumen deben llegar secuencialmente, y quien toma la decisión tiene que decidir si selecciona y empaqueta el artículo actualmente observado, o si lo deja pasar. Cada decisión es irrevocable. Por el contrario, el embalaje en contenedores fuera de línea permite reorganizar los artículos con la esperanza de lograr un mejor embalaje una vez que lleguen artículos adicionales. Por supuesto, esto requiere almacenamiento adicional para guardar los elementos que se van a reorganizar.

Declaración formal

En Computers and Intractability ^{[7] : 226} Garey y Johnson enumeran el problema del embalaje del contenedor bajo la referencia [SR1]. Definen su variante de decisión de la siguiente manera.

Instancia: conjunto finito de elementos, un tamaño para cada uno , una capacidad de contenedor de número entero positivo y un número entero positivo . ${\displaystyle I}$ ${\displaystyle s(i)\in \mathbb {Z} ^{+}}$ ${\displaystyle i\in I}$ ${\displaystyle B}$ ${\displaystyle K}$

Pregunta: ¿Existe una partición en conjuntos disjuntos de modo que la suma de los tamaños de los elementos en cada uno sea o menor? ${\displaystyle I}$ ${\displaystyle I_{1},\dots ,I_{K}}$ ${\displaystyle I_{j}}$ ${\displaystyle B}$

Tenga en cuenta que en la literatura se utiliza a menudo una notación equivalente, donde y para cada . Además, la investigación está interesada principalmente en la variante de optimización, que solicita el valor más pequeño posible de . Una solución es óptima si tiene un mínimo . El valor para una solución óptima para un conjunto de elementos se denota por o simplemente si el conjunto de elementos se desprende del contexto. ${\displaystyle B=1}$ ${\displaystyle s(i)\in \mathbb {Q} \cap (0,1]}$ ${\displaystyle i\in I}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle I}$ ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {OPT} }$

Una posible formulación de programación lineal entera del problema es:

donde si se usa el contenedor y si el artículo se coloca en el contenedor . ^[8] ${\displaystyle y_{j}=1}$ ${\displaystyle j}$ ${\displaystyle x_{ij}=1}$ ${\displaystyle i}$ ${\displaystyle j}$

Dureza del embalaje del contenedor

El problema del embalaje del contenedor es fuertemente NP-completo . Esto se puede demostrar reduciendo el problema de 3 particiones fuertemente NP completo al embalaje en contenedores. ^[7]

Además, no puede haber ningún algoritmo de aproximación con una relación de aproximación absoluta menor que a menos que . Esto se puede demostrar mediante una reducción del problema de partición : ^[9] dada una instancia de Partición donde la suma de todos los números de entrada es , construya una instancia de empaquetado de contenedores en la que el tamaño del contenedor sea T . Si existe una partición igual de las entradas, entonces el embalaje óptimo necesita 2 contenedores; por lo tanto, todo algoritmo con una relación de aproximación menor que ${\displaystyle {\tfrac {3}{2}}}$ ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ ${\displaystyle 2T}$3/2debe devolver menos de 3 contenedores, que deben ser 2 contenedores. Por el contrario, si no hay una partición equitativa de las entradas, entonces el embalaje óptimo necesita al menos 3 contenedores.

Por otro lado, el embalaje de contenedores se puede resolver en tiempo pseudopolinomial para cualquier número fijo de contenedores K y se puede resolver en tiempo polinomial para cualquier capacidad de contenedor fija B. ^[7]

Algoritmos de aproximación para el embalaje de contenedores.

Para medir el rendimiento de un algoritmo de aproximación, se consideran dos ratios de aproximación en la literatura. Para una lista determinada de elementos, el número indica el número de contenedores utilizados cuando se aplica el algoritmo a la lista , mientras que indica el número óptimo para esta lista. La relación de rendimiento absoluta en el peor de los casos para un algoritmo se define como ${\displaystyle L}$ ${\displaystyle A(L)}$ ${\displaystyle A}$ ${\displaystyle L}$ ${\displaystyle \mathrm {OPT} (L)}$ ${\displaystyle R_{A}}$ ${\displaystyle A}$

${\displaystyle R_{A}\equiv \inf\{r\geq 1:A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L\}.}$

Por otro lado, la relación asintótica del peor de los casos se define como ${\displaystyle R_{A}^{\infty }}$

${\displaystyle R_{A}^{\infty }\equiv \inf\{r\geq 1:\exists N>0,A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L{\text{ with }}\mathrm {OPT} (L)\geq N\}.}$

De manera equivalente, es el número más pequeño tal que exista una constante K, tal que para todas las listas L: ^[4] ${\displaystyle R_{A}^{\infty }}$

${\displaystyle A(L)\leq R_{A}^{\infty }\cdot \mathrm {OPT} (L)+K}$.

Además, se pueden restringir las listas a aquellas en las que todos los elementos tengan un tamaño como máximo de . Para dichas listas, las proporciones de rendimiento de tamaño acotado se indican como y . ${\displaystyle \alpha }$ ${\displaystyle R_{A}({\text{size}}\leq \alpha )}$ ${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )}$

Los algoritmos de aproximación para el embalaje en contenedores se pueden clasificar en dos categorías:

1. Heurísticas online, que consideran los elementos en un orden determinado y los colocan uno por uno dentro de los contenedores. Estas heurísticas también son aplicables a la versión fuera de línea de este problema.
2. Heurísticas fuera de línea, que modifican la lista dada de elementos, por ejemplo, ordenando los elementos por tamaño. Estos algoritmos ya no son aplicables a la variante en línea de este problema. Sin embargo, tienen una garantía de aproximación mejorada manteniendo la ventaja de su pequeña complejidad temporal. Una subcategoría de heurísticas fuera de línea son los esquemas de aproximación asintótica. Estos algoritmos tienen una garantía de aproximación de la forma para alguna constante que puede depender de . Para un valor arbitrariamente grande, estos algoritmos se acercan arbitrariamente a . Sin embargo, esto tiene el costo de una complejidad temporal (drásticamente) mayor en comparación con los enfoques heurísticos. ${\displaystyle (1+\varepsilon )\mathrm {OPT} (L)+C}$ ${\displaystyle 1/\varepsilon }$ ${\displaystyle \mathrm {OPT} (L)}$ ${\displaystyle \mathrm {OPT} (L)}$

Heurística en línea

En la versión en línea del problema del embalaje del contenedor, los artículos llegan uno tras otro y la decisión (irreversible) de dónde colocar un artículo debe tomarse antes de saber el siguiente artículo o incluso si habrá otro. David S. Johnson ha estudiado un conjunto diverso de heurísticas en línea y fuera de línea para el embalaje en contenedores en su doctorado. tesis. ^[10]

Algoritmos de clase única

Existen muchos algoritmos simples que utilizan el siguiente esquema general:

• Para cada elemento de la lista de entrada:
  1. Si el artículo cabe en uno de los contenedores abiertos actualmente, colóquelo en uno de estos contenedores;
  2. De lo contrario, abra un contenedor nuevo y coloque el nuevo artículo en él.

Los algoritmos difieren en el criterio por el cual eligen el contenedor abierto para el nuevo artículo en el paso 1 (consulte las páginas vinculadas para obtener más información):

• Next Fit (NF) siempre mantiene un único contenedor abierto. Cuando el nuevo artículo no cabe en él, cierra el contenedor actual y abre uno nuevo. Su ventaja es que es un algoritmo de espacio acotado, ya que sólo necesita mantener un único contenedor abierto en la memoria. Su desventaja es que su relación de aproximación asintótica es 2. En particular,y para cada unoexiste una lista L tal quey. ^[10] Su relación de aproximación asintótica se puede mejorar algo en función de los tamaños de los elementos:para todosypara todos. Para cada algoritmo A que sea un algoritmo AnyFit, se cumple que. ${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$ ${\displaystyle N\in \mathbb {N} }$ ${\displaystyle \mathrm {OPT} (L)=N}$ ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$ ${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2}$ ${\displaystyle \alpha \geq 1/2}$ ${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )}$ ${\displaystyle \alpha \leq 1/2}$ ${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{NF}^{\infty }({\text{size}}\leq \alpha )}$
• Next-k-Fit (NkF) es una variante de Next-Fit, pero en lugar de mantener solo un contenedor abierto, el algoritmo mantiene abiertos los últimos k contenedores y elige el primer contenedor en el que cabe el artículo. Por lo tanto, se denomina algoritmo espacial acotado k . ^[11] PorqueNkF ofrece resultados que mejoran en comparación con los resultados de NF; sin embargo, aumentar k a valores constantes mayores que 2 no mejora más el algoritmo en su peor comportamiento. Si el algoritmo A es un algoritmo AlmostAnyFit yluego. ^[10] ${\displaystyle k\geq 2}$ ${\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}$
• First-Fit (FF) mantiene todos los contenedores abiertos, en el orden en que fueron abiertos. Intenta colocar cada artículo nuevo en el primer contenedor en el que cabe. Su relación de aproximación es, y existe una familia de listas de entrada L para las cualescoincide con este límite. ^[12] ${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$ ${\displaystyle FF(L)}$
• Best-Fit (BF) también mantiene todos los contenedores abiertos, pero intenta colocar cada artículo nuevo en el contenedor con la carga máxima en la que cabe. Su relación de aproximación es idéntica a la de FF, es decir:, y existe una familia de listas de entrada L para las quecoincide con este límite. ^[13] ${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$ ${\displaystyle BF(L)}$
• Worst-Fit (WF) intenta colocar cada artículo nuevo en el contenedor con la carga mínima . Puede comportarse tan mal como Next-Fit y lo hará en la lista de peores casos . Además, sostiene que . Dado que WF es un algoritmo AnyFit, existe un algoritmo AnyFit tal que . ^[10] ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$ ${\displaystyle R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )}$ ${\displaystyle R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )}$
• Almost Worst-Fit (AWF) intenta colocar cada artículo nuevo dentro del segundo contenedor abierto más vacío (o el contenedor más vacío si hay dos de esos contenedores). Si no cabe, prueba con el más vacío. Tiene una relación asintótica en el peor de los casos de . ^[10] ${\displaystyle {\tfrac {17}{10}}}$

Para generalizar estos resultados, Johnson introdujo dos clases de heurísticas en línea llamadas algoritmo de cualquier ajuste y algoritmo de casi cualquier ajuste : ^{[4] : ​​470}

• En un algoritmo AnyFit (AF) , si los contenedores actuales no vacíos son B ₁ ,..., B _j , entonces el artículo actual no se empaquetará en B _{j +1} a menos que no quepa en ninguno de B ₁ ,.. ., B _j . Los algoritmos FF, WF, BF y AWF satisfacen esta condición. Johnson demostró que, para cualquier algoritmo AnyFit A y cualquier : ${\displaystyle \alpha }$

  ${\displaystyle R_{FF}^{\infty }(\alpha )\leq R_{A}^{\infty }(\alpha )\leq R_{WF}^{\infty }(\alpha )}$.

• En un algoritmo AlmostAnyFit (AAF) , si los contenedores actuales no vacíos son B ₁ ,..., B _j , y de estos contenedores, B _k es el único contenedor con la carga más pequeña, entonces el artículo actual no se empaquetará en B. _k , a menos que no quepa en ninguno de los contenedores a su izquierda. Los algoritmos FF, BF y AWF satisfacen esta condición, pero WF no. Johnson demostró que, para cualquier algoritmo AAF A y cualquier α :

  ${\displaystyle R_{A}^{\infty }(\alpha )=R_{FF}^{\infty }(\alpha )}$ En particular: . ${\displaystyle R_{A}^{\infty }=1.7}$

Algoritmos refinados

Es posible obtener mejores ratios de aproximación con heurísticas que no sean AnyFit. Estas heurísticas suelen mantener varias clases de contenedores abiertos, dedicados a artículos de diferentes rangos de tamaño (consulte las páginas vinculadas para obtener más información):

• El embalaje de contenedor de primer ajuste (RFF) refinado divide los tamaños de los artículos en cuatro rangos:,,y. Del mismo modo, los contenedores se clasifican en cuatro clases. El siguiente elementose asigna primero a su clase correspondiente. Dentro de esa clase, se asigna a un contenedor mediante first-fit . Tenga en cuenta que este algoritmo no es un algoritmo Any-Fit, ya que puede abrir un nuevo contenedor a pesar de que el elemento actual cabe dentro de un contenedor abierto. Este algoritmo fue presentado por primera vez por Andrew Chi-Chih Yao, ^[14] quien demostró que tiene una garantía de aproximacióny presentó una familia de listasconfor. ${\displaystyle \left({\frac {1}{2}},1\right]}$ ${\displaystyle \left({\frac {2}{5}},{\frac {1}{2}}\right]}$ ${\displaystyle \left({\frac {1}{3}},{\frac {2}{5}}\right]}$ ${\displaystyle \left(0,{\frac {1}{3}}\right]}$ ${\displaystyle i\in L}$ ${\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}$
• Harmonic-k divide el intervalo de tamañosbasándose en una progresión armónica enpartesparaytal que. Este algoritmo fue descrito por primera vez por Lee y Lee. ^[15] Tiene una complejidad temporal dey en cada paso, hay como máximo k contenedores abiertos que pueden usarse potencialmente para colocar elementos, es decir, es unalgoritmo de espacio acotado k . Para, su relación de aproximación satisfacey es asintóticamente ajustada. ${\displaystyle (0,1]}$ ${\displaystyle k-1}$ ${\displaystyle I_{j}:=\left({\frac {1}{j+1}},{\frac {1}{j}}\right]}$ ${\displaystyle 1\leq j<k}$ ${\displaystyle I_{k}:=\left(0,{\frac {1}{k}}\right]}$ ${\displaystyle \bigcup _{j=1}^{k}I_{j}=(0,1]}$ ${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$ ${\displaystyle k\rightarrow \infty }$ ${\displaystyle R_{Hk}^{\infty }\approx 1.6910}$
• Refined-harmonic combina ideas de Harmonic-k con ideas de Refined-First-Fit . Coloca los elementos más grandes quesimilares como en Refined-First-Fit, mientras que los elementos más pequeños se colocan usando Harmonic-k. La intuición de esta estrategia es reducir el enorme desperdicio de contenedores que contienen piezas que son apenas más grandes que. Este algoritmo fue descrito por primera vez por Lee y Lee. ^[15] Probaron que porquese cumple que. ${\displaystyle {\tfrac {1}{3}}}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle k=20}$ ${\displaystyle R_{RH}^{\infty }\leq 373/228}$

Límites inferiores generales para algoritmos en línea

Yao ^[14] demostró en 1980 que no puede haber ningún algoritmo en línea con una relación competitiva asintótica menor que . Brown ^[16] y Liang ^[17] mejoraron este límite para ${\displaystyle {\tfrac {3}{2}}}$1.536 35 . Posteriormente, este límite se mejoró a1.540 14 por Vliet. ^{[18] En 2012, Békési y Galambos [19]} volvieron a mejorar este límite inferior a . ${\displaystyle {\tfrac {248}{161}}\approx 1.54037}$

Tabla de comparación

Algoritmos sin conexión

En la versión fuera de línea del embalaje en contenedores, el algoritmo puede ver todos los artículos antes de comenzar a colocarlos en los contenedores. Esto permite alcanzar ratios de aproximación mejorados.

Aproximación multiplicativa

La técnica más sencilla utilizada por los esquemas de aproximación fuera de línea es la siguiente:

• Ordenar la lista de entrada por tamaño descendente;
• Ejecute un algoritmo en línea en la lista ordenada.

Johnson ^[10] demostró que cualquier esquema AnyFit A que se ejecute en una lista ordenada por tamaño descendente tiene una relación de aproximación asintótica de

${\displaystyle 1.22\approx {\frac {11}{9}}\leq R_{A}^{\infty }\leq {\frac {5}{4}}=1.25}$.

Algunos métodos de esta familia son (consulte las páginas vinculadas para obtener más información):

• First-fit-decreasing (FFD) ordena los elementos por tamaño descendente y luego llama a First-Fit. Su relación de aproximación es, y es ajustada. ^[22] ${\displaystyle FFD(I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}}$
• Next-fit-decreasing (NFD) ordena los elementos por tamaño descendente y luego llama a Next-Fit . Su ratio aproximado es ligeramente inferior a 1,7 en el peor de los casos. ^[23] También se ha analizado probabilísticamente. ^[24] 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. ^[25]
• Modificado de primer ajuste decreciente (MFFD) ^[26] , mejora el FFD para artículos de más de medio contenedor al clasificar los artículos por tamaño en cuatro clases de tamaño: grande, mediano, pequeño y diminuto, correspondientes a artículos con tamaño > 1/2 bin, > 1/3 bin, > 1/6 bin y artículos más pequeños respectivamente. Su garantía de aproximación es. ^[27] ${\displaystyle MFFD(I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1}$

Fernández de la Vega y Lueker ^[28] presentaron una PTAS para embalaje en contenedores. Para cada , su algoritmo encuentra una solución con tamaño como máximo y se ejecuta en el tiempo , donde denota una función que sólo depende de . Para este algoritmo, inventaron el método de redondeo de entrada adaptativo : los números de entrada se agrupan y se redondean al valor máximo en cada grupo. Esto produce una instancia con una pequeña cantidad de tamaños diferentes, que se puede resolver exactamente usando el programa lineal de configuración . ^[29] ${\displaystyle \varepsilon >0}$ ${\displaystyle (1+\varepsilon )\mathrm {OPT} +1}$ ${\displaystyle {\mathcal {O}}(n\log(1/\varepsilon ))+{\mathcal {O}}_{\varepsilon }(1)}$ ${\displaystyle {\mathcal {O}}_{\varepsilon }(1)}$ ${\displaystyle 1/\varepsilon }$

Aproximación aditiva

El algoritmo de empaquetado bin Karmarkar-Karp encuentra una solución con un tamaño como máximo y se ejecuta en un polinomio de tiempo en n (el polinomio tiene un grado alto, al menos 8). ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))}$

Rothvoss ^[30] presentó un algoritmo que genera una solución con como máximo contenedores. ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))}$

Hoberg y Rothvoss ^[31] mejoraron este algoritmo para generar una solución con como máximo contenedores. El algoritmo es aleatorio y su tiempo de ejecución es polinómico en n . ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} ))}$

Tabla de comparación

Algoritmos exactos

Martello y Toth ^[33] desarrollaron un algoritmo exacto para el problema de embalaje de contenedores unidimensional, llamado MTP. Una alternativa más rápida es el algoritmo Bin Completion propuesto por Korf en 2002 ^[34] y posteriormente mejorado. ^[35]

Schreiber y Korf presentaron una mejora adicional en 2013. ^[36] Se ha demostrado que el nuevo algoritmo de finalización de contenedores mejorado es hasta cinco órdenes de magnitud más rápido que la finalización de contenedores en problemas no triviales con 100 elementos, y supera al BCP (rama -and-cut-and-price) de Belov y Scheithauer sobre problemas que tienen menos de 20 contenedores como solución óptima. El algoritmo que funciona mejor depende de las propiedades del problema, como la cantidad de elementos, la cantidad óptima de contenedores, el espacio no utilizado en la solución óptima y la precisión del valor.

Pequeño número de diferentes tamaños.

Un caso especial de embalaje en contenedores es cuando hay una pequeña cantidad d de artículos de diferentes tamaños. Puede haber muchos artículos diferentes de cada tamaño. Este caso también se denomina embalaje bin de alta multiplicidad y admite algoritmos más eficientes que el problema general.

Embalaje en contenedores con fragmentación

El embalaje en contenedores con fragmentación o el embalaje en contenedores con objetos fragmentables es una variante del problema del embalaje en contenedores en el que se permite dividir los artículos en partes y colocar cada parte por separado en un contenedor diferente. Dividir los artículos en partes puede permitir mejorar el rendimiento general, por ejemplo, minimizando el número total de contenedores. Además, el problema computacional de encontrar un cronograma óptimo puede volverse más fácil a medida que algunas de las variables de optimización se vuelven continuas. Por otro lado, separar elementos puede resultar costoso. El problema fue presentado por primera vez por Mandal, Chakrabary y Ghose. ^[37]

Variantes

El problema tiene dos variantes principales.

1. En la primera variante, denominada bin-packing con fragmentación que aumenta el tamaño ( BP-SIF ), cada artículo puede estar fragmentado; Al tamaño de cada fragmento se le suman unidades superiores.
2. En la segunda variante, llamada bin-packing con fragmentación que preserva el tamaño ( BP-SPF ), cada artículo tiene un tamaño y un costo; fragmentar un artículo aumenta su costo pero no cambia su tamaño.

Complejidad computacional

Mandal, Chakrabary y Ghose ^[37] demostraron que BP-SPF es NP-duro .

Menakerman y Rom ^[38] demostraron que BP-SIF y BP-SPF son ambos fuertemente NP-duros . A pesar de la dureza, presentan varios algoritmos e investigan su rendimiento. Sus algoritmos utilizan algoritmos clásicos para el empaquetado de contenedores, como la disminución del siguiente ajuste y del primer ajuste , como base para sus algoritmos.

Bertazzi, Golden y Wang ^[39] introdujeron una variante de BP-SIF con regla de división: un artículo puede dividirse de una sola manera según su tamaño. Es útil para el problema de generación de rutas de vehículos, por ejemplo. En su artículo, proporcionan el límite de rendimiento en el peor de los casos de la variante. ${\displaystyle 1-x}$

Shachnai, Tamir y Yehezkeli ^[40] desarrollaron esquemas de aproximación para BP-SIF y BP-SPF; un PTAS dual (un PTAS para la versión dual del problema), un PTAS asintótico llamado APTAS y un FPTAS asintótico dual llamado AFPTAS para ambas versiones.

Ekici ^[41] introdujo una variante de BP-SPF en la que algunos elementos están en conflicto y está prohibido empaquetar fragmentos de elementos en conflicto en el mismo contenedor. Demostraron que esta variante también es NP-dura.

Cassazza y Ceselli ^[42] introdujeron una variante sin coste ni gastos generales, y el número de contenedores es fijo. Sin embargo, se debe minimizar el número de fragmentaciones. Presentan algoritmos de programación matemática para soluciones exactas y aproximadas.

Problemas relacionados

El problema de la mochila fraccionada con penalizaciones lo introdujeron Malaguti, Monaci, Paronuzzi y Pferschy. ^[43] Desarrollaron un FPTAS y un programa dinámico para el problema, y ​​mostraron un extenso estudio computacional comparando el rendimiento de sus modelos. Véase también: Programación de trabajos fraccionada .

Restricciones de cardinalidad en los contenedores.

Existe una variante del empaquetado de contenedores en la que existen restricciones de cardinalidad en los contenedores: cada contenedor puede contener como máximo k elementos, para algún entero fijo k .

• Krause, Shen y Schwetman ^[44] introducen este problema como una variante de la programación óptima del trabajo : una computadora tiene algunos k procesadores. Hay algunos n trabajos que toman una unidad de tiempo (1), pero tienen diferentes requisitos de memoria. Cada unidad de tiempo se considera un único contenedor. El objetivo es utilizar la menor cantidad posible de contenedores (= unidades de tiempo) y, al mismo tiempo, garantizar que en cada contenedor se ejecuten como máximo k trabajos. Presentan varios algoritmos heurísticos que encuentran una solución con la mayoría de los contenedores. ${\displaystyle 2\mathrm {OPT} }$
• Kellerer y Pferschy ^[45] presentan un algoritmo con tiempo de ejecución que encuentra una solución con la mayoría de los contenedores. Su algoritmo realiza una búsqueda binaria de OPT. Por cada valor buscado m , intenta empaquetar los artículos en contenedores de 3 m /2. ${\displaystyle O(n^{2}\log {n})}$ ${\displaystyle \left\lceil {\frac {3}{2}}\mathrm {OPT} \right\rceil }$

Funciones no aditivas

Hay varias formas de extender el modelo de embalaje en contenedores a funciones de carga y costos más generales:

• Anily, Bramel y Simchi-Levi ^[46] estudian un entorno donde el costo de un contenedor es una función cóncava del número de artículos en el contenedor. El objetivo es minimizar el coste total en lugar del número de contenedores. Muestran que el empaquetamiento de contenedores creciente del siguiente ajuste alcanza una relación de aproximación absoluta en el peor de los casos de como máximo 7/4, y una relación asintótica en el peor de los casos de 1,691 para cualquier función de costo cóncava y monótona.
• Cohen, Keller, Mirrokni y Zadimoghaddam ^[47] estudian un entorno donde el tamaño de los elementos no se conoce de antemano, pero es una variable aleatoria . Esto es particularmente común en entornos de computación en la nube . Si bien existe un límite superior en la cantidad de recursos que necesita un determinado usuario, la mayoría de los usuarios utilizan mucho menos que la capacidad. Por lo tanto, el administrador de la nube puede ganar mucho con un ligero exceso de compromiso . Esto induce una variante del embalaje en contenedores con restricciones de probabilidad: la probabilidad de que la suma de los tamaños en cada contenedor sea como máximo B debe ser al menos p , donde p es una constante fija (el embalaje en contenedores estándar corresponde a p =1). Muestran que, bajo supuestos suaves, este problema es equivalente a un problema de embalaje de contenedores submodulares , en el que la "carga" en cada contenedor no es igual a la suma de los artículos, sino a una determinada función submodular de los mismos.

Problemas relacionados

En el problema del embalaje de contenedores, el tamaño de los contenedores es fijo y su número puede ampliarse (pero debe ser lo más pequeño posible).

Por el contrario, en el problema de partición de números de múltiples vías , el número de contenedores es fijo y su tamaño se puede ampliar. El objetivo es encontrar una partición en la que los tamaños de los contenedores sean lo más iguales posible (en la variante llamada problema de programación multiprocesador o problema de makepan mínimo , el objetivo es específicamente minimizar el tamaño del contenedor más grande).

En el problema de embalaje de contenedores inversos , ^[48] tanto el número de contenedores como sus tamaños son fijos, pero los tamaños de los artículos se pueden cambiar. El objetivo es lograr la mínima perturbación en el vector de tamaño de los artículos para que todos los artículos puedan empaquetarse en el número prescrito de contenedores.

En el problema de embalaje máximo de contenedores de recursos , ^[49] el objetivo es maximizar el número de contenedores utilizados, de modo que, para algunos pedidos de los contenedores, ningún elemento de un contenedor posterior quepa en un contenedor anterior. En un problema dual, el número de contenedores es fijo y el objetivo es minimizar el número total o el tamaño total de los artículos colocados en los contenedores, de modo que ningún artículo restante quepa en un contenedor vacío.

En el problema de cobertura de contenedores , el tamaño del contenedor está limitado desde abajo : el objetivo es maximizar el número de contenedores utilizados de modo que el tamaño total en cada contenedor sea al menos un umbral determinado.

En el problema de asignación justa e indivisible de tareas (una variante de la asignación justa de elementos ), los elementos representan tareas y hay diferentes personas, cada una de las cuales atribuye un valor de dificultad diferente a cada tarea. El objetivo es asignar a cada persona un conjunto de tareas con un límite superior en su valor de dificultad total (por lo tanto, a cada persona le corresponde un contenedor). En este problema también se utilizan muchas técnicas de embalaje en contenedores. ^[50]

En el problema del corte con guillotina , tanto los artículos como los "contenedores" son rectángulos bidimensionales en lugar de números unidimensionales, y los artículos deben cortarse del contenedor mediante cortes de extremo a extremo.

En el problema egoísta del embalaje del contenedor , cada artículo es un jugador que quiere minimizar su coste. ^[51]

También existe una variante del embalaje en contenedores en la que el coste que se debe minimizar no es el número de contenedores, sino una determinada función cóncava del número de artículos en cada contenedor. ^[46]

Otras variantes son embalaje en contenedor bidimensional, ^[52] embalaje en contenedor tridimensional , ^[53] embalaje en contenedor con entrega , ^[54]

Recursos

• BPPLIB: una biblioteca de encuestas, códigos, puntos de referencia, generadores, solucionadores y bibliografía.

Implementaciones

• Online : visualización de heurísticas para el embalaje de contenedores 1D y 2D
• Python: el paquete prtpy contiene código para varios algoritmos de partición de números, empaquetado de contenedores y cobertura de contenedores. El paquete binpacking contiene algoritmos codiciosos para resolver dos problemas típicos de embalaje de contenedores. ^[55]
• C++ : el paquete bin-packing contiene varios algoritmos codiciosos, así como datos de prueba. El paquete OR-tools contiene algoritmos de empaquetado bin en C++, con contenedores en Python, C# y Java.
• C : Implementación de 7 algoritmos clásicos de empaquetado de contenedores aproximados en C con resultados e imágenes
• PHP : Clase PHP para empaquetar archivos sin exceder un límite de tamaño determinado
• Haskell : una implementación de varias heurísticas de empaquetado de contenedores, incluidas FFD y MFFD.
• C : Fpart: herramienta de línea de comandos de código abierto para empaquetar archivos (C, con licencia BSD)
• C# : Solucionador de stock de corte y embalaje de contenedores
• Java : caparf: marco de investigación de algoritmos de corte y embalaje, que incluye varios algoritmos de embalaje de contenedores y datos de prueba.

Referencias

1. Martello, Silvano; Toth, Paolo (1990), "Problema del embalaje en contenedores" (PDF) , Problemas de mochila: algoritmos e implementaciones informáticas , Chichester, Reino Unido: John Wiley and Sons, ISBN 0471924202
2. Korte, Bernhard; Vygen, Jens (2006). "Embalaje en contenedores". Optimización combinatoria: teoría y algoritmos . Algoritmos y combinatoria 21. Springer. págs. 426–441. doi :10.1007/3-540-29297-7_18. ISBN 978-3-540-25684-7.
3. Barrington, mezcla de David (2006). "Embalaje en contenedor". Archivado desde el original el 16 de febrero de 2019 . Consultado el 27 de febrero de 2016 .
4. Coffman Jr., Edward G.; Csirik, János; Galambos, Gábor; Martello, Silvano; Vigo, Daniele (2013), Pardalos, Panos M.; Du, Ding-Zhu; Graham, Ronald L. (eds.), "Algoritmos de aproximación de embalaje de contenedores: encuesta y clasificación", Manual de optimización combinatoria , Nueva York, NY: Springer, págs. 455–531, doi :10.1007/978-1-4419-7997 -1_35, ISBN 978-1-4419-7997-1, recuperado 2021-08-08
5. Lewis, R. (2009), "Un método de escalada de colinas de uso general para problemas de agrupación mínima independiente del orden: un estudio de caso sobre coloración de gráficos y embalaje de contenedores" (PDF) , Investigación de operaciones y computadoras , 36 (7): 2295 –2310, doi :10.1016/j.cor.2008.09.004, S2CID  1577334
6. Sindelar, Michael; Sitaraman, Ramesh ; Shenoy, Prashant (2011), "Algoritmos compatibles con el uso compartido para la colocación de máquinas virtuales" (PDF) , Actas del 23º Simposio ACM sobre paralelismo en algoritmos y arquitecturas (SPAA), San José, CA, junio de 2011 : 367–378
7. Garey, MR ; Johnson, DS (1979). Víctor Klee (ed.). Computadoras e intratabilidad: una guía para la teoría de la integridad NP . Una serie de libros sobre ciencias matemáticas. San Francisco, California: W. H. Freeman and Co. págs. x+338. ISBN 0-7167-1045-5. SEÑOR  0519066.
8. Martello y Toth 1990, pag. 221
9. Vazirani, Vijay V. (14 de marzo de 2013). Algoritmos de aproximación . Springer Berlín Heidelberg. pag. 74.ISBN _ 978-3662045657.
10. Johnson, David S (1973). "Algoritmos de embalaje de contenedores casi óptimos" (PDF) . Instituto de Tecnología de Massachusetts .
11. González, Teófilo F. (23 de mayo de 2018). Manual de algoritmos de aproximación y metaheurísticas. Volumen 2 Aplicaciones contemporáneas y emergentes . Taylor y Francis incorporados. ISBN 9781498770156.
12. 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) . Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 20 : 538–549. doi :10.4230/LIPIcs.STACS.2013.538.
13. György, Dósa; Sgall, Jirí (2014). "Análisis óptimo del embalaje del contenedor de mejor ajuste". Autómatas, lenguajes y programación . Apuntes de conferencias sobre informática. vol. 8572, págs. 429–441. doi :10.1007/978-3-662-43948-7_36. ISBN 978-3-662-43947-0. {{cite book}}: |journal=ignorado ( ayuda )
14. Yao, Andrew Chi-Chih (abril de 1980). "Nuevos algoritmos para el embalaje de contenedores". Revista de la ACM . 27 (2): 207–227. doi : 10.1145/322186.322187 . S2CID  7903339.
15. Lee, CC; Lee, DT (julio de 1985). "Un algoritmo sencillo de embalaje de contenedores en línea". Revista de la ACM . 32 (3): 562–572. doi : 10.1145/3828.3833 . S2CID  15441740.
16. Donna J, marrón (1979). "Un límite inferior para algoritmos de embalaje de contenedores unidimensionales en línea" (PDF) . Representante Técnico . Archivado (PDF) desde el original el 17 de marzo de 2022.
17. Liang, Frank M. (1980). "Un límite inferior para el embalaje en contenedores en línea". Cartas de procesamiento de información . 10 (2): 76–79. doi :10.1016/S0020-0190(80)90077-0.
18. van Vliet, André (1992). "Un límite inferior mejorado para los algoritmos de embalaje de contenedores en línea". Cartas de procesamiento de información . 43 (5): 277–284. doi :10.1016/0020-0190(92)90223-I.
19. Balogh, János; Békési, József; Galambos, Gábor (julio de 2012). "Nuevos límites inferiores para determinadas clases de algoritmos de embalaje de contenedores". Informática Teórica . 440–441: 1–13. doi : 10.1016/j.tcs.2012.04.017 .
20. Ramanan, Prakash; Marrón, Donna J; Lee, CC; Lee, DT (septiembre de 1989). "Embalaje de contenedores en línea en tiempo lineal". Revista de algoritmos . 10 (3): 305–326. doi :10.1016/0196-6774(89)90031-X. hdl : 2142/74206 .
21. Seiden, Steven S. (2002). "Sobre el problema del embalaje de contenedores en línea". Revista de la ACM . 49 (5): 640–671. doi :10.1145/585265.585269. S2CID  14164016.
22. Dósa, György (2007). "El límite estrecho del algoritmo de embalaje de contenedores decreciente del primer ajuste es FFD (I) ≤ 11/9 \ mathrm {OPT} (I) + 6/9". Combinatoria, Algoritmos, Metodologías Probabilísticas y Experimentales. ESCAPAR . doi :10.1007/978-3-540-74450-4_1.
23. Panadero, BS; Coffman, Jr., EG (1 de junio de 1981). "Un límite asintótico estrecho para el embalaje de contenedores decreciente del siguiente ajuste". Revista SIAM de Métodos Algebraicos y Discretos . 2 (2): 147-152. doi :10.1137/0602019. ISSN  0196-5212.{{cite journal}}: CS1 maint: multiple names: authors list (link)
24. Csirik, J.; Galambos, G.; Frenk, JBG; Friso, AM; Rinnooy Kan, AHG (1 de noviembre de 1986). "Un análisis probabilístico de la heurística de embalaje de contenedores decreciente del siguiente ajuste". Cartas de investigación operativa . 5 (5): 233–236. doi :10.1016/0167-6377(86)90013-1. hdl : 1765/11645 . ISSN  0167-6377. S2CID  50663185.
25. Pescador, David C. (1 de diciembre de 1988). "Next-fit empaqueta una lista y su reverso en la misma cantidad de contenedores". Cartas de investigación operativa . 7 (6): 291–293. doi :10.1016/0167-6377(88)90060-0. ISSN  0167-6377.
26. Johnson, David S; Garey, Michael R (octubre de 1985). "Un teorema 7160 para el embalaje de contenedores". Revista de Complejidad . 1 (1): 65-106. doi : 10.1016/0885-064X(85)90022-6 .
27. Yue, Minyi; Zhang, Lei (julio de 1995). "Una prueba simple de la desigualdad MFFD(L) ≤ 71/60 OPT(L) + 1,L para el algoritmo de empaquetado en contenedores MFFD". Acta Mathematicae Applicatae Sínica . 11 (3): 318–330. doi :10.1007/BF02011198. S2CID  118263129.
28. Fernández de la Vega, W.; Lueker, GS (1981). "El embalaje del contenedor se puede resolver en 1 + ε en tiempo lineal". Combinatoria . 1 (4): 349–355. doi :10.1007/BF02579456. ISSN  1439-6912. S2CID  10519631.
29. Claire Mathieu. "Algoritmos de aproximación Parte I, Semana 3: embalaje en contenedores". Coursera . Archivado desde el original el 15 de julio de 2021.
30. Rothvoß, T. (1 de octubre de 2013). "Aproximación del embalaje de contenedores dentro de contenedores O (log OPT · Log Log OPT)". 2013 54º Simposio Anual del IEEE sobre Fundamentos de la Informática . págs. 20-29. arXiv : 1301.4010 . doi :10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7. S2CID  15905063.
31. Hoberg, Rebecca; Rothvoss, Thomas (1 de enero de 2017), "A Logarithmic Additive Integrality Gap for Bin Packing", Actas del Simposio anual ACM-SIAM de 2017 sobre algoritmos discretos , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. arXiv : 1503.08796 , doi : 10.1137/1.9781611974782.172 , ISBN 978-1-61197-478-2, S2CID  1647463
32. Karmarkar, Narendra; Karp, Richard M. (noviembre de 1982). "Un esquema de aproximación eficiente para el problema del embalaje en contenedores unidimensional". 23º Simposio anual sobre fundamentos de la informática (SFCS 1982) : 312–320. doi :10.1109/SFCS.1982.61. S2CID  18583908.
33. Martello y Toth 1990, págs. 237-240.
34. Korf, Richard E. (2002). Un nuevo algoritmo para un embalaje óptimo de contenedores (PDF) . AAAI-02.
35. RE Korf (2003), Un algoritmo mejorado para un embalaje óptimo del contenedor . Actas de la Conferencia Conjunta Internacional sobre Inteligencia Artificial, (págs. 1252-1258)
36. Schreiber, Ethan L.; Korf, Richard E. (2013), "Compleción mejorada de contenedores para un embalaje óptimo de contenedores y una partición de números" (PDF) , Actas de la vigésimo tercera conferencia conjunta internacional sobre inteligencia artificial , IJCAI '13, Beijing, China: AAAI Press, págs. 651–658, ISBN 978-1-57735-633-2
37. Mandal, California; Chakrabarti, PP; Ghose, S. (1 de junio de 1998). "Complejidad del embalaje de contenedores de objetos fragmentables y una aplicación". Computadoras y Matemáticas con Aplicaciones . 35 (11): 91–97. doi :10.1016/S0898-1221(98)00087-X. ISSN  0898-1221.
38. Nir Menakerman y Raphael Rom "Embalaje en contenedores con fragmentación de artículos". Algoritmos y estructuras de datos, Séptimo taller internacional, WADS 2001, Providence, RI, EE. UU., 8 al 10 de agosto de 2001, Actas.
39. Bertazzi, Luca; Dorado, Bruce; Wang, Xingyin (31 de mayo de 2019). "El problema del embalaje en contenedores con fragmentación de artículos: un análisis del peor de los casos". Matemática Aplicada Discreta . Reunión GO X, Rigi Kaltbad (CH), 10 al 14 de julio de 2016. 261 : 63–77. doi : 10.1016/j.dam.2018.08.023 . ISSN  0166-218X. S2CID  125361557.
40. Shachnai, Hadas; Tamir, Tami; Yehezkely, Omer (2006). "Esquemas de aproximación para embalaje con fragmentación de artículos". En Erlebach, Thomas; Persinao, Giuseppe (eds.). Aproximación y Algoritmos en Línea . Apuntes de conferencias sobre informática. vol. 3879. Berlín, Heidelberg: Springer. págs. 334–347. doi :10.1007/11671411_26. ISBN 978-3-540-32208-5.
41. Ekici, Ali (1 de febrero de 2021). "Problema de embalaje en contenedores con conflictos y fragmentación de artículos". Investigación de operaciones y computadoras . 126 : 105113. doi : 10.1016/j.cor.2020.105113. ISSN  0305-0548. S2CID  225002556.
42. Casazza, Marco; Ceselli, Alberto (1 de junio de 2014). "Algoritmos de programación matemática para problemas de embalaje de contenedores con fragmentación de artículos". Investigación de operaciones y computadoras . 46 : 1–11. doi :10.1016/j.cor.2013.12.008. ISSN  0305-0548.
43. Malaguti, Enrico; Monaci, Michele; Paronuzzi, Paolo; Pferschy, Ulrich (16 de marzo de 2019). "Optimización de enteros con valores fraccionarios penalizados: el caso de la mochila". Revista europea de investigación operativa . 273 (3): 874–888. doi :10.1016/j.ejor.2018.09.020. hdl : 11585/657029 . ISSN  0377-2217. S2CID  31722681.
44. Krause, KL; Shen, VY; Schwetman, HD (1 de octubre de 1975). "Análisis de varios algoritmos de programación de tareas para un modelo de sistemas informáticos de multiprogramación". Revista de la ACM . 22 (4): 522–550. doi : 10.1145/321906.321917 . ISSN  0004-5411. S2CID  10214857.
45. Kellerer, H.; Pferschy, U. (1 de enero de 1999). "La cardinalidad limitó los problemas de embalaje en contenedores". Anales de investigación de operaciones . 92 : 335–348. doi :10.1023/A:1018947117526. ISSN  1572-9338. S2CID  28963291.
46. abAnily, Shoshana; Bramel, Julien; Simchi-Levi, David (1 de abril de 1994). "Análisis de heurísticas del peor de los casos para el problema del embalaje de contenedores con estructuras de costos generales". La investigación de operaciones . 42 (2): 287–298. doi :10.1287/opre.42.2.287. ISSN  0030-364X.
47. Cohen, Maxime C.; Keller, Philipp W.; Mirrokni, Vahab; Zadimoghaddam, Morteza (1 de julio de 2019). "Compromiso excesivo en servicios en la nube: embalaje de contenedores con restricciones de probabilidad". Ciencias de la gestión . 65 (7): 3255–3271. arXiv : 1705.09335 . doi :10.1287/mnsc.2018.3091. ISSN  0025-1909. S2CID  159270392.
48. Chung, Yerim; Park, Myoung-Ju (1 de enero de 2015). "Notas sobre problemas de embalaje en contenedores inversos". Cartas de procesamiento de información . 115 (1): 60–68. doi :10.1016/j.ipl.2014.09.005. ISSN  0020-0190.
49. Boyardo, Juana ; Epstein, Leah; Favrholdt, Lene M.; Kohrt, Jens S.; Larsen, Kim S.; Pedersen, Morten M.; Wøhlk, Sanne (11 de octubre de 2006). "El problema del embalaje del contenedor de recursos máximo". Informática Teórica . 362 (1): 127-139. doi : 10.1016/j.tcs.2006.06.001. ISSN  0304-3975.
50. Huang, Xin; Lu, Pinyan (10 de noviembre de 2020). "Un marco algorítmico para aproximar la asignación de tareas compartidas de Maximin". arXiv : 1907.04505 [cs.GT].
51. Mamá, Ruixin; Dósa, György; Han, Xin; Ting, Hing-Fung; Sí, Deshi; Zhang, Yong (1 de agosto de 2013). "Una nota sobre un problema egoísta de embalaje de contenedores". Revista de optimización global . 56 (4): 1457-1462. doi :10.1007/s10898-012-9856-9. ISSN  0925-5001. S2CID  3082040.
52. Lodi A., Martello S., Monaci, M., Vigo, D. (2010) "Problemas de embalaje de contenedores bidimensionales". En V.Th. Paschos (Ed.), Paradigmas de optimización combinatoria , Wiley/ISTE, págs. 107-129
53. Optimización del embalaje de contenedores tridimensionales mediante simulación
54. Benkő A., Dósa G., Tuza Z. (2010) "Embalaje/cubrimiento de contenedores con entrega, resuelto con la evolución de algoritmos", Actas de la Quinta Conferencia Internacional IEEE 2010 sobre Computación Bioinspirada: Teorías y aplicaciones, BIC-TA 2010 , art. No. 5645312, págs. 298–302.
55. Vaccaro, Alessio (13 de noviembre de 2020). "🧱 4 pasos para asignar recursos fácilmente con Python y Bin Packing". Medio . Consultado el 21 de marzo de 2021 .