Problema de embalaje del contenedor

Problema matemático y computacional

El problema del empaquetamiento de contenedores ^{[1] [2] [3] [4]} es un problema de optimización en el que se deben empaquetar elementos de diferentes tamaños en un número finito de contenedores, cada uno de una capacidad fija determinada, de manera que se minimice la cantidad de contenedores utilizados. El problema tiene muchas aplicaciones, como llenar contenedores, cargar camiones con restricciones de capacidad de peso, crear copias de seguridad de archivos en medios, dividir un prefijo de red en múltiples subredes ^[5] y mapeo de tecnología en el diseño de chips semiconductores FPGA .

Computacionalmente, el problema es NP-hard , y el problema de decisión correspondiente , decidir si los elementos pueden caber en un número específico de contenedores, es NP-completo . A pesar de su dificultad 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 elemento en el primer contenedor en el que encajará. Requiere Θ ( n  log  n ) tiempo, donde n es el número de elementos a empaquetar. El algoritmo puede hacerse mucho más efectivo ordenando primero la lista de elementos en orden decreciente (a veces conocido como el algoritmo decreciente de primer ajuste), aunque esto todavía 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 ordenamiento de elementos que permite que el primer ajuste produzca una solución óptima. ^[6]

Existen muchas variantes de este problema, como el empaquetado en 2D, el empaquetado lineal, el empaquetado por peso, el empaquetado por costo, etc. El problema del empaquetado en contenedores también puede considerarse un caso especial del problema del stock de corte . Cuando el número de contenedores se limita 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 caben en el contenedor se conoce como el problema de la mochila .

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

Otra variante del empaquetado de contenedores que resulta de interés en la práctica es el denominado empaquetado de contenedores en línea . En este caso, se supone que los artículos de diferente volumen llegan secuencialmente y el responsable de la toma de decisiones debe decidir si selecciona y empaqueta el artículo observado en ese momento o lo deja pasar. Cada decisión se toma sin necesidad de recordar nada. Por el contrario, el empaquetado de contenedores fuera de línea permite reorganizar los artículos con la esperanza de lograr un mejor empaquetado cuando lleguen artículos adicionales. Por supuesto, esto requiere almacenamiento adicional para guardar los artículos que se van a reorganizar.

Declaración formal

En Computers and Intractability ^{[8] : 226,} Garey y Johnson enumeran el problema de empaquetamiento de contenedores 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 tal 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 a menudo se utiliza una notación equivalente, donde y para cada . Además, la investigación se interesa principalmente por 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 de . El valor de una solución óptima para un conjunto de elementos se denota por o simplemente si el conjunto de elementos se desprende claramente 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 utiliza el contenedor y si el artículo se coloca en el contenedor . ^[9] ${\displaystyle y_{j}=1}$ ${\displaystyle j}$ ${\displaystyle x_{ij}=1}$ ${\displaystyle i}$ ${\displaystyle j}$

Dureza del embalaje del contenedor

El problema de empaquetamiento de bins es fuertemente NP-completo . Esto se puede demostrar reduciendo el problema de 3 particiones fuertemente NP-completo al empaquetamiento de bins. ^[8]

Además, no puede haber ningún algoritmo de aproximación con una razón de aproximación absoluta menor que a menos que . Esto se puede demostrar mediante una reducción del problema de partición : ^[10] dada una instancia de Partición donde la suma de todos los números de entrada es , construya una instancia de empaquetamiento de bins en la que el tamaño del bin sea T . Si existe una partición igual de las entradas, entonces el empaquetamiento óptimo necesita 2 bins; por lo tanto, cada algoritmo con una razón de aproximación menor que ⁠ ${\displaystyle {\tfrac {3}{2}}}$ ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ ${\displaystyle 2T}$3/2⁠ debe 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 empaquetamiento óptimo necesita al menos 3 contenedores.

Por otra parte, el empaquetamiento 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 fija de contenedor B. ^[8]

Algoritmos de aproximación para el empaquetamiento de contenedores

Para medir el rendimiento de un algoritmo de aproximación, en la literatura se consideran dos ratios de aproximación. Para una lista dada de elementos, el número denota el número de contenedores utilizados cuando se aplica el algoritmo a la lista , mientras que denota el número óptimo para esta lista. El ratio de rendimiento absoluto 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 otra parte, la razón asintótica del peor caso 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 existe alguna 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 tienen un tamaño de como máximo . Para dichas listas, los índices de rendimiento de tamaño limitado 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 empaquetamiento de contenedores se pueden clasificar en dos categorías:

1. Heurísticas en línea, 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 al tiempo que mantienen 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 de empaquetado de contenedores, los artículos llegan uno tras otro y la decisión (irreversible) de dónde colocar un artículo debe tomarse antes de saber cuál será el siguiente 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 empaquetado de contenedores en su tesis doctoral. ^[11]

Algoritmos de clase única

Hay 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 actualmente abiertos, colóquelo en uno de estos contenedores;
  2. De lo contrario, abra un nuevo contenedor y coloque el nuevo artículo dentro.

Los algoritmos difieren en el criterio con el que 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 bin abierto. Cuando el nuevo elemento no cabe en él, cierra el bin actual y abre uno nuevo. Su ventaja es que es un algoritmo de espacio acotado, ya que solo necesita mantener un único bin abierto en la memoria. Su desventaja es que su razón de aproximación asintótica es 2. En particular,, y para cada unoexiste una lista L tal quey. ^[11] Su razón de aproximación asintótica se puede mejorar un poco 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 abierto solo un contenedor, el algoritmo mantiene abiertos los últimos k contenedores y elige el primer contenedor en el que encaja el elemento. Porlo tanto, se denomina algoritmo de espacio acotado por k . ^[12] El NkF ofrece resultados que mejoran en comparación con los resultados de NF, sin embargo, aumentar k a valores constantes mayores que 2 no mejora aún más el algoritmo en su comportamiento en el peor de los casos. Si el algoritmo A es un algoritmo AlmostAnyFit yentonces. ^[11] ${\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 nuevo elemento en el primer contenedor en el que encaja. Su razón de aproximación es, y hay una familia de listas de entrada L para las quecoincide con este límite. ^[13] ${\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 nuevo elemento 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 hay una familia de listas de entrada L para las quecoincide con este límite. ^[14] ${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$ ${\displaystyle BF(L)}$
• Worst-Fit (WF) intenta colocar cada nuevo elemento en el contenedor con la carga mínima . Puede comportarse tan mal como Next-Fit y lo hará en la lista de peores casos para ese . Además, cumple que . Dado que WF es un algoritmo AnyFit, existe un algoritmo AnyFit tal que . ^[11] ${\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 )}$
• El método Almost Worst-Fit (AWF) intenta colocar cada elemento nuevo dentro del segundo contenedor abierto más vacío (o el contenedor más vacío si hay dos contenedores de este tipo). Si no cabe, prueba con el más vacío. Tiene una razón asintótica de peor caso de . ^[11] ${\displaystyle {\tfrac {17}{10}}}$

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

• En un algoritmo AnyFit (AF) , si los contenedores no vacíos actuales son B ₁ ,..., B _j , entonces el elemento 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 no vacíos actuales son B ₁ ,..., B _j , y de estos contenedores, B _k es el único contenedor con la carga más pequeña, entonces el elemento 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

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

• El empaquetamiento de contenedores de ajuste refinado (RFF) divide los tamaños de los elementos en cuatro rangos:,,y. De manera similar, 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 utilizando el primer ajuste . Tenga en cuenta que este algoritmo no es un algoritmo Any-Fit ya que puede abrir un nuevo contenedor a pesar del hecho de que el elemento actual encaja dentro de un contenedor abierto. Este algoritmo fue presentado por primera vez por Andrew Chi-Chih Yao, ^[15] quien demostró que tiene una garantía de aproximación dey presentó una familia de listasconpara. ${\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ñosenpartesbasadas en una progresión armónica paraytales que. Lee y Lee describieron por primera vez este algoritmo. ^[16] Tiene una complejidad temporal dey en cada paso, hay como máximo k contenedores abiertos que se pueden usar potencialmente para colocar elementos, es decir, es unalgoritmo espacial acotado por k . Para , su relación de aproximación satisface, y es asintóticamente ajustado. ${\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}$
• El algoritmo armónico refinado 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 utilizando 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. ^[16] Demostraron que parase 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 ^[15] demostró en 1980 que no puede haber ningún algoritmo en línea con una relación competitiva asintótica menor que . Brown ^[17] y Liang ^[18] mejoraron este límite a ${\displaystyle {\tfrac {3}{2}}}$1.536 35 . Posteriormente, este límite se mejoró a1.540 14 por Vliet. ^[19] En 2012, este límite inferior fue mejorado nuevamente por Békési y Galambos ^[20] a . ${\displaystyle {\tfrac {248}{161}}\approx 1.54037}$

Tabla comparativa

Algoritmos offline

En la versión offline del empaquetado en contenedores, el algoritmo puede ver todos los artículos antes de comenzar a colocarlos en los contenedores, lo que permite lograr mejores ratios de aproximación.

Aproximación multiplicativa

La técnica más simple 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 ^[11] 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):

• El método First-fit-decreasing (FFD) ordena los elementos por tamaño descendente y luego llama a First-Fit. Su razón de aproximación es, y es ajustada. ^[23] ${\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 relación aproximada es ligeramente inferior a 1,7 en el peor de los casos. ^[24] También se ha analizado de forma probabilística. ^[25] Next-Fit empaqueta una lista y su inversa en el mismo número de contenedores. Por lo tanto, Next-Fit-Increasing tiene el mismo rendimiento que Next-Fit-Decreasing. ^[26]
• La primera opción de ajuste modificado decreciente (MFFD) ^[27] mejora la FFD para elementos más grandes que la mitad de un contenedor al clasificar los elementos por tamaño en cuatro clases de tamaño: grande, mediano, pequeño y diminuto, que corresponden a elementos con un tamaño > 1/2 contenedor, > 1/3 contenedor, > 1/6 contenedor y elementos más pequeños respectivamente. Su garantía de aproximación es. ^[28] ${\displaystyle MFFD(I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1}$

Fernández de la Vega y Lueker ^[29] presentaron un PTAS para empaquetamiento de bins. Para cada , su algoritmo encuentra una solución con tamaño como máximo y se ejecuta en tiempo , donde denota una función que solo 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 un pequeño número de tamaños diferentes, que se puede resolver exactamente utilizando el programa lineal de configuración . ^[30] ${\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 empaquetamiento de contenedores 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 ^[31] presentó un algoritmo que genera una solución con un máximo de contenedores. ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))}$

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

Tabla comparativa

Algoritmos exactos

Martello y Toth ^[34] desarrollaron un algoritmo exacto para el problema de empaquetamiento de bins unidimensional, llamado MTP. Una alternativa más rápida es el algoritmo de compleción de bins propuesto por Korf en 2002 ^[35] y posteriormente mejorado. ^[36]

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

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

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

Empaquetamiento con fragmentación

El empaquetamiento de contenedores con fragmentación o el empaquetamiento de contenedores de objetos fragmentables es una variante del problema del empaquetamiento de contenedores en el que se permite dividir los elementos en partes y colocar cada parte por separado en un contenedor diferente. Dividir los elementos 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, ya que algunas de las variables de optimización se vuelven continuas. Por otro lado, dividir los elementos puede ser costoso. El problema fue introducido por primera vez por Mandal, Chakrabary y Ghose. ^[38]

Variantes

El problema tiene dos variantes principales.

1. En la primera variante, denominada empaquetamiento de contenedores con fragmentación creciente de tamaño ( BP-SIF ), cada elemento puede fragmentarse; se agregan unidades de sobrecarga al tamaño de cada fragmento.
2. En la segunda variante, denominada empaquetamiento de contenedores 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 ^[38] demostraron que BP-SPF es NP-duro .

Menakerman y Rom ^[39] demostraron que tanto BP-SIF como BP-SPF son fuertemente NP-hard . A pesar de la dureza, presentan varios algoritmos e investigan su desempeño. Sus algoritmos utilizan algoritmos clásicos para empaquetamiento de bins, como next-fit y first-fit decreciente , como base para sus algoritmos.

Bertazzi, Golden y Wang ^[40] introdujeron una variante de BP-SIF con regla de división: se permite dividir un elemento de una sola manera según su tamaño. Esto es útil para el problema de enrutamiento 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 ^[41] 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 ^[42] introdujo una variante de BP-SPF en la que algunos elementos están en conflicto y está prohibido agrupar fragmentos de elementos en conflicto en el mismo contenedor. Demostró que esta variante también es NP-hard.

Cassazza y Ceselli ^[43] introdujeron una variante sin costo ni sobrecarga, y el número de contenedores es fijo. Sin embargo, el número de fragmentaciones debería minimizarse. Presentan algoritmos de programación matemática para soluciones exactas y aproximadas.

Problemas relacionados

El problema de la mochila fraccionaria con penalizaciones fue introducido por Malaguti, Monaci, Paronuzzi y Pferschy. ^[44] Desarrollaron un FPTAS y un programa dinámico para el problema, y ​​mostraron un extenso estudio computacional comparando el desempeño de sus modelos. Véase también: Programación de tareas fraccionarias .

Rendimiento con tamaños de elementos divisibles

Un caso especial importante de empaquetamiento de contenedores es que los tamaños de los elementos forman una secuencia divisible (también llamada factorizada ). Un caso especial de tamaños de elementos divisibles ocurre en la asignación de memoria en sistemas informáticos, donde los tamaños de los elementos son todos potencias de 2. Si los tamaños de los elementos son divisibles, entonces algunos de los algoritmos heurísticos para el empaquetamiento de contenedores encuentran una solución óptima. ^[45]

Restricciones de cardinalidad en los bins

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

• Krause, Shen y Schwetman ^[46] presentan este problema como una variante de la programación óptima de trabajos : 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 solo contenedor. El objetivo es utilizar la menor cantidad posible de contenedores (=unidades de tiempo), al tiempo que se garantiza que en cada contenedor se ejecuten como máximo k trabajos. Presentan varios algoritmos heurísticos que encuentran una solución con como máximo contenedores. ${\displaystyle 2\mathrm {OPT} }$
• Kellerer y Pferschy ^[47] presentan un algoritmo con tiempo de ejecución , que encuentra una solución con un máximo de contenedores. Su algoritmo realiza una búsqueda binaria de OPT. Para cada valor buscado m , intenta empaquetar los elementos en 3 m /2 contenedores. ${\displaystyle O(n^{2}\log {n})}$ ${\displaystyle \left\lceil {\frac {3}{2}}\mathrm {OPT} \right\rceil }$

Funciones no aditivas

Hay varias formas de ampliar el modelo de bin-packing a funciones de carga y costos más generales:

• Anily, Bramel y Simchi-Levi ^[48] estudian un contexto en el que el costo de un contenedor es una función cóncava del número de elementos en el contenedor. El objetivo es minimizar el costo total en lugar del número de contenedores. Demuestran que el empaquetamiento de contenedores con ajuste siguiente alcanza una relación de aproximación absoluta al peor de los casos de como máximo 7/4, y una relación asintótica al peor de los casos de 1,691 para cualquier función de costo cóncava y monótona.
• Cohen, Keller, Mirrokni y Zadimoghaddam ^[49] estudian un entorno en el que el tamaño de los elementos no se conoce de antemano, sino que 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 empaquetamiento de contenedores con restricciones de azar: la probabilidad de que la suma de tamaños en cada contenedor sea como máximo B debe ser al menos p , donde p es una constante fija (el empaquetamiento de contenedores estándar corresponde a p = 1). Muestran que, bajo supuestos suaves, este problema es equivalente a un problema de empaquetamiento de contenedores submodular , en el que la "carga" en cada contenedor no es igual a la suma de elementos, sino a una determinada función submodular de esta.

Problemas relacionados

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

En cambio, en el problema de partición de números multidireccional , el número de bins es fijo y su tamaño se puede ampliar. El objetivo es encontrar una partición en la que los tamaños de los bins sean lo más parecidos posible (en la variante denominada problema de programación de multiprocesadores o problema de mínima capacidad de procesamiento , el objetivo es específicamente minimizar el tamaño del bin más grande).

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

En el problema de empaquetamiento de contenedores de recursos máximos , ^[51] el objetivo es maximizar el número de contenedores utilizados, de modo que, para algún orden 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 elementos colocados en los contenedores, de modo que ningún elemento restante quepa en un contenedor vacío.

En el problema de cubrimiento de contenedores , el tamaño del contenedor está limitado desde abajo : el objetivo es maximizar la cantidad 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 ítems ), los ítems representan tareas y hay distintas 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, cada persona corresponde a un contenedor). En este problema también se utilizan muchas técnicas del empaquetamiento de contenedores. ^[52]

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 del embalaje egoísta , cada artículo es un jugador que quiere minimizar su coste. ^[53]

Existe también una variante del empaquetamiento de contenedores en la que el coste que debe minimizarse no es el número de contenedores, sino más bien una determinada función cóncava del número de artículos en cada contenedor. ^[48]

Otras variantes son el embalaje bin bidimensional, ^[54] el embalaje bin tridimensional , ^[55] el embalaje bin con entrega , ^[56]

Recursos

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

Referencias

1. Martello, Silvano; Toth, Paolo (1990), "Problema de empaquetado de 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). "Bin-Packing". 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, David Mix (2006). «Bin Packing». 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, consultado el 8 de agosto de 2021
5. "DHCPv6-PD - Primeros pasos" . Consultado el 12 de junio de 2024 .
6. Lewis, R. (2009), "Un método de escalada de propósito general para problemas de agrupamiento mínimo independiente del orden: un estudio de caso sobre coloración de gráficos y empaquetamiento de bins" (PDF) , Computers and Operations Research , 36 (7): 2295–2310, doi :10.1016/j.cor.2008.09.004, S2CID  1577334
7. Sindelar, Michael; Sitaraman, Ramesh ; Shenoy, Prashant (2011), "Algoritmos que reconocen el uso compartido para la colocación de máquinas virtuales" (PDF) , Actas del 23.º Simposio de la ACM sobre paralelismo en algoritmos y arquitecturas (SPAA), San José, California, junio de 2011 : 367–378
8. Garey, M. R. ; Johnson, D. S. (1979). Victor Klee (ed.). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . Una serie de libros sobre las ciencias matemáticas. San Francisco, California: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5.Sr. 0519066  .
9. Martello y Toth 1990, pag. 221
10. Vazirani, Vijay V. (14 de marzo de 2013). Algoritmos de aproximación . Springer Berlin Heidelberg. pág. 74. ISBN 978-3662045657.
11. Johnson, David S (1973). "Algoritmos de empaquetamiento de contenedores casi óptimos" (PDF) . Instituto Tecnológico de Massachusetts .
12. Gonzalez, Teofilo F. (23 de mayo de 2018). Manual de algoritmos de aproximación y metaheurísticas. Volumen 2 Aplicaciones contemporáneas y emergentes . Taylor & Francis Incorporated. ISBN 9781498770156.
13. 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) . 20 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 538–549. doi : 10.4230/LIPIcs.STACS.2013.538 .
14. György, Dósa; Sgall, Jirí (2014). "Análisis óptimo del empaquetamiento de bins de mejor ajuste". Autómatas, lenguajes y programación . Apuntes de clase en 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 )
15. Yao, Andrew Chi-Chih (abril de 1980). "Nuevos algoritmos para el empaquetamiento de contenedores". Revista de la ACM . 27 (2): 207–227. doi : 10.1145/322186.322187 . S2CID  7903339.
16. 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.
17. Donna J, Brown (1979). "Un límite inferior para algoritmos de empaquetamiento de contenedores unidimensionales en línea" (PDF) . Informe técnico . Archivado (PDF) del original el 17 de marzo de 2022.
18. Liang, Frank M. (1980). "Un límite inferior para el empaquetamiento de contenedores en línea". Information Processing Letters . 10 (2): 76–79. doi :10.1016/S0020-0190(80)90077-0.
19. van Vliet, André (1992). "Un límite inferior mejorado para algoritmos de empaquetamiento de contenedores en línea". Information Processing Letters . 43 (5): 277–284. doi :10.1016/0020-0190(92)90223-I.
20. 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 .
21. 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 .
22. 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.
23. Dósa, György (2007). "El límite estricto del algoritmo de empaquetamiento de bins decreciente de primer ajuste es FFD(I) ≤ 11/9\mathrm{OPT}(I) + 6/9". Combinatoria, algoritmos, metodologías probabilísticas y experimentales. ESCAPE . doi :10.1007/978-3-540-74450-4_1.
24. Baker, BS; Coffman, Jr., EG (1 de junio de 1981). "Un límite asintótico ajustado para el empaquetamiento de bins decreciente en el siguiente ajuste". Revista SIAM sobre 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)
25. 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. S2CID  50663185.
26. 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.
27. Johnson, David S; Garey, Michael R (octubre de 1985). "Un teorema 7160 para empaquetamiento de bins". Journal of Complexity . 1 (1): 65–106. doi : 10.1016/0885-064X(85)90022-6 .
28. 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 empaquetamiento de bins MFFD". Acta Mathematicae Applicatae Sinica . 11 (3): 318–330. doi :10.1007/BF02011198. S2CID  118263129.
29. Fernandez de la Vega, W.; Lueker, GS (1981). "El empaquetamiento de bins puede resolverse dentro de 1 + ε en tiempo lineal". Combinatorica . 1 (4): 349–355. doi :10.1007/BF02579456. ISSN  1439-6912. S2CID  10519631.
30. Claire Mathieu. "Algoritmos de aproximación, parte I, semana 3: empaquetamiento de contenedores". Coursera . Archivado desde el original el 15 de julio de 2021.
31. Rothvoß, T. (1 de octubre de 2013). "Aproximación del empaquetamiento de bins dentro de bins O(log OPT · Log Log OPT)". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . págs. 20–29. arXiv : 1301.4010 . doi :10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7.S2CID15905063  .​
32. Hoberg, Rebecca; Rothvoss, Thomas (1 de enero de 2017), "Una brecha de integralidad aditiva logarítmica para empaquetamiento de bins", Actas del Simposio anual ACM-SIAM de 2017 sobre algoritmos discretos , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 2616–2625, arXiv : 1503.08796 , doi : 10.1137/1.9781611974782.172 , ISBN 978-1-61197-478-2, S2CID1647463 ​
33. Karmarkar, Narendra; Karp, Richard M. (noviembre de 1982). "Un esquema de aproximación eficiente para el problema de empaquetamiento de bins unidimensional". 23.° Simposio Anual sobre Fundamentos de la Ciencia de la Computación (SFCS 1982) : 312–320. doi :10.1109/SFCS.1982.61. S2CID  18583908.
34. Martello y Toth 1990, págs. 237-240.
35. Korf, Richard E. (2002). Un nuevo algoritmo para el empaquetamiento óptimo de contenedores (PDF) . AAAI-02.
36. RE Korf (2003), Un algoritmo mejorado para el empaquetamiento óptimo de contenedores . Actas de la Conferencia conjunta internacional sobre inteligencia artificial (págs. 1252-1258).
37. Schreiber, Ethan L.; Korf, Richard E. (2013), "Completado de bin mejorado para empaquetamiento de bin óptimo y 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
38. Mandal, CA; Chakrabarti, PP; Ghose, S. (1998-06-01). "Complejidad del empaquetamiento de contenedores de objetos fragmentables y una aplicación". Computers & Mathematics with Applications . 35 (11): 91–97. doi :10.1016/S0898-1221(98)00087-X. ISSN  0898-1221.
39. Nir Menakerman y Raphael Rom "Bin Packing with Item Fragmentation". Algorithms and Data Structures, 7º Taller Internacional, WADS 2001, Providence, RI, EE.UU., 8-10 de agosto de 2001, Actas.
40. Bertazzi, Luca; Golden, Bruce; Wang, Xingyin (31 de mayo de 2019). "El problema del empaquetamiento de contenedores con fragmentación de elementos: un análisis del peor caso". Matemáticas aplicadas discretas . Reunión GO X, Rigi Kaltbad (Suiza), 10-14 de julio de 2016. 261 : 63–77. doi : 10.1016/j.dam.2018.08.023 . ISSN  0166-218X. S2CID  125361557.
41. Shachnai, Hadas; Tamir, Tami; Yehezkely, Omer (2006). "Esquemas de aproximación para empaquetamiento con fragmentación de ítems". En Erlebach, Thomas; Persinao, Giuseppe (eds.). Aproximación y algoritmos en línea . Apuntes de clase en informática. Vol. 3879. Berlín, Heidelberg: Springer. págs. 334–347. doi :10.1007/11671411_26. ISBN . 978-3-540-32208-5.
42. Ekici, Ali (1 de febrero de 2021). "Problema de empaquetamiento de contenedores con conflictos y fragmentación de elementos". Computers & Operations Research . 126 : 105113. doi :10.1016/j.cor.2020.105113. ISSN  0305-0548. S2CID  225002556.
43. Casazza, Marco; Ceselli, Alberto (1 de junio de 2014). "Algoritmos de programación matemática para problemas de empaquetamiento de contenedores con fragmentación de ítems". Computers & Operations Research . 46 : 1–11. doi :10.1016/j.cor.2013.12.008. ISSN  0305-0548.
44. Malaguti, Enrico; Monaci, Michele; Paronuzzi, Paolo; Pferschy, Ulrich (16 de marzo de 2019). "Optimización de enteros con valores fraccionarios penalizados: el caso Knapsack". 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.
45. Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Empaquetado de contenedores con tamaños de elementos divisibles". Journal of Complexity . 3 (4): 406–428. doi :10.1016/0885-064X(87)90009-4. ISSN  0885-064X.
46. Krause, KL; Shen, VY; Schwetman, HD (1975-10-01). "Análisis de varios algoritmos de planificación de tareas para un modelo de sistemas informáticos multiprogramados". Revista de la ACM . 22 (4): 522–550. doi : 10.1145/321906.321917 . ISSN  0004-5411. S2CID  10214857.
47. Kellerer, H.; Pferschy, U. (1999-01-01). "Problemas de bin-packing con restricciones de cardinalidad". Annals of Operations Research . 92 : 335–348. doi :10.1023/A:1018947117526. ISSN  1572-9338. S2CID  28963291.
48. Anily, Shoshana; Bramel, Julien; Simchi-Levi, David (1994-04-01). "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.
49. Cohen, Maxime C.; Keller, Philipp W.; Mirrokni, Vahab; Zadimoghaddam, Morteza (1 de julio de 2019). "Sobrecompromiso en servicios en la nube: empaquetado de contenedores con restricciones aleatorias". Management Science . 65 (7): 3255–3271. arXiv : 1705.09335 . doi :10.1287/mnsc.2018.3091. ISSN  0025-1909. S2CID  159270392.
50. Chung, Yerim; Park, Myoung-Ju (1 de enero de 2015). "Notas sobre problemas de empaquetamiento inverso". Cartas de procesamiento de la información . 115 (1): 60–68. doi :10.1016/j.ipl.2014.09.005. ISSN  0020-0190.
51. Boyar, Joan ; 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 empaquetamiento máximo de contenedores de recursos". Ciencias de la Computación Teórica . 362 (1): 127–139. doi :10.1016/j.tcs.2006.06.001. ISSN  0304-3975.
52. Huang, Xin; Lu, Pinyan (10 de noviembre de 2020). "Un marco algorítmico para aproximar la asignación de tareas con la máxima participación". arXiv : 1907.04505 [cs.GT].
53. Ma, Ruixin; Dósa, György; Han, Xin; Ting, Hing-Fung; Ye, Deshi; Zhang, Yong (1 de agosto de 2013). "Una nota sobre un problema de empaquetamiento egoísta". Revista de optimización global . 56 (4): 1457–1462. doi :10.1007/s10898-012-9856-9. ISSN  0925-5001. S2CID  3082040.
54. Lodi A., Martello S., Monaci, M., Vigo, D. (2010) "Problemas de empaquetamiento de bins bidimensionales". En V.Th. Paschos (Ed.), Paradigms of Combinatorial Optimization , Wiley/ISTE, págs. 107–129
55. Optimización del embalaje tridimensional de contenedores mediante simulación
56. Benkő A., Dósa G., Tuza Z. (2010) "Empaquetado/cubrimiento de contenedores con entrega, resuelto con la evolución de algoritmos", Actas 2010 IEEE 5.ª Conferencia internacional sobre computación bioinspirada: teorías y aplicaciones, BIC-TA 2010 , art. n.º 5645312, págs. 298-302.