Problema de empaquetado en contenedores

El problema de empaquetado en contenedores^[1]​^[2]​^[3]​^[4]​ es una cuestión de optimización, en la que artículos de diferentes tamaños deben distribuirse en un conjunto de contenedores, cada uno con una capacidad fija, de forma que se minimice el número de contenedores utilizados. Este problema tiene diversas aplicaciones, como el llenado de contenedores, la carga de camiones con restricciones de capacidad de peso, la creación de archivos de copia de seguridad en medios, la división de un prefijo de red en múltiples subredes^[5]​ y la asignación de tecnologías en el diseño de matrices de puertas programables en campo (FPGA) en circuitos integrados.

Computacionalmente, el problema es NP-difícil, y el correspondiente problema de decisión, que dilucida si los elementos caben 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 First-Fit proporciona una solución rápida, pero a menudo no óptima, que implica colocar cada elemento en el primer contenedor en el que quepa. Requiere un tiempo Θ(n log n), 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 variaciones de este problema, como el empaquetado 2D, el empaquetado lineal, el empaquetado por peso, el empaquetado por costo y otros. El problema del empaquetado en contenedores también puede considerarse un caso especial del problema de corte de valores. Cuando el número de contenedores se limita a uno y cada elemento se caracteriza por un volumen y un valor, el problema de maximizar el valor de los elementos que caben en el contenedor se conoce como problema de la mochila.

Una variante del empaquetado en contenedores que se da en la práctica es cuando los elementos pueden compartir espacio al empaquetarse en un contenedor. Específicamente, un conjunto de elementos podría ocupar menos espacio al empaquetarse juntos que la suma de sus tamaños individuales. Esta variante se conoce como empaquetado de máquinas virtuales (MV),^[7]​ ya que cuando se empaquetan máquinas virtuales (MV) en un servidor, su requerimiento de memoria total podría disminuir debido a que hay páginas compartidas por las MV que solo necesitan almacenarse una vez. Si los elementos pueden compartir espacio de forma arbitraria, el problema del empaquetado en contenedores es difícil de aproximar. Sin embargo, si el espacio compartido se jerarquiza, como ocurre con el uso compartido de memoria en máquinas virtuales, el problema del empaquetado en contenedores se puede aproximar eficientemente.

Otra variante del empaquetado en contenedores de interés en la práctica es el llamado empaquetado en contenedores en línea. En este caso, se supone que los artículos de diferente volumen llegan secuencialmente, y quien toma la decisión debe decidir si selecciona y empaqueta el artículo observado actualmente o lo deja pasar. Cada decisión no se puede revertir. Por el contrario, el empaquetado en contenedores fuera de línea permite reorganizar los artículos con la esperanza de lograr un mejor empaquetado cuando lleguen artículos adicionales. Esto, por supuesto, requiere almacenamiento adicional para depositar temporalmente los artículos que se reorganizarán más adelante.

En Computers and Intractability: A Guide to the Theory of NP-Completeness,^[8]​^: 226 Garey y Johnson enumeran el problema de empaquetado en contenedores bajo la referencia [SR1]. Definen su variante de decisión de la siguiente manera:

Ejemplo: Conjunto finito ${\displaystyle I}$ de artículos, un tamaño ${\displaystyle s(i)\in \mathbb {Z} ^{+}}$ para cada ${\displaystyle i\in I}$, una capacidad de contenedor entera positiva ${\displaystyle B}$ y un entero positivo ${\displaystyle K}$.

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

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

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

Minimizar ${\displaystyle K=\sum _{j=1}^{n}y_{j}}$
sujeto a que	${\displaystyle K\geq 1,}$
	${\displaystyle \sum _{i\in I}s(i)x_{ij}\leq By_{j},}$	${\displaystyle \forall j\in \{1,\ldots ,n\}}$
	${\displaystyle \sum _{j=1}^{n}x_{ij}=1,}$	${\displaystyle \forall i\in I}$
	${\displaystyle y_{j}\in \{0,1\},}$	${\displaystyle \forall j\in \{1,\ldots ,n\}}$
	${\displaystyle x_{ij}\in \{0,1\},}$	${\displaystyle \forall i\in I\,\forall j\in \{1,\ldots ,n\}}$

donde ${\displaystyle y_{j}=1}$ si se utiliza el contenedor ${\displaystyle j}$ y ${\displaystyle x_{ij}=1}$ si el elemento ${\displaystyle i}$ se coloca en el contenedor ${\displaystyle j}$.^[9]​

El problema del empaquetado en contenedores es difícilmente NP-completo. Esto se puede demostrar reduciendo el problema de la 3-partición difícilmente NP-completo al empaquetado en contenedores.^[8]​

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

Por otro lado, el empaquetado en contenedores se puede resolver en tiempo pseudopolinómico para cualquier número fijo de contenedores K, y en tiempo polinomial para cualquier capacidad fija de los contenedores B.^[8]​

Para medir el rendimiento de un algoritmo de aproximación, en la literatura sobre el tema se consideran dos ratios de aproximación. Para una lista dada de elementos ${\displaystyle L}$, el número ${\displaystyle A(L)}$ denota el número en contenedores utilizados cuando el algoritmo ${\displaystyle A}$ se aplica a la lista ${\displaystyle L}$, mientras que ${\displaystyle \mathrm {OPT} (L)}$ denota el número óptimo para esta lista. El ratio de rendimiento absoluto en el peor caso ${\displaystyle R_{A}}$ para un algoritmo ${\displaystyle A}$ se define como:

${\displaystyle R_{A}\equiv \inf\{r\geq 1:A(L)/\mathrm {OPT} (L)\leq r{\text{ para todas las listas }}L\}.}$

Por otro lado, el ratio asintótico en el peor caso ${\displaystyle R_{A}^{\infty }}$ se define como:

${\displaystyle R_{A}^{\infty }\equiv \inf\{r\geq 1:\exists N>0,A(L)/\mathrm {OPT} (L)\leq r{\text{ para todas las listas }}L{\text{ con }}\mathrm {OPT} (L)\geq N\}.}$

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

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

Además, se pueden restringir las listas a aquellas cuyos elementos tengan un tamaño máximo de ${\displaystyle \alpha }$. Para estas listas, los índices de rendimiento de tamaño acotado se denotan como ${\displaystyle R_{A}({\text{tamaño}}\leq \alpha )}$ y ${\displaystyle R_{A}^{\infty }({\text{tamaño}}\leq \alpha )}$.

Los algoritmos de aproximación para el empaquetado en 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 a 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 de elementos dada, por ejemplo, ordenándolos por tamaño. Estos algoritmos ya no son aplicables a la variante en línea de este problema. Sin embargo, ofrecen una garantía de aproximación mejorada, manteniendo la ventaja de su baja complejidad temporal. Una subcategoría de las 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 ${\displaystyle (1+\varepsilon )\mathrm {OPT} (L)+C}$ para alguna constante que puede depender de ${\displaystyle 1/\varepsilon }$. Para un valor arbitrario de ${\displaystyle \mathrm {OPT} (L)}$, estos algoritmos se aproximan arbitrariamente a ${\displaystyle \mathrm {OPT} (L)}$. Sin embargo, esto conlleva una complejidad temporal (drásticamente) mayor en comparación con los enfoques heurísticos.

En la versión en línea del problema de empaquetado en contenedores, los artículos llegan uno tras otro y la decisión (irreversible) de dónde colocar un artículo debe tomarse antes de conocer 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 en contenedores en su tesis doctoral.^[11]​

Existen muchos algoritmos simples que utilizan el siguiente esquema general:

• Para cada elemento de la lista de entrada:
  1. Si el elemento cabe en uno de los contenedores abiertos, colóquelo en uno de ellos.
  2. En caso contrario, abra un nuevo contenedor y coloque el nuevo elemento en él

Los algoritmos difieren en el criterio con el que eligen el contenedor abierto para el nuevo elemento en el paso 1 (consúltense las páginas enlazadas para obtener más información):

• Next Fit (NF) siempre mantiene un único contenedor abierto. Cuando el nuevo elemento no cabe en él, cierra el contenedor actual y abre uno nuevo. Su ventaja es que es un algoritmo de espacio acotado, ya que solo necesita mantener un único contenedor abierto en memoria. Su desventaja es que su razón de aproximación asintótica es 2. En particular, ${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$, y para cada ${\displaystyle N\in \mathbb {N} }$ existe una lista L tal que ${\displaystyle \mathrm {OPT} (L)=N}$ y ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$.^[11]​ Su razón de aproximación asintótica se puede mejorar ligeramente según los tamaños de los elementos: ${\displaystyle R_{NF}^{\infty }({\text{tamaño}}\leq \alpha )\leq 2}$ para todos los ${\displaystyle \alpha \geq 1/2}$ y ${\displaystyle R_{NF}^{\infty }({\text{tamaño}}\leq \alpha )\leq 1/(1-\alpha )}$ para todos los ${\displaystyle \alpha \leq 1/2}$. Para cada algoritmo (A que sea un algoritmo AnyFit, se cumple ${\displaystyle R_{A}^{\infty }({\text{tamaño}}\leq \alpha )\leq R_{NF}^{\infty }({\text{tamaño}}\leq \alpha )}$.
• Next-k-Fit (NkF) es una variante de Next-Fit, pero en lugar de mantener solo un intervalo abierto, el algoritmo mantiene abiertos los últimos k intervalos y elige el primero en el que encaja el elemento. Por lo tanto, se denomina algoritmo de espacio k-acotado.^[12]​ Para ${\displaystyle k\geq 2}$, el método NkF ofrece resultados mejorados en comparación con los resultados del método NF. Sin embargo, aumentar k a valores constantes mayores que 2 no mejora aún más el algoritmo en su peor caso. Si el algoritmo A es un algoritmo AlmostAnyFit (de "CasiCualquierAjuste) y ${\displaystyle m=\lfloor 1/\alpha \rfloor \geq 2}$, entonces ${\displaystyle R_{A}^{\infty }({\text{tamaño}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{tamaño}}\leq \alpha )=1+1/m}$.^[11]​
• First-Fit (FF) mantiene todos los contenedores abiertos, en el orden en que se abrieron. Intenta colocar cada elemento nuevo en el primer contenedor en el que encaja. Su razón de aproximación es ${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$, y existe una familia de listas de entrada L para las cuales ${\displaystyle FF(L)}$ coincide con este límite.^[13]​
• Best-Fit (BF) también mantiene todos los contenedores abiertos, en el orden en que se abrieron. Pero intenta colocar cada nuevo elemento en el contenedor en el que encaje que esté más cargado. Su razón de aproximación es ${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$, y existe una familia de listas de entrada L para las cuales ${\displaystyle BF(L)}$ coincide con este límite.^[14]​
• Worst-Fit (WF) (peor llenado) intenta colocar cada nuevo elemento en el contenedor menos lleno. Puede comportarse tan mal como el Next-Fit, y lo hará en la lista de peores casos para ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$. Además, cumple que ${\displaystyle R_{WF}^{\infty }({\text{tamaño}}\leq \alpha )=R_{NF}^{\infty }({\text{tamaño}}\leq \alpha )}$. Dado que el WF es un algoritmo AnyFit, existe un algoritmo AnyFit tal que ${\displaystyle R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )}$.^[11]​
• Almost Worst-Fit (AWF) (casi peor llenado) intenta colocar cada elemento nuevo dentro del segundo contenedor abierto más vacío (o el contenedor más vacío si hay dos). Si no encaja, prueba con el más vacío. Su razón asintótica de peor caso es ${\displaystyle {\tfrac {17}{10}}}$.^[11]​

Para generalizar estos resultados, Johnson introdujo dos clases de heurísticas en línea denominadas algoritmos de ajuste aleatorio y algoritmos de ajuste casi aleatorio:^[4]​^: 470

• En un algoritmo AnyFit (AF), si los contenedores actuales no vacíos son B₁,..., B_j, el elemento actual no se empaquetará en B_j+1 a menos que no encaje en ninguno de los siguientes B₁,..., B_j. Los algoritmos FF, WF, BF y AWF satisfacen esta condición. Johnson demostró que, para cualquier algoritmo A AnyFit 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 con la carga más pequeña, 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 cumplen esta condición, pero WF no. Johnson demostró que, para cualquier algoritmo A AAF y cualquier α:

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

Se pueden 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 elementos de diferentes rangos de tamaño (consulte las páginas enlazadas para obtener más información):

• Refined-first-fit bin packing (RFF) divide los tamaños de los elementos en cuatro rangos: ${\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]}$ y ${\displaystyle \left(0,{\frac {1}{3}}\right]}$. De igual forma, los contenedores se categorizan en cuatro clases. El siguiente elemento, ${\displaystyle i\in L}$, se asigna primero a su clase correspondiente. Dentro de esa clase, se asigna a un contenedor mediante first-fit. Cabe destacar que este algoritmo no es un algoritmo de ajuste aleatorio, ya que puede abrir un nuevo contenedor aunque el elemento actual encaje dentro de uno abierto. Este algoritmo fue presentado inicialmente por Andrew Chi-Chih Yao,^[15]​ quien demostró que tiene una garantía de aproximación de ${\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}$ y presentó una familia de listas ${\displaystyle L_{k}}$ con ${\displaystyle RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3}$ para ${\displaystyle \mathrm {OPT} (L)=6k+1}$.
• Harmonic-k divide el intervalo de tamaños ${\displaystyle (0,1]}$ basándose en una progresión armónica (matemática) en ${\displaystyle k-1}$ fragmentos ${\displaystyle I_{j}:=\left({\frac {1}{j+1}},{\frac {1}{j}}\right]}$ para ${\displaystyle 1\leq j<k}$ y ${\displaystyle I_{k}:=\left(0,{\frac {1}{k}}\right]}$ tales que ${\displaystyle \bigcup _{j=1}^{k}I_{j}=(0,1]}$. Este algoritmo fue descrito por primera vez por Lee y Lee.^[16]​ Tiene una complejidad temporal de ${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$ y en cada paso, hay como máximo k contenedores abiertos que pueden usarse potencialmente para colocar elementos; es decir, es un algoritmo de espacio acotado por k. Para ${\displaystyle k\rightarrow \infty }$, su razón de aproximación satisface ${\displaystyle R_{Hk}^{\infty }\approx 1.6910}$ y es asintóticamente ajustado.
• Refined-harmonic combina ideas de Harmonic-k con ideas de Refined-First-Fit. Para ello, coloca los elementos mayores que ${\displaystyle {\tfrac {1}{3}}}$ de forma similar a como se hace en el ajuste refinado, mientras que los menores se colocan utilizando Harmonic-k. La intuición de esta estrategia es reducir el gran desperdicio de contenedores que contienen piezas apenas mayores que ${\displaystyle {\tfrac {1}{2}}}$. Este algoritmo fue descrito por primera vez por Lee y Lee,^[16]​ quienes emostraron que para ${\displaystyle k=20}$ se cumple ${\displaystyle R_{RH}^{\infty }\leq 373/228}$.

Yao^[15]​ demostró en 1980 que no puede existir ningún algoritmo en línea con una razón competitiva asintótica menor que ${\displaystyle {\tfrac {3}{2}}}$. Brown^[17]​ y Liang^[18]​ mejoraron este límite a ${\displaystyle 1.53635}$. Posteriormente, Vliet lo mejoró a ${\displaystyle 1.54014}$.^[19]​ En 2012, Békési y Galambos^[20]​ volvieron a mejorar este límite inferior a${\displaystyle {\tfrac {248}{161}}\approx 1.54037}$.

Algoritmo	Garantía de aproximación	Lista de peores casos ${\displaystyle L}$	Complejidad temporal
Next Fit (NF)	${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$[11]​	${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$[11]​	${\displaystyle {\mathcal {O}}(|L|)}$
First-fit (FF)	${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor }$[13]​	${\displaystyle FF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor }$[13]​	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[11]​
Best-fit (BF)	${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor }$[14]​	${\displaystyle BF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor }$[14]​	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[11]​
Worst-Fit (WF)	${\displaystyle WF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$[11]​	${\displaystyle WF(L)=2\cdot \mathrm {OPT} (L)-2}$[11]​	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[11]​
Almost-Worst-Fit (AWF)	${\displaystyle R_{AWF}^{\infty }\leq 17/10}$[11]​	${\displaystyle R_{AWF}^{\infty }=17/10}$[11]​	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[11]​
Refined-First-Fit (RFF)	${\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}$[15]​	${\displaystyle RFF(L)=(5/3)\mathrm {OPT} (L)+1/3}$ (para ${\displaystyle \mathrm {OPT} (L)=6k+1}$)[15]​	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[15]​
Harmonic-k (Hk)	${\displaystyle R_{Hk}^{\infty }\leq 1.69103}$ para ${\displaystyle k\rightarrow \infty }$[16]​	${\displaystyle R_{Hk}^{\infty }\geq 1.69103}$[16]​	${\displaystyle {\mathcal {O}}(|L|\log(|L|)}$[16]​
Refined Harmonic (RH)	${\displaystyle R_{RH}^{\infty }\leq 373/228\approx 1.63597}$[16]​		${\displaystyle {\mathcal {O}}(|L|)}$[16]​
Modified Harmonic (MH)	${\displaystyle R_{MH}^{\infty }\leq 538/33\approx 1.61562}$[21]​
Modified Harmonic 2 (MH2)	${\displaystyle R_{MH2}^{\infty }\leq 239091/148304\approx 1.61217}$[21]​
Harmonic + 1 (H+1)		${\displaystyle R_{H+1}^{\infty }\geq 1.59217}$[22]​
Harmonic ++ (H++)	${\displaystyle R_{H++}^{\infty }\leq 1.58889}$[22]​	${\displaystyle R_{H++}^{\infty }\geq 1.58333}$[22]​

En la versión fuera de línea del empaquetado en contenedores, el algoritmo puede ver todos los elementos antes de comenzar a colocarlos en contenedores. Esto permite obtener mejores razones de aproximación.

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;
• Ejecutar un algoritmo en línea sobre la lista ordenada.

Johnson^[11]​ demostró que cualquier esquema A del tipo AnyFit que se ejecuta en una lista ordenada por tamaño descendente tiene una razó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 (consúltense las páginas enlazadas para obtener más información):

• First-fit-decreasing (FFD) ordena los elementos por tamaño descendente y luego utiliza el procedimiento First-Fit. Su razón de aproximación es ${\displaystyle FFD(I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}}$, lo cual es ajustado.^[23]​
• Next-fit-decreasing (NFD) ordena los elementos por tamaño descendente y luego utiliza Next-Fit. Su razón aproximada es ligeramente inferior a 1,7 en el peor de los casos.^[24]​ También se ha analizado probabilísticamente.^[25]​ Next-Fit empaqueta una lista y su inverso en el mismo número de contenedores. Por lo tanto, Next-Fit-Increasing tiene el mismo rendimiento que Next-Fit-Decreasing.^[26]​
• Modified first-fit-decreasing (MFFD),^[27]​ mejora el procedimiento FFD para elementos mayores de medio contenedor al clasificarlos por tamaño en cuatro clases: grande, mediano, pequeño y diminuto, correspondientes a elementos con 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 ${\displaystyle MFFD(I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1}$.^[28]​

Fernández de la Vega y Lueker^[29]​ presentaron un PTAS para el empaquetado en contenedores. Para cada ${\displaystyle \varepsilon >0}$, su algoritmo encuentra una solución con un tamaño máximo de ${\displaystyle (1+\varepsilon )\mathrm {OPT} +1}$ y se ejecuta en tiempo ${\displaystyle {\mathcal {O}}(n\log(1/\varepsilon ))+{\mathcal {O}}_{\varepsilon }(1)}$, donde ${\displaystyle {\mathcal {O}}_{\varepsilon }(1)}$ denota una función que solo depende de ${\displaystyle 1/\varepsilon }$. 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 programación lineal de configuración.^[30]​

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

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

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

Algoritmo	Garantía aproximada	Peor caso posible
First-fit-decreasing (FFD)	${\displaystyle \mathrm {FFD} (I)\leq {\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}}$[23]​	${\displaystyle \mathrm {FFD} (I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}}$[23]​
Modified-first-fit-decreasing (MFFD)	${\displaystyle \mathrm {MFFD} (I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1}$[28]​	${\displaystyle R_{\mathrm {MFFD} }^{\infty }\geq {\frac {71}{60}}}$[27]​
Karmarkar y Karp	${\displaystyle \mathrm {KK} (I)\leq \mathrm {OPT} (I)+O(\log ^{2}{\mathrm {OPT} (I)})}$[33]​
Rothvoss	${\displaystyle \mathrm {HB} (I)\leq \mathrm {OPT} (I)+O(\log {\mathrm {OPT} (I)}\log \log {\mathrm {OPT} (I)})}$[31]​
Hoberg y Rothvoss	${\displaystyle \mathrm {HB} (I)\leq \mathrm {OPT} (I)+O(\log {\mathrm {OPT} (I)})}$[32]​

Martello y Toth^[34]​ desarrollaron un algoritmo exacto para el problema de empaquetado en contenedores unidimensional, llamado MTP. Una alternativa más rápida es el algoritmo de completamiento en contenedores propuesto por Richard E. Korf en 2002.^[35]​ y posteriormente mejorado).^[36]​

Schreiber y Korf presentaron una mejora adicional en 2013. El nuevo algoritmo^[37]​ de Completamiento en contenedores Mejorado ha demostrado ser hasta cinco órdenes de magnitud más rápido que el Completamiento en contenedores en problemas no triviales con 100 elementos, y supera al algoritmo BCP (ramificación, corte y precio) de Belov y Scheithauer en problemas con menos de 20 contenedores como solución óptima. El mejor rendimiento del algoritmo depende de propiedades del problema, como el número de elementos, el número óptimo en contenedores, el espacio no utilizado en la solución óptima y la precisión del valor.

Un caso especial de empaquetado en contenedores se da cuando hay un pequeño número d de elementos de diferentes tamaños. Puede haber muchos elementos diferentes de cada tamaño. Este caso también se denomina empaquetado en contenedores de alta multiplicidad y admite algoritmos más eficientes que el problema general.

El empaquetado en contenedores con fragmentación o empaquetado en contenedores de objetos fragmentables es una variante del problema de empaquetado en contenedores que permite fragmentar elementos en partes y colocar cada parte por separado en un contenedor diferente. Dividir elementos en partes puede mejorar el rendimiento general, por ejemplo, minimizando el número total de contenedores. Además, el problema computacional de encontrar una programación óptima puede resultar más sencillo, ya que algunas de las variables de optimización se vuelven continuas. Por otro lado, separar elementos puede ser costoso. El problema fue introducido por primera vez por Mandal, Chakrabary y Ghose.^[38]​

El problema tiene dos variantes principales.

1. En la primera variante, denominada empaquetado en contenedores con fragmentación creciente de tamaño (BP-SIF), cada elemento puede fragmentarse, y se añaden unidades adicionales al tamaño de cada fragmento resultante. En la segunda variante, denominada empaquetado en contenedores con fragmentación que preserva el tamaño (BP-SPF), cada elemento tiene un tamaño y un coste; fragmentar un elemento aumenta su coste, pero no modifica su tamaño.

Mandal, Chakrabary y Ghose^[38]​ demostraron que BP-SPF es NP-difícil.

Menakerman y Rom^[39]​ demostraron que BP-SIF y BP-SPF son ambos totalmente NP-completos. A pesar de su complejidad, presentaron varios algoritmos e investigan su rendimiento. Sus programas utilizan algoritmos clásicos de empaquetado en contenedores, como next-fit y first-fit decreasing como base.

Bertazzi, Golden y Wang^[40]​ introdujeron una variante de BP-SIF con la regla de división ${\displaystyle 1-x}$: un elemento solo puede dividirse de una manera según su tamaño. Esto es útil para problemas de enrutamiento de vehículos, por ejemplo. En su artículo, proporcionan el límite de rendimiento en el peor caso posible de la variante.

Shachnai, Tamir y Yehezkeli^[41]​ desarrollaron esquemas de aproximación para BP-SIF y BP-SPF: un método 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 entran en conflicto y se prohíbe agrupar fragmentos de elementos en conflicto en la misma bandeja. Demostraron que esta variante también es NP-difícil.

Cassazza y Ceselli^[43]​ introdujeron una variante sin costo ni sobrecarga, con un número fijo de bandejas. Sin embargo, se debe minimizar el número de fragmentaciones. Presentan algoritmos de programación matemática para soluciones exactas y aproximadas.

El problema de la mochila fraccionario con penalizaciones fue introducido por Malaguti, Monaci, Paronuzzi y Pferschy.^[44]​ Desarrollaron un FPTAS y un sistema de programación dinámica para abordar el problema, y presentaron un extenso estudio computacional que compara el rendimiento de sus modelos. Véase también: programación de trabajos fraccionables.

Un caso especial importante de empaquetado en 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 se da 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, algunos de los algoritmos heurísticos para el empaquetado en contenedores encuentran una solución óptima.^[45]​

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

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

Existen varias maneras de extender el modelo de empaquetado de contenedores a funciones de costo y carga más generales:

• Anily, Bramel y Simchi-Levi (^[48]​) estudian un contexto donde el coste 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, no el número de contenedores. Demuestran que el procedimiento next-fit-increasing alcanza una razón de aproximación absoluta en el peor de los casos de como máximo 7/4, y una razón asintótica en el peor de los casos de 1,691 para cualquier función de coste cóncava y monótona.
• Cohen, Keller, Mirrokni y Zadimoghaddam (^[49]​) estudiaron un entorno donde el tamaño de los elementos no se conoce de antemano, pero es un variable aleatoria. Esto es particularmente común en entornos computación en la nube. Si bien existe un límite superior para la cantidad de recursos que necesita un usuario, la mayoría de los usuarios utilizan mucho menos que la capacidad. Por lo tanto, el administrador de la nube puede obtener una gran ventaja con un sobrecompromiso de memoria ligero. Esto induce una variante del empaquetado en contenedores con restricciones de azar: la probabilidad de que la suma de los tamaños en cada contenedor sea como máximo B debería ser al menos p, donde p es una constante fija (el empaquetado en contenedores estándar corresponde a p = 1). Demuestran que, bajo supuestos moderados, este problema es equivalente a un problema de empaquetado en contenedores submodular, 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 esta.

En el problema de empaquetado en contenedores, el tamaño de los contenedores es fijo y su número puede aumentarse (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 contenedores es fijo, pero su tamaño puede aumentarse. 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 denominada problema de programación de multiprocesadores o problema de hacer vano mínimo, el objetivo es minimizar el tamaño del contenedor más grande).

En el problema de empaquetado inverso de contenedores,^[50]​ tanto el número de contenedores como sus tamaños son fijos, pero el tamaño de los elementos puede modificarse. El objetivo es minimizar la perturbación del vector de tamaño de los elementos para que todos los elementos puedan empaquetarse en el número de contenedores prescrito.

En el problema de máximo empaquetado en contenedores de recursos,^[51]​ el objetivo es maximizar el número de contenedores utilizados, de modo que, para cierta ordenación de los contenedores, ningún elemento de un contenedor posterior quepa en uno 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 reparto en contenedores, el tamaño del contenedor está acotado desde abajo: el objetivo es maximizar el número de contenedores utilizados de modo que la ocupación total de cada contenedor alcance al menos un umbral determinado.

En el problema de asignación justa e indivisible de tareas (una variante de asignación justa de artículos), 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 total de dificultad (por lo tanto, cada persona corresponde a un contenedor). En este problema también se utilizan muchas técnicas del empaquetado en contenedores.^[52]​

En el problema 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 para obtener piezas de tamaños determinados.

En el problema del empaquetado egoísta en contenedores, cada artículo es un jugador que busca minimizar su costo.^[53]​

También existe una variante del empaquetado de contenedores en la que el costo que debe minimizarse no es el número de contenedores, sino una cierta función cóncava del número de artículos alojados en cada contenedor.^[48]​

Otras variantes son el empaquetado en contenedores bidimensional,^[54]​ el empaquetado en contenedores tridimensional,^[55]​ o el empaquetado en contenedores con entrega.^[56]​

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