Problema de embalaje de contenedores

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Problema matemático y computacional

El problema del embalaje en contenedores es un problema de optimización, en el que los artículos de diferentes tamaños deben empaquetarse en un número finito de contenedores o contenedores, cada uno de una capacidad fija dada, de manera que se minimice el número de contenedores utilizados. El problema tiene muchas aplicaciones, como el llenado de contenedores, la carga de camiones con limitaciones de capacidad de peso, la creación de copias de seguridad de archivos en medios y el mapeo tecnológico en el diseño de chips semiconductores FPGA.

Desde el punto de vista computacional, el problema es NP-difícil 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 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 consiste en 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 que se empaquetarán. El algoritmo se puede hacer mucho más efectivo clasificando 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. Se sabe, sin embargo, que siempre existe al menos un ordenamiento de elementos que permite el primer ajuste para producir una solución óptima.

Existen muchas variaciones de este problema, como empaquetamiento 2D, empaquetamiento lineal, empaquetamiento por peso, empaquetamiento por costo, etc. El problema del embalaje en contenedores 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 el 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 empacan juntos que la suma de sus tamaños individuales. Esta variante se conoce como empaquetado de VM, ya que cuando las máquinas virtuales (VM) se empaquetan en un servidor, su requisito de memoria total podría disminuir debido a las páginas compartidas por las VM que solo necesitan almacenarse una vez. Si los artículos pueden compartir espacio de forma arbitraria, el problema del embalaje en contenedores es difícil incluso de aproximarse. Sin embargo, si el espacio compartido se ajusta a una jerarquía, como es el caso de la memoria compartida en máquinas virtuales, el problema del empaquetamiento en contenedores se puede aproximar de manera eficiente.

Otra variante de bin packing de interés en la práctica es el llamado bin packing online. Aquí se supone que los artículos de diferente volumen llegan secuencialmente, y el tomador de decisiones tiene que decidir si selecciona y empaqueta el artículo actualmente observado, o si lo deja pasar. Cada decisión es sin revocación. 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, Garey y Johnson enumeran el problema del embalaje en contenedores bajo la referencia [SR1]. Definen su variante de decisión de la siguiente manera.

Instance: Finite set $I$ de artículos, tamaño ${displaystyle s(i)in mathbb {Z} ^{+}}$ para cada uno $iin I$ , una capacidad de entrada positiva $B$ , y un entero positivo $K$ .

Pregunta: ¿Hay una partición de $I$ en conjuntos ${displaystyle I_{1},dotsI_{K}}$ tal que la suma de los tamaños de los artículos en cada $I_{j}$ es $B$ o menos?

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

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

minimizar ${displaystyle K=sum _{j=1}^{n}y_{j}}$
sujeto a	${displaystyle Kgeq 1,}$
	${displaystyle sum _{iin I}s(i)x_{ij}leq By_{j},}$	$forall jin {1,ldotsn}$
	$sum _{j=1}^{n}x_{ij}=1,$	${displaystyle forall iin I}$
	${displaystyle y_{j}in {0,1},}$	$forall jin {1,ldotsn}$
	$x_{ij} in {0,1},$	${displaystyle forall iin I,forall jin {1,ldotsn}}$

Donde ${displaystyle y_{j}=1}$ si bin $j$ se utiliza y $x_{ij} = 1$ si el tema $i$ se pone en bin $j$ .

Dureza del embalaje del contenedor

El problema de empaquetamiento en contenedores es fuertemente NP-completo. Esto se puede probar reduciendo el problema de 3 particiones fuertemente NP-completo al empaque de contenedores.

Además, no puede haber algoritmo de aproximación con relación de aproximación absoluta menor que ${displaystyle {tfrac {3}{2}}}$ a) ${displaystyle {mathsf {P}}={mathsf {NP}}}$ . Esto puede ser probado por una reducción del problema de partición: dada una instancia de partición donde la suma de todos los números de entrada es $2T$ , construir un caso de bin-packing en el que el tamaño de la bin es $T$ . Si existe una partición igual de las entradas, entonces el embalaje óptimo necesita 2 cubos; por lo tanto, cada algoritmo con una relación de aproximación menor que 3/2 debe devolver menos de 3 cubos, que deben ser 2 cubos. En cambio, si no hay una partición igual de las entradas, entonces el embalaje óptimo necesita al menos 3 cubos.

Por otro lado, 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 de ubicación fija $B$ .

Algoritmos de aproximación para bin packing

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

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

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

0,A(L)/mathrm {OPT} (L)leq r{text{ for all lists }}L{text{ with }}mathrm {OPT} (L)geq N}.}" xmlns="http://www.w3.org/1998/Math/MathML">RAJUEGO JUEGO ↑ ↑ inf{}r≥ ≥ 1:∃ ∃ N■0,A()L)/OPT()L)≤ ≤ rpara todas las listasLconOPT()L)≥ ≥ N}.{displaystyle R_{A}^{infty }equiv inf{rgeq 1:exists N título0,A(L)/mathrm {OPT} (L)leq r{text{ for all lists }L{text{ with }mathrm {OPT} (L)geq N}.}0,A(L)/mathrm {OPT} (L)leq r{text{ for all lists }}L{text{ with }}mathrm {OPT} (L)geq N}.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e3ee61d3cbdfdee4396999f8451035cba5dd31a7" style="vertical-align: -1.005ex; width:79.65ex; height:3.009ex;"/>

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

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

Además, se puede restringir las listas a aquellas para las cuales todos los artículos tienen un tamaño de la mayoría $alpha$ . Para tales listas, las ratios de rendimiento de tamaño consolidado se denotan como ${displaystyle R_{A}({text{size}}leq alpha)}$ y ${displaystyle R_{A}^{infty }({text{size}}leq alpha)}$ .

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

Heurística en línea, que considera los artículos en un orden dado y los coloca uno por uno dentro de los contenedores. Estas heurísticas también son aplicables a la versión en línea de este problema.
Heurística sin línea, que modifica la lista dada de artículos, por ejemplo, clasificando 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 de tiempo. Una subcategoría de heurísticas fuera de línea es esquemas de aproximación asintotica. Estos algoritmos tienen una garantía de aproximación de la forma ${displaystyle (1+varepsilon)mathrm {OPT} (L)+C}$ para cierta constante que puede depender $1/varepsilon$ . Para un tamaño arbitrario ${displaystyle mathrm {OPT} (L)}$ estos algoritmos se acercan arbitrariamente ${displaystyle mathrm {OPT} (L)}$ . Sin embargo, esto viene a costa de un (drastically) aumento de la complejidad del tiempo en comparación con los enfoques heurísticos.

Heurística en línea

En la versión en línea del problema de embalaje 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 saber cuál será el próximo artículo o incluso si habrá otro. David S. Johnson ha estudiado un conjunto diverso de heurísticas fuera de línea y en línea para el empaque en contenedores en su Ph.D. tesis.

Algoritmos de clase única

Hay muchos algoritmos simples que usan el siguiente esquema general:

Para cada elemento en la lista de entrada:
1. Si el artículo encaja en uno de los contenedores abiertos actualmente, ponlo en uno de estos contenedores;
2. De lo contrario, abre un nuevo contenedor y pone el nuevo artículo en él.

Los algoritmos difieren en el criterio por el cual eligen la papelera abierta para el nuevo elemento en el paso 1 (consulte las páginas vinculadas para obtener más información):

Siguiente Fit (NF) Siempre mantiene un único cubo abierto. Cuando el nuevo artículo no encaja en él, cierra el contenedor actual y abre un nuevo contenedor. Su ventaja es que es un algoritmo de espacio limitado ya que sólo necesita mantener un único bin abierto en la memoria. Su desventaja es que su relación de aproximación asintotica es 2. En particular, ${displaystyle NF(L)leq 2cdot mathrm {OPT} (L)-1}$ , y para cada ${displaystyle Nin mathbb {N} }$ existe una lista $L$ tales que ${displaystyle mathrm {OPT} (L)=N}$ y ${displaystyle NF(L)=2cdot mathrm {OPT} (L)-2}$ . Su relación de aproximación asintotica puede mejorarse en cierta medida sobre la base de los tamaños del artículo: ${displaystyle R_{NF}^{infty }({text{size}}leq alpha)leq 2}$ para todos ${displaystyle alpha geq 1/2}$ y ${displaystyle R_{NF}^{infty }({text{size}}leq alpha)leq 1/(1-alpha)}$ para todos ${displaystyle alpha leq 1/2}$ . Para cada algoritmo $A$ que es un AnyFit-algorithm sostiene que ${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 sólo un bin abierto, el algoritmo mantiene el último $k$ Los cubos abren y eligen el primer cubo en el que cabe el artículo. Por lo tanto, se llama a k-bounded space algoritmo. Para $kgeq 2$ el NkF ofrece resultados que se mejoran en comparación con los resultados del NF, sin embargo, aumentando $k$ a valores constantes más grandes que $2$ mejora el algoritmo no más en su peor comportamiento. Si algoritmo $A$ es un CasiAnyFit-algorithm y ${displaystyle m=lfloor 1/alpha rfloor geq 2}$ entonces ${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 artículo en el primero Bin en el que encaja. Su relación de aproximación es ${displaystyle FF(L)leq lfloor 1.7mathrm {OPT} rfloor }$ , y hay una familia de listas de entrada $L$ para la cual ${displaystyle FF(L)}$ coincide con este límite.
Best-Fit (FB), también, mantiene todos los contenedores abiertos, pero los intentos de colocar cada nuevo artículo en el contenedor con el máximo carga en la que encaja. Su relación de aproximación es idéntica a la de FF, es decir: ${displaystyle BF(L)leq lfloor 1.7mathrm {OPT} rfloor }$ , y hay una familia de listas de entrada $L$ para la cual ${displaystyle BF(L)}$ coincide con este límite.
Worst-Fit (WF) intentos de colocar cada nuevo artículo en el contenedor con el mínimo Carga. Puede comportarse tan mal como Next-Fit, y lo hará en la peor lista de casos para eso ${displaystyle NF(L)=2cdot mathrm {OPT} (L)-2}$ . Además, sostiene que ${displaystyle R_{WF}^{infty }({text{size}}leq alpha)=R_{NF}^{infty }({text{size}}leq alpha)}$ . Como WF es un AnyFit-algorithm, existe un AnyFit-algorithm tal que ${displaystyle R_{AF}^{infty }(alpha)=R_{NF}^{infty }(alpha)}$ .
Casi peor (AWF) intentos de colocar cada nuevo artículo dentro del segundo más vacío open bin (o emptiest bin si hay dos cubos de este tipo). Si no encaja, intenta el más vacío. Tiene una relación asintotica del peor de los casos ${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 casi cualquier ajuste:

En un AnyFit (AF) algoritmo, si los contenedores no vacíos actuales son B₁,...B_j, entonces el artículo actual no será empaquetado B_{j+ 1} a menos que no cabe en ninguno de B₁,...B_j. Los algoritmos FF, WF, BF y AWF satisfacen esta condición. Johnson demostró que, para cualquier algoritmo de AnyFit A y cualquier $alpha$ :
${displaystyle R_{FF}^{infty }(alpha)leq R_{A}^{infty }(alpha)leq R_{WF}^{infty }(alpha)}$ .
En un CasiAnyFit (AAF) algoritmo, si los contenedores no vacíos actuales son B₁,...B_j, y de estos contenedores, B_k es el único bin con la carga más pequeña, entonces el artículo actual no se empaquetará en B_k, a menos que no cabe 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 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 índices de aproximación con heurísticas que no son 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):

Embalaje de basura (RFF) particiones el tamaño del artículo en cuatro rangos: ${displaystyle left({frac {1}{2}},1right]}$ , ${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]}$ . Del mismo modo, los contenedores se clasifican en cuatro clases. El siguiente tema ${displaystyle iin L}$ se asigna primero a su clase correspondiente. Dentro de esa clase, se asigna a un bin usando el primer beneficio. Tenga en cuenta que este algoritmo no es un algoritmo Any-Fit ya que puede abrir un nuevo bin a pesar de que el elemento actual se ajusta dentro de un contenedor abierto. Este algoritmo fue presentado por Andrew Chi-Chih Yao, quien demostró que tiene una garantía de aproximación ${displaystyle RFF(L)leq (5/3)cdot mathrm {OPT} (L)+5}$ y presentó una familia de listas $L_{k}$ con ${displaystyle RFF(L_{k})=(5/3)mathrm {OPT} (L_{k})+1/3}$ para ${displaystyle mathrm {OPT} (L)=6k+1}$ .
Armonic-k particiones el intervalo de tamaños ${displaystyle (0,1]}$ basado en una progresión armónica hacia $k-1$ pedazos ${displaystyle I_{j}:=left({frac {1}{j+1}},{frac {1}{j}}right]}$ para $<math alttext="{displaystyle 1leq j1\leq \leq j.k{displaystyle 1leq jierek} <img alt="{displaystyle 1leq j$ 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. Tiene una complejidad del tiempo ${displaystyle {mathcal {O}}(|L|log(|L|))}$ y a cada paso, hay $k$ los contenedores abiertos que pueden ser utilizados para colocar objetos, es decir, es un $k$ - algoritmo espacial atado. Para $k rightarrow infty$ , su relación de aproximación satisfechas ${displaystyle R_{Hk}^{infty }approx 1.6910}$ , y es asintóticamente apretado.
Refined-harmonic combina ideas de Harmonic-k con ideas de Refined-First-Fit. Coloca los elementos más grandes que ${displaystyle {tfrac {1}{3}}}$ similar al Refined-First-Fit, mientras que los artículos más pequeños se colocan utilizando Harmonic-k. La intuición de esta estrategia es reducir los enormes desechos para los contenedores que contienen piezas que son más grandes que ${displaystyle {tfrac {1}{2}}}$ . Este algoritmo fue descrito por primera vez por Lee y Lee. Demostraron que ${displaystyle k=20}$ sostiene que ${displaystyle R_{RH}^{infty }leq 373/228}$ .

Límites inferiores generales para algoritmos en línea

Yao demostró en 1980 que no puede haber algoritmo en línea con una relación competitiva asintotica menor que ${displaystyle {tfrac {3}{2}}}$ . Brown y Liang mejoraron este límite a 1.53635. Después, este límite fue mejorado 1.54014 por Vliet. En 2012, este límite inferior fue mejorado de nuevo por Békési y Galambos a ${displaystyle {tfrac {248}{161}}approx 1.54037}$ .

Tabla comparativa

Algoritm	Garantía de aproximación	Lista de casos peor $L$	Time-complexity
Next-fit (NF)	${displaystyle NF(L)leq 2cdot mathrm {OPT} (L)-1}$	${displaystyle NF(L)=2cdot mathrm {OPT} (L)-2}$	${displaystyle {mathcal {O}}(\|L\|)}$
Primer beneficio (FF)	${displaystyle FF(L)leq lfloor 1.7mathrm {OPT} (L)rfloor }$	${displaystyle FF(L)=lfloor 1.7mathrm {OPT} (L)rfloor }$	${displaystyle {mathcal {O}}(\|L\|log(\|L\|))}$
Best-fit (BF)	${displaystyle BF(L)leq lfloor 1.7mathrm {OPT} (L)rfloor }$	${displaystyle BF(L)=lfloor 1.7mathrm {OPT} (L)rfloor }$	${displaystyle {mathcal {O}}(\|L\|log(\|L\|))}$
Worst-Fit (WF)	${displaystyle WF(L)leq 2cdot mathrm {OPT} (L)-1}$	${displaystyle WF(L)=2cdot mathrm {OPT} (L)-2}$	${displaystyle {mathcal {O}}(\|L\|log(\|L\|))}$
Casi peor (AWF)	${displaystyle R_{AWF}^{infty }leq 17/10}$	${displaystyle R_{AWF}^{infty }=17/10}$	${displaystyle {mathcal {O}}(\|L\|log(\|L\|))}$
Refined-First-Fit (RFF)	${displaystyle RFF(L)leq (5/3)cdot mathrm {OPT} (L)+5}$	${displaystyle RFF(L)=(5/3)mathrm {OPT} (L)+1/3}$ (por ${displaystyle mathrm {OPT} (L)=6k+1}$ )	${displaystyle {mathcal {O}}(\|L\|log(\|L\|))}$
Armonic-k (Hk)	${displaystyle R_{Hk}^{infty }leq 1.69103}$ para $k rightarrow infty$	${displaystyle R_{Hk}^{infty }geq 1.69103}$	${displaystyle {mathcal {O}}(\|L\|log(\|L\|)}$
Refined Harmonic (RH)	${displaystyle R_{RH}^{infty }leq 373/228approx 1.63597}$		${displaystyle {mathcal {O}}(\|L\|)}$
Armonía Modificada (MH)	${displaystyle R_{MH}^{infty }leq 538/33approx 1.61562}$
Armonía Modificada 2 (MH2)	${displaystyle R_{MH2}^{infty }leq 239091/148304approx 1.61217}$
Armonic + 1 (H+1)		${displaystyle R_{H+1}^{infty }geq 1.59217}$
Armonic ++ (H+)	${displaystyle R_{H++}^{infty }leq 1.58889}$	${displaystyle R_{H++}^{infty }geq 1.58333}$

Algoritmos sin conexión

En la versión sin conexión del embalaje en contenedores, el algoritmo puede ver todos los elementos antes de comenzar a colocarlos en los contenedores. Esto permite obtener relaciones de aproximación mejoradas.

Aproximación multiplicativa

La técnica más simple utilizada por los algoritmos fuera de línea es:

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

Johnson demostró que cualquier algoritmo AnyFit A que se ejecuta en una lista ordenada por tamaño descendente tiene una relación de aproximación asintótica de

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

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

Reducción de los beneficios (FFD) - ordena los elementos por tamaño descendente, luego llama First-Fit. Su relación de aproximación es ${displaystyle FFD(I)={frac {11}{9}}mathrm {OPT} (I)+{frac {6}{9}}}$ , y esto es apretado.
Próxima reducción de beneficios (NFD) - ordena los elementos por tamaño descendente, luego llama Next-Fit. Su relación aproximada es ligeramente inferior a 1,7 en el peor de los casos. También se ha analizado probabilísticamente. Next-Fit empaca 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.
Modificación de la reducción de los primeros beneficios (MFFD) - mejora en FFD para artículos más grandes de la mitad de un bin clasificando artículos por tamaño en cuatro clases grandes, medias, pequeñas y pequeñas, 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 ${displaystyle MFFD(I)leq {frac {71}{60}}mathrm {OPT} (I)+1}$ .

Fernandez de la Vega y Lueker presentaron un PTAS para el embalaje de contenedores. Por todos $0}" xmlns="http://www.w3.org/1998/Math/MathML">ε ε ■0{displaystyle varepsilon }0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e04ec3670b50384a3ce48aca42e7cc5131a06b12" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;"/>$ , su algoritmo encuentra una solución con tamaño a la mayoría ${displaystyle (1+varepsilon)mathrm {OPT} +1}$ y corre en el tiempo ${displaystyle {mathcal {O}}(nlog(1/varepsilon))+{mathcal {O}}_{varepsilon }(1)}$ , donde ${displaystyle {mathcal {O}}_{varepsilon }(1)}$ denota una función sólo dependiente de $1/varepsilon$ . Para este algoritmo, inventaron el método redondeo de entrada adaptativo: los números de entrada se agrupan y redondean hasta el valor del máximo en cada grupo. Esto produce una instancia con un pequeño número de tamaños diferentes, que se pueden resolver exactamente utilizando el programa lineal de configuración.

Aproximación aditiva

El algoritmo de empaquetado de bin Karmarkar-Karp encuentra una solución con tamaño a la mayoría ${displaystyle mathrm {OPT} +{mathcal {O}}(log ^{2}(mathrm {OPT}))}$ , y corre en el tiempo polinomio en $n$ (el polinomio tiene un alto grado - al menos 8).

Rothvoss presentó un algoritmo que genera una solución con ${displaystyle mathrm {OPT} +{mathcal {O}}(log(mathrm {OPT})cdot log log(mathrm {OPT}))}$ Bins.

Hoberg y Rothvoss mejoraron este algoritmo para generar una solución con ${displaystyle mathrm {OPT} +{mathcal {O}}(log(mathrm {OPT}))}$ Bins. El algoritmo es aleatorizado, y su tiempo de funcionamiento es polinomio en $n$ .

Tabla comparativa

Algoritm	Garantía de aproximación	Caso peor
Reducción de los beneficios (FFD)	${displaystyle mathrm {FFD} (I)leq {frac {11}{9}}mathrm {OPT} (I)+{frac {6}{9}}}$	${displaystyle mathrm {FFD} (I)={frac {11}{9}}mathrm {OPT} (I)+{frac {6}{9}}}$
Modificación de la reducción de las prestaciones (MFFD)	${displaystyle mathrm {MFFD} (I)leq {frac {71}{60}}mathrm {OPT} (I)+1}$	${displaystyle R_{mathrm {MFFD} }^{infty }geq {frac {71}{60}}}$
Karmarkar y Karp	${displaystyle mathrm {KK} (I)leq mathrm {OPT} (I)+O(log ^{2}{mathrm {OPT} (I)})}$
Rothvoss	${displaystyle mathrm {HB} (I)leq mathrm {OPT} (I)+O(log {mathrm {OPT} (I)}log log {mathrm {OPT} (I)})}$
Hoberg y Rothvoss	${displaystyle mathrm {HB} (I)leq mathrm {OPT} (I)+O(log {mathrm {OPT} (I)})}$

Algoritmos exactos

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

Schreiber y Korf presentaron una mejora adicional en 2013. Se muestra 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 -y-corte-y-precio) de Belov y Scheithauer en 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 un pequeño número 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 de contenedores de alta multiplicidad, y admite algoritmos más eficientes que el problema general.

Bin-packing con fragmentación

El bin-packing con fragmentación o bin-packing de objetos fragmentables es una variante del problema del bin packing en el que se permite dividir elementos en partes y poner cada parte por separado en un contenedor diferente. Dividir 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 programa óptimo puede volverse más fácil, ya que algunas de las variables de optimización se vuelven continuas. Por otro lado, desarmar elementos puede resultar costoso. El problema fue presentado por primera vez por Mandal, Chakrabary y Ghose.

Variantes

El problema tiene dos variantes principales.

En la primera variante, llamada envasado con fragmentación de tamaño creciente ()BP-SIF), cada elemento puede ser fragmentado; las unidades superiores se añaden al tamaño de cada fragmento.
En la segunda variante, llamada envasado con fragmentación de tamaño reservada ()BP-SPF) cada artículo tiene un tamaño y un costo; la fragmentación de un artículo aumenta su costo pero no cambia su tamaño.

Complejidad computacional

Mandal, Chakrabary y Ghose demostraron que BP-SPF es NP-duro.

Menakerman y Rom demostraron que BP-SIF y BP-SPF son fuertemente NP-duros. A pesar de la dureza, presentan varios algoritmos e investigan su desempeño. Sus algoritmos usan algoritmos clásicos para bin-packing, como el siguiente ajuste y la disminución del primer ajuste, como base para sus algoritmos.

Bertazzi, Golden y Wang presentaron una variante de BP-SIF con $1-x$ regla de división: se permite dividir un artículo de una sola manera según su tamaño. Es útil para el problema de enrutamiento del vehículo, por ejemplo. En su papel, proporcionan el peor rendimiento de la variante.

Shachnai, Tamir y Yehezkeli 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 introdujo una variante de BP-SPF en la que algunos artículos están en conflicto y está prohibido empaquetar fragmentos de artículos en conflicto en el mismo contenedor. Demostraron que esta variante también es NP-dura.

Cassazza y Ceselli introdujeron una variante sin costo ni gastos generales, y el número de contenedores es fijo. Sin embargo, el número de fragmentaciones debe minimizarse. Presentan algoritmos de programación matemática para soluciones exactas y aproximadas.

Problemas relacionados

El problema de la mochila fraccionada con penaltis fue introducido por Malaguti, Monaci, Paronuzzi y Pferschy. Desarrollaron un FPTAS y un programa dinámico para el problema, y mostraron un extenso estudio computacional comparando el desempeño de sus modelos. Ver también: Programación de trabajos fraccionados.

Restricciones de cardinalidad en los contenedores

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

Krause, Shen y Schwetman presentan este problema como una variante de programación de trabajo óptima: un ordenador tiene algunos k procesadores. Hay algunos n empleos que requieren tiempo unitario (1), pero tienen diferentes requisitos de memoria. Cada unidad de tiempo se considera un único bin. El objetivo es utilizar como pocos cubos (= unidades de tiempo) como sea posible, asegurando al mismo tiempo que en cada cubo, en la mayoría k Trabajos corren. Presentan varios algoritmos heurísticos que encuentran una solución con ${displaystyle 2mathrm {OPT} }$ Bins.
Kellerer y Pferschy presentan un algoritmo con tiempo de ejecución ${displaystyle O(n^{2}log {n})}$ , que encuentra una solución con ${displaystyle leftlceil {frac {3}{2}}mathrm {OPT} rightrceil }$ Bins. Su algoritmo realiza una búsqueda binaria de OPT. Por cada valor buscado m, intenta empacar los elementos en 3m/2 cubos.

Funciones no aditivas

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

Anily, Bramel y Simchi-Levi estudian un entorno donde el costo de un bin es una función de cóncava del número de elementos en el contenedor. El objetivo es minimizar el total Costo en lugar del número de contenedores. Muestran que el embalaje de basura que aumenta la función siguiente alcanza una relación de aproximación del peor de los casos absolutos de la mayoría de 7/4, y una relación asintotica del peor de los casos de 1.691 para cualquier función de concave y monotone costo.
Cohen, Keller, Mirrokni y Zadimoghaddam estudian un entorno donde el tamaño de los artículos no se conoce con antelación, pero es una variable aleatoria. Esto es particularmente común en ambientes de computación en la nube. Aunque hay un límite superior en la cantidad de recursos que un usuario necesita, la mayoría de los usuarios utilizan mucho menos que la capacidad. Por lo tanto, el administrador de la nube puede ganar mucho por un ligero exceso de compromiso. Esto induce una variante de empaquetado de basura con restricciones de oportunidad: la probabilidad de que la suma de los tamaños en cada contenedor es en la mayoría B por lo menos p, donde p es una constante fija (paquete estándar corresponde a p=1). Muestran que, bajo suposiciones leves, este problema equivale a un embalaje de contenedores submodular problema, en el que la "carga" en cada bin no es igual a la suma de los elementos, sino a una determinada función submodular de ella.

Problemas relacionados

En el problema del embalaje en 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 la partición de números de varias vías, el número de contenedores es fijo y su tamaño puede ampliarse. 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 de multiprocesador o problema de mínimo makepan, el objetivo es específicamente minimizar el tamaño del contenedor más grande).

En el problema del embalaje en contenedores inverso, 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 del artículo para que todos los artículos puedan empaquetarse en el número prescrito de contenedores.

En el problema de empaquetado máximo de contenedores de recursos, el objetivo es maximizar el número de contenedores utilizados, de modo que, para algunos pedidos de contenedores, ningún artículo en un el contenedor posterior cabe en un contenedor anterior. En un problema dual, la cantidad de contenedores es fija 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 sin llenar.

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

En el problema de la 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 una dificultad diferente -valor 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 de embalaje en contenedores.

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

En el problema del empaquetado egoísta en contenedores, cada artículo es un jugador que quiere minimizar su costo.

También existe una variante de bin packing en la que el coste que debe minimizarse no es el número de bins, sino una determinada función cóncava del número de artículos en cada bin.

Otras variantes son embalaje en contenedores bidimensional, embalaje en contenedores tridimensional, embalaje en contenedores con entrega,

Recursos

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

Implementaciones

Online: visualización de heurística para envases de bin 1D y 2D
Python: El paquete prtpy contiene código para varios algoritmos de numeración, envasado de bin y encubrimiento de bin. El paquete de binpacking contiene algoritmos codiciosos para resolver dos problemas típicos de empaquetado de basura.
C++: El paquete de bin-packing contiene varios algoritmos codiciosos, así como datos de prueba. El paquete OR-tools contiene algoritmos de embalaje de bin en C++, con envolturas en Python, C# y Java.
C: Implementación de 7 algoritmos clásicos de empaquetado de bin en C con resultados e imágenes
PHP: PHP Clase para empaquetar archivos sin exceder un límite de tamaño dado
Haskell: Una implementación de varias heurísticas de embalaje de basura, incluyendo FFD y MFFD.
C: Fpart: herramienta de línea de comando de código abierto para empaquetar archivos (C, BSD-licensed)
C#: Bin Packing y Cutting Stock Solver
Java: Caprf - Corte y embalaje Algorithms Marco de Investigación, incluyendo un número de algoritmos de embalaje de bin y datos de prueba.

Contenido relacionado

Más resultados...