Hispanopedia Wiki
Articulo de referencia

Problema de empaquetamiento de contenedores

El problema de empaquetamiento de contenedores [ 1 ] [ 2 ] [ 3 ] [ 4 ] es un problema de optimización en el que artículos de diferentes tamaños deben empaquetarse en un número f...

Hispanopedia WikiContenido en espanolLectura gratuita

El problema de empaquetamiento de contenedores [ 1 ] [ 2 ] [ 3 ] [ 4 ] es un problema de optimización en el que artículos de diferentes tamaños deben empaquetarse en un número finito de contenedores, cada uno de una capacidad fija dada, de manera que se minimice el número 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-difícil , y el problema de decisión correspondiente , decidir 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 de primer ajuste proporciona una solución rápida pero a menudo no óptima, que consiste en colocar cada elemento en el primer contenedor en el que quepa. Requiere un tiempo de Θ ( 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 descendente (a veces conocido como algoritmo de primer ajuste descendente), 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 algoritmo de 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 corte de existencias . Cuando el número de contenedores se limita a uno 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 problema de empaquetamiento de contenedores que se da en la práctica es cuando los elementos pueden compartir espacio al ser empaquetados en un contenedor. Específicamente, un conjunto de elementos podría ocupar menos espacio al ser empaquetados juntos que la suma de sus tamaños individuales. Esta variante se conoce como empaquetamiento de máquinas virtuales (VM) [ 7 ] , ya que cuando las máquinas virtuales (VM) se empaquetan en un servidor, su requerimiento total de memoria puede disminuir debido a las páginas compartidas por las VM que solo necesitan almacenarse una vez. Si los elementos pueden compartir espacio de forma arbitraria, el problema de empaquetamiento de contenedores es difícil incluso de aproximar. Sin embargo, si el uso compartido de espacio se ajusta a una jerarquía, como es el caso del uso compartido de memoria en las máquinas virtuales, el problema de empaquetamiento de contenedores se puede aproximar de manera eficiente.

Otra variante del método de empaquetado en contenedores que resulta interesante en la práctica es el llamado empaquetado en línea . En este método, se supone que los artículos de distinto volumen llegan secuencialmente, y quien toma las decisiones debe decidir si selecciona y empaqueta el artículo que observa en ese momento o si lo deja pasar. Cada decisión es irreversible. En cambio, el empaquetado fuera de línea permite reorganizar los artículos con la esperanza de lograr un mejor empaquetado una vez que lleguen más. Esto, por supuesto, requiere espacio de 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 finitoI{\displaystyle I}de artículos, un tamaños(i)∈Z+{\displaystyle s(i)\in \mathbb {Z} ^{+}}para cadai∈I{\displaystyle i\in I}, una capacidad de compartimento entero positivoB{\displaystyle B}y un número entero positivoK{\displaystyle K}.

Pregunta: ¿Existe una partición deI{\displaystyle I}en conjuntos disjuntosI1,…,IK{\displaystyle I_{1},\dots ,I_{K}}de tal manera que la suma de los tamaños de los elementos en cadaIj{\displaystyle I_{j}}esB{\displaystyle B}¿O menos?

Nótese que en la literatura a menudo se utiliza una notación alternativa, pero no equivalente, dondeB=1{\displaystyle B=1}ys(i)∈Q∩(0,1]{\displaystyle s(i)\in \mathbb {Q} \cap (0,1]}para cadai∈I{\displaystyle i\in I}Además, la investigación se interesa principalmente en la variante de optimización, que pide el valor más pequeño posible deK{\displaystyle K}Una solución es óptima si tiene un mínimoK{\displaystyle K}. ElK{\displaystyle K}-valor para una solución óptima para un conjunto de elementosI{\displaystyle I}se denota porOPAGT(I){\displaystyle \mathrm {OPT} (I)}o simplementeOPAGT{\displaystyle \mathrm {OPT} }si el conjunto de elementos queda claro a partir del contexto.

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

dóndeyj=1{\displaystyle y_{j}=1}si contenedorj{\displaystyle j}se utiliza yincógnitaij=1{\displaystyle x_{ij}=1}si el artículoi{\displaystyle i}se coloca en el contenedorj{\displaystyle j}. [ 9 ]

Dureza del embalaje del contenedor

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

Además, no puede haber ningún algoritmo de aproximación con una relación de aproximación absoluta menor que32{\displaystyle {\tfrac {3}{2}}}a menos quePAG=nortePAG{\displaystyle {\mathsf {P}}={\mathsf {NP}}}. 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 es2T{\displaystyle 2T}Construir una instancia de empaquetamiento de contenedores en la que el tamaño del contenedor sea T. Si existe una partición equitativa de las entradas, entonces el empaquetamiento ó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, que deben ser 2 contenedores. Por el contrario, si no existe una partición equitativa de las entradas, entonces el empaquetamiento óptimo necesita al menos 3 contenedores.

Por otro lado, el problema de empaquetamiento de contenedores es resoluble en tiempo pseudopolinomial para cualquier número fijo de contenedores K , y resoluble 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 razones de aproximación. Para una lista dada de elementosL{\displaystyle L}el númeroA(L){\displaystyle A(L)}indica el número de contenedores utilizados cuando el algoritmoA{\displaystyle A}se aplica a la listaL{\displaystyle L}, mientrasOPAGT(L){\displaystyle \mathrm {OPT} (L)}denota el número óptimo para esta lista. La relación de rendimiento en el peor caso absolutoRA{\displaystyle R_{A}}para un algoritmoA{\displaystyle A}se define como

RA≡inf{r≥1:A(L)/OPAGT(L)≤r para todas las listas L}.{\displaystyle R_{A}\equiv \inf\{r\geq 1:A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L\}.}

Por otro lado, la razón asintótica del peor casoRA∞{\displaystyle R_{A}^{\infty }}se define como

RA∞≡inf{r≥1:∃norte>0,A(L)/OPAGT(L)≤r para todas las listas L con OPAGT(L)≥norte}.{\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 forma equivalente,RA∞{\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: [ 4 ]

A(L)≤RA∞⋅OPAGT(L)+K{\displaystyle A(L)\leq R_{A}^{\infty }\cdot \mathrm {OPT} (L)+K}.

Además, se pueden restringir las listas a aquellas para las que todos los elementos tengan un tamaño máximo deα{\displaystyle \alpha }Para dichas listas, las relaciones de rendimiento de tamaño limitado se denotan comoRA(tamaño≤α){\displaystyle R_{A}({\text{size}}\leq \alpha )}yRA∞(tamaño≤α){\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. Las heurísticas en línea 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 de elementos dada, 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 baja 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(1+ε)OPAGT(L)+do{\displaystyle (1+\varepsilon )\mathrm {OPT} (L)+C}para alguna constante que puede depender de1/ε{\displaystyle 1/\varepsilon }Para un valor arbitrariamente grandeOPAGT(L){\displaystyle \mathrm {OPT} (L)}Estos algoritmos se acercan arbitrariamente aOPAGT(L){\displaystyle \mathrm {OPT} (L)}Sin embargo, esto conlleva un aumento drástico en la complejidad temporal en comparación con los enfoques heurísticos.

Heurística en línea

En la versión en línea del problema de empaquetamiento 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 conocer el siguiente artículo o incluso si habrá otro. David S. Johnson estudió un conjunto diverso de heurísticas fuera de línea y en línea para el problema de empaquetamiento de contenedores en su tesis doctoral. [ 11 ]

Algoritmos de una sola clase

Existen muchos algoritmos sencillos 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 que están actualmente abiertos, colóquelo en uno de esos contenedores;
    2. De lo contrario, abre un nuevo contenedor y coloca el nuevo artículo dentro.

Los algoritmos difieren en el criterio que utilizan para elegir el contenedor vacío para el nuevo artículo en el paso 1 (consulte 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 limitado, 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,norteF(L)≤2⋅OPAGT(L)−1{\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}y para cada unonorte∈norte{\displaystyle N\in \mathbb {N} }existe una lista L tal queOPAGT(L)=norte{\displaystyle \mathrm {OPT} (L)=N}ynorteF(L)=2⋅OPAGT(L)−2{\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}. [ 11 ] Su razón de aproximación asintótica puede mejorarse un poco en función de los tamaños de los elementos:RnorteF∞(tamaño≤α)≤2{\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2}a pesar deα≥1/2{\displaystyle \alpha \geq 1/2}yRnorteF∞(tamaño≤α)≤1/(1−α){\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )}a pesar deα≤1/2{\displaystyle \alpha \leq 1/2}Para cada algoritmo A que sea un algoritmo AnyFit, se cumple queRA∞(tamaño≤α)≤RnorteF∞(tamaño≤α){\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{NF}^{\infty }({\text{size}}\leq \alpha )}.
  • Next-k-Fit (NkF) es una variante de Next-Fit, pero en lugar de mantener solo un contenedor abierto, el algoritmo mantiene abiertos los últimos k contenedores y elige el primer contenedor en el que encaja el elemento. Por lo tanto, se denomina algoritmo de espacio k-limitado . [ 12 ] Parak≥2{\displaystyle k\geq 2}El NkF ofrece resultados mejorados 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 ymetro=⌊1/α⌋≥2{\displaystyle m=\lfloor 1/\alpha \rfloor \geq 2}entoncesRA∞(tamaño≤α)≤Rnorte2F∞(tamaño≤α)=1+1/metro{\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{size}}\leq \alpha )=1+1/m}. [ 11 ]
  • First-Fit (FF) mantiene todos los contenedores abiertos, en el orden en que se abrieron. Intenta colocar cada nuevo elemento en el primer contenedor en el que cabe. Su índice de aproximación esFF(L)≤⌊1.7OPAGT⌋{\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }y existe una familia de listas de entrada L para las cualesFF(L){\displaystyle FF(L)}coincide con este límite. [ 13 ]
  • El método 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 índice de aproximación es idéntico al de FF, es decir:BF(L)≤⌊1.7OPAGT⌋{\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }y existe una familia de listas de entrada L para las cualesBF(L){\displaystyle BF(L)}coincide con este límite. [ 14 ]
  • 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 peor caso para eso.norteF(L)=2⋅OPAGT(L)−2{\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}Además, sostiene queRWF∞(tamaño≤α)=RnorteF∞(tamaño≤α){\displaystyle R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )}Dado que WF es un algoritmo AnyFit, existe un algoritmo AnyFit tal queRAF∞(α)=RnorteF∞(α){\displaystyle R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )}. [ 11 ]
  • El método Almost Worst-Fit (AWF) intenta colocar cada nuevo elemento dentro del segundo contenedor abierto más vacío (o el contenedor más vacío si hay dos de estos contenedores). Si no cabe, intenta con el más vacío. Tiene una razón asintótica en el peor caso de1710{\displaystyle {\tfrac {17}{10}}}. [ 11 ]

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 actuales no vacíos son B 1 ,..., B j , entonces el artículo actual no se colocará en B j +1 a menos que no quepa en ninguno de B 1 ,..., 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 }:
    RFF∞(α)≤RA∞(α)≤RWF∞(α){\displaystyle R_{FF}^{\infty }(\alpha )\leq R_{A}^{\infty }(\alpha )\leq R_{WF}^{\infty }(\alpha )}.
  • En un algoritmo AlmostAnyFit (AAF) , si los contenedores actuales no vacíos son B 1 ,..., B j , y de estos contenedores, B k es el único contenedor con la carga más pequeña, entonces el artículo actual no se colocará 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 α :
    RA∞(α)=RFF∞(α){\displaystyle R_{A}^{\infty }(\alpha )=R_{FF}^{\infty }(\alpha )} En particular:RA∞=1.7{\displaystyle R_{A}^{\infty }=1.7}.

Algoritmos refinados

Es posible obtener mejores índices 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):

  • El empaquetado en contenedores de ajuste preciso (RFF, por sus siglas en inglés) divide los tamaños de los artículos en cuatro rangos:(12,1]{\displaystyle \left({\frac {1}{2}},1\right]},(25,12]{\displaystyle \left({\frac {2}{5}},{\frac {1}{2}}\right]},(13,25]{\displaystyle \left({\frac {1}{3}},{\frac {2}{5}}\right]}, y(0,13]{\displaystyle \left(0,{\frac {1}{3}}\right]}. De manera similar, los contenedores se clasifican en cuatro clases. El siguiente elementoi∈L{\displaystyle i\in L}primero se asigna a su clase correspondiente. Dentro de esa clase, se asigna a un contenedor usando first-fit . Tenga en cuenta que este algoritmo no es un algoritmo Any-Fit ya que puede abrir un nuevo contenedor a pesar de que el elemento actual cabe dentro de un contenedor abierto. Este algoritmo fue presentado por primera vez por Andrew Chi-Chih Yao, [ 15 ] quien demostró que tiene una garantía de aproximación deRFF(L)≤(5/3)⋅OPAGT(L)+5{\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}y presentó una familia de listasLk{\displaystyle L_{k}}conRFF(Lk)=(5/3)OPAGT(Lk)+1/3{\displaystyle RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3}paraOPAGT(L)=6k+1{\displaystyle \mathrm {OPT} (L)=6k+1}.
  • Particiones armónicas-k del intervalo de tamaños(0,1]{\displaystyle (0,1]}basado en una progresión armónica enk−1{\displaystyle k-1}piezasIj:=(1j+1,1j]{\displaystyle I_{j}:=\left({\frac {1}{j+1}},{\frac {1}{j}}\right]}para1≤j<k{\displaystyle 1\leq j<k}yIk:=(0,1k]{\displaystyle I_{k}:=\left(0,{\frac {1}{k}}\right]}de tal manera que⋃j=1kIj=(0,1]{\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 deO(|L|registro⁡(|L|)){\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 k -limitado. Parak→∞{\displaystyle k\rightarrow \infty }, su razón de aproximación satisfaceRHk∞≈1.6910{\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 . Coloca los elementos más grandes que13{\displaystyle {\tfrac {1}{3}}}similar a como en Refined-First-Fit, mientras que los elementos más pequeños se colocan usando Harmonic-k. La intuición de esta estrategia es reducir el enorme desperdicio de contenedores que contienen piezas que son solo más grandes que12{\displaystyle {\tfrac {1}{2}}}. Este algoritmo fue descrito por primera vez por Lee y Lee. [ 16 ] Demostraron que parak=20{\displaystyle k=20}sostiene queRRH∞≤373/228{\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 razón competitiva asintótica menor que32{\displaystyle {\tfrac {3}{2}}}. Brown [ 17 ] y Liang [ 18 ] mejoraron esta cota a1.53635 . Posteriormente, este límite se mejoró a1,54014 por van Vliet. [ 19 ] [ 20 ] En 2012, este límite inferior fue mejorado nuevamente por Békési y Galambos [ 20 ] a248161≈1.54037{\displaystyle {\tfrac {248}{161}}\approx 1.54037}.

Tabla comparativa

Algoritmos fuera de línea

En la versión sin conexión del algoritmo de empaquetamiento de contenedores, este puede visualizar todos los elementos antes de comenzar a colocarlos en los contenedores. Esto permite obtener mejores índices de aproximación.

Aproximación multiplicativa

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

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

Johnson [ 11 ] demostró que cualquier esquema AnyFit A que se ejecuta en una lista ordenada por tamaño descendente tiene una razón de aproximación asintótica de

1.22≈119≤RA∞≤54=1,25{\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 enlazadas 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 índice de aproximación esFFD(I)=119OPAGT(I)+69{\displaystyle FFD(I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}}y esto es ajustado. [ 23 ]
  • 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 probabilísticamente. [ 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 ]
  • El método modificado de primer ajuste decreciente (MFFD) [ 27 ] mejora el método FFD para elementos mayores de 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 tamaño > 1/2 contenedor, > 1/3 contenedor, > 1/6 contenedor y elementos más pequeños, respectivamente. Su garantía de aproximación esMETROFFD(I)≤7160OPAGT(I)+1{\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 de contenedores. Para cadaε>0{\displaystyle \varepsilon >0}, su algoritmo encuentra una solución con un tamaño máximo de(1+ε)OPAGT+1{\displaystyle (1+\varepsilon )\mathrm {OPT} +1}y corre a tiempo O(norteregistro⁡(1/ε))+Oε(1){\displaystyle {\mathcal {O}}(n\log(1/\varepsilon ))+{\mathcal {O}}_{\varepsilon }(1)}, dóndeOε(1){\displaystyle {\mathcal {O}}_{\varepsilon }(1)}denota una función que depende únicamente de1/ε{\displaystyle 1/\varepsilon }Para este algoritmo, inventaron el método de redondeo adaptativo de entrada : los números de entrada se agrupan y se redondean al valor máximo de cada grupo. Esto produce una instancia con un número reducido de tamaños diferentes, que puede resolverse exactamente mediante el programa lineal de configuración . [ 30 ]

Aproximación aditiva

El algoritmo de empaquetamiento de contenedores de Karmarkar-Karp encuentra una solución con un tamaño máximoOPAGT+O(registro2⁡(OPAGT)){\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))}y se ejecuta en un tiempo polinomial en n (el polinomio tiene un grado alto, al menos 8).

Rothvoss [ 31 ] presentó un algoritmo que genera una solución con como máximoOPAGT+O(registro⁡(OPAGT)⋅registro⁡registro⁡(OPAGT)){\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))}contenedores.

Hoberg y Rothvoss [ 32 ] mejoraron este algoritmo para generar una solución con como máximoOPAGT+O(registro⁡(OPAGT)){\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} ))}contenedores. El algoritmo es aleatorio y su tiempo de ejecución es polinomial en n .

Tabla comparativa

Algoritmos exactos

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

Schreiber y Korf presentaron una mejora adicional en 2013. [ 37 ] Se demuestra que el nuevo algoritmo de Compleción de Contenedores Mejorada es hasta cinco órdenes de magnitud más rápido que el algoritmo de Compleción de Contenedores 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 contenedores como solución óptima. El algoritmo que mejor funciona depende de propiedades del problema como el número de elementos, el número óptimo de contenedores, el espacio no utilizado en la solución óptima y la precisión del valor.

Un número reducido de tamaños diferentes

Un caso especial del problema de empaquetamiento de contenedores se da cuando hay un número pequeño d de artículos de diferentes tamaños. Puede haber muchos artículos 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.

Empaquetado de contenedores con fragmentación

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

Variantes

El problema tiene dos variantes principales.

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

Complejidad computacional

Mandal, Chakrabarti y Ghose [ 38 ] demostraron que BP-SPF es NP-duro .

Menakerman y Rom [ 39 ] demostraron que BP-SIF y BP-SPF son problemas NP-difíciles . A pesar de su dificultad, presentan varios algoritmos e investigan su rendimiento. Sus algoritmos utilizan algoritmos clásicos para el empaquetamiento de contenedores, como next-fit y first-fit decreasing , como base.

Bertazzi, Golden y Wang [ 40 ] introdujeron una variante de BP-SIF con1−incógnita{\displaystyle 1-x}Regla de división: un elemento solo puede dividirse de una manera según su tamaño. Resulta útil, por ejemplo, para el problema de enrutamiento de vehículos . En su artículo, proporcionan el límite de rendimiento en el peor de los casos de esta variante.

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. 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 contenedores. Sin embargo, se debe minimizar el número de fragmentaciones. Presentan algoritmos de programación matemática para obtener soluciones tanto exactas como aproximadas.

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 rendimiento de sus modelos. Véase también: Planificación fraccionaria de tareas .

Rendimiento con tamaños de artículos divisibles

Un caso especial importante del problema de empaquetamiento de contenedores es cuando 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 algoritmos heurísticos para el problema de empaquetamiento de contenedores encuentran una solución óptima. [ 45 ]

Restricciones de cardinalidad en los contenedores

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

  • Krause, Shen y Schwetman [ 46 ] introducen este problema como una variante de la programación óptima de trabajos : una computadora tiene k procesadores. Hay n trabajos que toman un tiempo unitario (1), pero tienen diferentes requisitos de memoria. Cada unidad de tiempo se considera un solo contenedor. El objetivo es usar la menor cantidad posible de contenedores (=unidades de tiempo), asegurando que en cada contenedor se ejecuten como máximo k trabajos. Presentan varios algoritmos heurísticos que encuentran una solución con como máximo2OPAGT{\displaystyle 2\mathrm {OPT} }contenedores.
  • Kellerer y Pferschy [ 47 ] presentan un algoritmo con tiempo de ejecuciónO(norte2registro⁡norte){\displaystyle O(n^{2}\log {n})}, que encuentra una solución con como máximo⌈32OPAGT⌉{\displaystyle \left\lceil {\frac {3}{2}}\mathrm {OPT} \right\rceil }contenedores. Su algoritmo realiza una búsqueda binaria para OPT. Para cada valor buscado m , intenta empaquetar los elementos en 3 m /2 contenedores.

Funciones no aditivas

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

  • Anily, Bramel y Simchi-Levi [ 48 ] estudian un escenario donde 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 creciente alcanza una razón de aproximación absoluta en el peor caso de como máximo 7/4, y una razón asintótica en el peor caso de 1,691 para cualquier función de costo cóncava y monótona.
  • Cohen, Keller, Mirrokni y Zadimoghaddam [ 49 ] estudian un escenario donde 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 usuario determinado, la mayoría de los usuarios utilizan mucho menos que la capacidad. Por lo tanto, el administrador de la nube puede obtener grandes beneficios con una ligera sobreasignación . Esto induce una variante del problema de empaquetamiento de contenedores con restricciones de probabilidad : 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 problema de empaquetamiento de contenedores estándar corresponde a p = 1). Demuestran 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 los elementos, sino a una cierta función submodular de ella.

En el problema de empaquetamiento de 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 en múltiples vías , el número de compartimentos es fijo y su tamaño puede ampliarse. El objetivo es encontrar una partición en la que los tamaños de los compartimentos sean lo más iguales posible (en la variante denominada problema de planificación de multiprocesadores o problema de tiempo de finalización mínimo , el objetivo es específicamente minimizar el tamaño del compartimento más grande).

En el problema de empaquetamiento de contenedores vectoriales , cada elemento es un vector, y el tamaño de cada contenedor también es un vector. Sea un contenedor de tamañow{\displaystyle w}y la suma de vectores en el contenedor seav{\displaystyle v}, entonces el requisito es que∀i,vi≤wi{\displaystyle \forall i,v_{i}\leq w_{i}}. [ 50 ]

En el problema inverso de empaquetamiento de contenedores , [ 51 ] tanto el número de contenedores como sus tamaños son fijos, pero los tamaños de los artículos pueden variar. El objetivo es lograr la mínima perturbación en el vector de tamaños de los artículos para que todos los artículos puedan empaquetarse en el número de contenedores prescrito.

En el problema de empaquetamiento de contenedores con recursos máximos , [ 52 ] el objetivo es maximizar el número de contenedores utilizados, de manera que, para algún ordenamiento 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 manera que ningún elemento restante quepa en un contenedor vacío.

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

En el problema de asignación equitativa e indivisible de tareas (una variante de la asignación equitativa de ítems ), los ítems representan tareas, y hay diferentes personas, cada una de las cuales atribuye un valor de dificultad distinto 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). Muchas técnicas del problema de empaquetamiento de contenedores también se utilizan en este problema. [ 53 ]

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

En el problema de empaquetamiento de contenedores egoísta , cada artículo es un jugador que quiere minimizar su costo. [ 54 ]

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

En logística y comercio electrónico , el empaquetado tridimensional en contenedores es la base de la “cartonización”, donde el software selecciona una caja de envío y una disposición de embalaje viable para un conjunto de artículos; problemas industriales estrechamente relacionados incluyen la carga de contenedores y palés. [ 55 ]

Otras variantes son el empaquetado de contenedores bidimensional, [ 56 ] el empaquetado de contenedores tridimensional , [ 57 ] el empaquetado de contenedores con entrega , [ 58 ]

Recursos

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

Referencias

  1. ↑ Martello, Silvano; Toth, Paolo (1990), "Problema de empaquetamiento de contenedores" (PDF) , Problemas de la mochila: algoritmos e implementaciones informáticas , Chichester, Reino Unido: John Wiley and Sons, ISBN 0471924202Archivado del original (PDF) el 8 de mayo de 2006.
  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 del original el 16 de febrero de 2019. Recuperado el 27 de febrero de 2016 .
  4. ^ Coffman Jr. , Edward G .; Csirik, János; Galambos, Gábor; Martello, Silvano; Vigo, Daniele (2013), "Algoritmos de aproximación de embalaje de contenedores: estudio y clasificación" , en Pardalos, Panos M.; Du, Ding-Zhu; Graham, Ronald L. (eds.), 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 ascenso de colinas de propósito general para problemas de agrupamiento mínimo independientes del orden: un estudio de caso en coloración de grafos y empaquetamiento de contenedores" (PDF) , Computers and Operations Research , 36 (7): 2295–2310 , doi : 10.1016/j.cor.2008.09.004 , S2CID 1577334 
  7. ↑ Sindelar, Michael; Sitaraman, Ramesh K.; Shenoy, Prashant (2011). «Algoritmos conscientes del uso compartido para la colocación de máquinas virtuales» . Actas del vigésimo tercer simposio anual de la ACM sobre paralelismo en algoritmos y arquitecturas . págs. 367–378 . doi : 10.1145/1989493.1989554 . ISBN  978-1-4503-0743-7.
  8. 1 2 3 Garey, M. R. ; Johnson, D. S. (1979). Victor Klee (ed.). Computadoras e intratabilidad: una guía a la teoría de la NP-completitud . Una serie de libros en ciencias matemáticas. San Francisco, California: W. H. Freeman and Co. pp. x+338 . ISBN      0-7167-1045-5. MR 0519066 . 
  9. ^ Martello y Toth 1990 , pág. 221 
  10. ↑ Vazirani, Vijay V. (14 de marzo de 2013). Algoritmos de aproximación . Springer Berlin Heidelberg. pág. 74. ISBN  978-3662045657.
  11. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Johnson, David S (1973). "Algoritmos de empaquetamiento de contenedores casi óptimos" (PDF) . Instituto Tecnológico de Massachusetts .
  12. ↑ González, Teófilo F. (23 de mayo de 2018). Manual de algoritmos de aproximación y metaheurísticas. Volumen 2 Aplicaciones contemporáneas y emergentes . Taylor & Francis Incorporated. ISBN 9781498770156.
  13. 1 2 3 Dósa, György; Sgall, Jiri (2013). "Embalaje de 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. 1 2 3 György, Dósa; Sgall, Jirí (2014). "Análisis óptimo del empaquetamiento de contenedores de mejor ajuste". Autómatas, lenguajes y programación . Notas de clase en ciencias de la computación. Vol. 8572. págs. 429–441 . doi : 10.1007/978-3-662-43948-7_36 . ISBN   978-3-662-43947-0.
  15. 1 2 3 4 5 Yao, Andrew Chi-Chih (abril de 1980). "Nuevos algoritmos para el empaquetamiento de contenedores" . Journal of the ACM . 27 (2): 207– 227. doi : 10.1145/322186.322187 . S2CID 7903339 . 
  16. 1 2 3 4 5 6 7 Lee, CC; Lee, DT (julio de 1985). "Un algoritmo simple de empaquetamiento de contenedores en línea" . Journal of the 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. 1 2 Balogh, János; Békési, József; Galambos, Gábor (julio de 2012). "Nuevos límites inferiores para determinadas clases de algoritmos de empaquetado de contenedores" . Informática Teórica . 440– 441: 1– 13. doi : 10.1016/j.tcs.2012.04.017 .
  21. 1 2 Ramanan, Prakash; Brown, Donna J; Lee, CC; Lee, DT (septiembre de 1989). "Empaquetamiento 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. 1 2 3 Seiden, Steven S. (2002). "Sobre el problema de empaquetamiento de contenedores en línea". Journal of the ACM . 49 (5): 640– 671. doi : 10.1145/585265.585269 . S2CID 14164016 . 
  23. 1 2 3 Dósa, György (2007). "El límite ajustado del algoritmo de empaquetamiento de contenedores 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 (1981-06-01). "Una cota asintótica ajustada para el problema de empaquetamiento de contenedores con ajuste siguiente decreciente" . SIAM Journal on Algebraic and Discrete Methods . 2 (2): 147– 152. doi : 10.1137/0602019 . ISSN 0196-5212 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
  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 contenedores de ajuste siguiente decreciente" . 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 inversa 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. 1 2 Johnson, David S; Garey, Michael R (octubre de 1985). "Un teorema 7160 para el empaquetamiento de contenedores" . Journal of Complexity . 1 (1): 65– 106. doi : 10.1016/0885-064X(85)90022-6 .
  28. 1 2 Yue, Minyi; Zhang, Lei (julio de 1995). "Una demostración simple de la desigualdad MFFD(L) ≤ 71/60 OPT(L) + 1,L para el algoritmo de empaquetamiento de contenedores MFFD". Acta Mathematicae Applicatae Sinica . 11 (3): 318– 330. doi : 10.1007/BF02011198 . S2CID 118263129 . 
  29. ↑ Fernández de la Vega, W.; Lueker, GS (1981). "El problema de empaquetamiento de contenedores se puede resolver en 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 del original el 15 de julio de 2021.
  31. 1 2 Rothvoß, T. (2013-10-01). "Aproximación del empaquetamiento de contenedores dentro de O(log OPT · Log Log OPT) contenedores". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . pp. 20–29 . arXiv : 1301.4010 . doi : 10.1109/FOCS.2013.11 . ISBN  978-0-7695-5135-7. S2CID 15905063 . 
  32. 1 2 Hoberg, Rebecca; Rothvoss, Thomas (2017), "Una brecha de integralidad aditiva logarítmica para el empaquetamiento de contenedores", Actas del vigésimo octavo simposio anual ACM-SIAM sobre algoritmos discretos , SIAM, págs. 2616–2625 , arXiv : 1503.08796 , doi : 10.1137/1.9781611974782.172 , ISBN  978-1-61197-478-2, S2CID 1647463 
  33. ↑ Karmarkar, Narendra; Karp, Richard M. (noviembre de 1982). "Un esquema de aproximación eficiente para el problema de empaquetamiento de contenedores unidimensional" . 23.º Simposio Anual sobre Fundamentos de la Informática (SFCS 1982) . págs. 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. ↑ Richard E. Korf (2003), Un algoritmo mejorado para el empaquetamiento óptimo de contenedores . Actas de la Conferencia Internacional Conjunta sobre Inteligencia Artificial, (págs. 1252–1258)
  37. ↑ Schreiber, Ethan L.; Korf, Richard E. (2013), "Improved Bin Completion for Optimal Bin Packing and Number Partitioning" (PDF) , Actas de la Vigésimo Tercera Conferencia Internacional Conjunta sobre Inteligencia Artificial , IJCAI '13, Pekín, China: AAAI Press, pp. 651–658 , ISBN  978-1-57735-633-2
  38. 1 2 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 "Empaquetamiento de contenedores con fragmentación de artículos". Algoritmos y estructuras de datos, 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 (CH), 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 el empaquetado con fragmentación de elementos" . En Erlebach, Thomas; Persinao, Giuseppe (eds.). Aproximación y algoritmos en línea . Lecture Notes in Computer Science. Vol. 3879. Berlín, Heidelberg: Springer. pp. 334–347 . doi : 10.1007/11671411_26 . ISBN   978-3-540-32208-5.
  42. ↑ Ekici, Ali (2021-02-01). "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 (2014-06-01). "Algoritmos de programación matemática para problemas de empaquetamiento de contenedores con fragmentación de artículos" . 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 (2019-03-16). "Optimización entera con valores fraccionarios penalizados: El caso de la mochila" . European Journal of Operational Research . 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 artículos 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" . Journal of the 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 empaquetamiento de contenedores con restricciones de cardinalidad" . Annals of Operations Research . 92 : 335–348 . doi : 10.1023/A:1018947117526 . ISSN 1572-9338 . S2CID 28963291 .  
  48. 1 2 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" . Operations Research . 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 (2019-07-01). "Sobreasignación en servicios en la nube: empaquetamiento de contenedores con restricciones de probabilidad" . Management Science . 65 (7): 3255–3271 . arXiv : 1705.09335 . doi : 10.1287/mnsc.2018.3091 . ISSN 0025-1909 . S2CID 159270392 .  
  50. ↑ Johnson, David S. (2016), "Vector Bin Packing" , en Kao, Ming-Yang (ed.), Encyclopedia of Algorithms , Nueva York, NY: Springer New York, pp. 2319–2323 , doi : 10.1007/978-1-4939-2864-4_495 , ISBN  978-1-4939-2863-7, consultado el 15 de mayo de 2025
  51. ↑ Chung, Yerim; Park, Myoung-Ju (2015-01-01). "Notas sobre problemas inversos de empaquetamiento de contenedores" . Information Processing Letters . 115 (1): 60– 68. doi : 10.1016/j.ipl.2014.09.005 . ISSN 0020-0190 . 
  52. ^ Boyardo, Juana ; Epstein, Leah; Favrholdt, Lene M.; Kohrt, Jens S.; Larsen, Kim S.; Pedersen, Morten M.; Wøhlk, Sanne (11 de octubre de 2006). "El problema del embalaje del contenedor de recursos máximo" . Informática Teórica . 362 (1): 127– 139. doi : 10.1016/j.tcs.2006.06.001 . ISSN 0304-3975 . 
  53. ↑ Huang, Xin; Lu, Pinyan (2020-11-10). "Un marco algorítmico para aproximar la asignación de partes maximin de tareas". arXiv : 1907.04505 [ cs.GT ].
  54. ↑ Ma, Ruixin; Dósa, György; Han, Xin; Ting, Hing-Fung; Ye, Deshi; Zhang, Yong (2013-08-01). "Una nota sobre un problema de empaquetamiento de contenedores egoísta" . Journal of Global Optimization . 56 (4): 1457– 1462. doi : 10.1007/s10898-012-9856-9 . ISSN 0925-5001 . S2CID 3082040 .  
  55. ↑ "Empaquetado de contenedores 3D: El Tetris de la logística" . www.optioryx.com . Consultado el 6 de enero de 2026 .
  56. ↑ Lodi A., Martello S., Monaci, M., Vigo, D. (2010) "Problemas de empaquetamiento de contenedores bidimensionales". En V.Th. Paschos (Ed.), Paradigmas de optimización combinatoria , Wiley/ISTE, pp. 107–129
  57. ↑ Kanavathy LR, Dube E. (2006) Actas de la Sexta Conferencia Internacional IASTED sobre Modelado, Simulación y Optimización, MSO Optimización del empaquetamiento tridimensional de contenedores mediante simulación
  58. ↑ Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010). "Empaquetado/recubrimiento de contenedores con entrega, resuelto con la evolución de algoritmos" . Quinta Conferencia Internacional IEEE de 2010 sobre Computación Bioinspirada: Teorías y Aplicaciones (BIC-TA) . pp. 298–302 . doi : 10.1109/BICTA.2010.5645312 . ISBN  978-1-4244-6437-1.
Lecturas relacionadas
6 articulos
Optimization problemIn mathematics , engineering , computer science and economics , an optimization problem is the problem of finding the best solution from all feasib...RespaldoRespaldoEn tecnología de la información , una copia de seguridad o copia de seguridad de datos es una copia de los datos de una computadora que se toma y s...Circuito integradoCircuito integradoUn circuito integrado ( CI ), también conocido como microchip , chip de computadora o simplemente chip , es un pequeño dispositivo electrónico comp...Matriz de puertas programables en campoMatriz de puertas programables en campoUna matriz de puertas programables en campo ( FPGA ) es un tipo de circuito integrado configurable que se puede programar repetidamente después de ...Dureza NPDiagrama de Euler para conjuntos de problemas P , NP , NP-completos y NP-difíciles. El lado izquierdo es válido bajo el supuesto de que P≠NP , mien...Problema de decisiónUn problema de decisión sólo tiene dos salidas posibles ( sí o no ) en cualquier entrada. En la teoría de la computabilidad y la teoría de la compl...