En el problema del embalaje en contenedores , los artículos de diferentes volúmenes deben empaquetarse en un número finito de contenedores o contenedores, cada uno de un volumen determinado fijo de manera que se minimice el número de contenedores utilizados. En la teoría de la complejidad computacional , es un problema NP-difícil combinatorio . [1] El problema de decisión (decidir si los elementos encajarán en un número específico de contenedores) es NP-completo . [2]
Hay muchas variaciones de este problema, como empaque 2D, empaque lineal, empaque por peso, empaque por costo, etc. Tienen muchas aplicaciones, como llenar contenedores, cargar camiones con limitaciones de capacidad de peso, crear copias de seguridad de archivos en medios y mapeo de tecnología en el diseño de chips semiconductores de matriz de puertas programables en campo .
El problema del embalaje del contenedor también puede verse como un caso especial del problema del material de corte . Cuando el número de contenedores está restringido a 1 y cada artículo se caracteriza por un volumen y 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 .
A pesar de que el problema del empaquetado de contenedores tiene una complejidad computacional NP-hard , se pueden producir soluciones óptimas para casos muy grandes del problema con algoritmos sofisticados. Además, se han desarrollado muchas heurísticas : por ejemplo, el algoritmo de primer ajuste proporciona una solución rápida, pero a menudo no óptima, que implica colocar cada elemento en el primer contenedor en el que quepa. Requiere un tiempo Θ ( n log n ), donde n es el número de elementos que se deben empaquetar. El algoritmo se puede hacer 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 de el algoritmo. Sin embargo, se sabe que siempre existe al menos un pedido de artículos que permite que el primer ajuste produzca una solución óptima. [3]
Una variante de empaquetado en contenedores que ocurre en la práctica es cuando los artículos pueden compartir espacio cuando se empaquetan en un contenedor. Específicamente, un conjunto de artículos podría ocupar menos espacio cuando se empaquetan juntos que la suma de sus tamaños individuales. Esta variante se conoce como empaquetado de VM [4] ya que cuando las máquinas virtuales (VM) se empaquetan en un servidor, su requerimiento total de memoria podría disminuir debido a las páginas compartidas por las VM que solo necesitan ser almacenadas una vez. Si los artículos pueden compartir el espacio de formas arbitrarias, el problema del embalaje del contenedor es difícil de aproximar. Sin embargo, si el espacio compartido encaja en una jerarquía, como es el caso del uso compartido de memoria en máquinas virtuales, el problema de empaquetado de contenedores se puede aproximar de manera eficiente.
Otra variante de embalaje en contenedores de interés en la práctica es el denominado embalaje en contenedores en línea . Aquí se supone que los artículos de diferente volumen llegan secuencialmente, y el tomador de decisiones tiene que decidir si seleccionar y empaquetar el artículo observado actualmente, o dejarlo pasar. Cada decisión es irrevocable. Por el contrario, el embalaje en contenedores fuera de línea permite reorganizar los artículos con la esperanza de lograr un mejor embalaje una vez que lleguen artículos adicionales. Por supuesto, esto requerirá almacenamiento adicional para guardar los artículos que se reorganizarán.
Declaración formal
En Computers and Intractability [5], Garey y Johnson enumeran el problema de empaquetado de contenedores bajo la referencia [SR1]. Definen su variante de decisión de la siguiente manera.
Instancia: conjunto finito de artículos, una talla para cada , una capacidad de bin de enteros positivos y un entero positivo .
Pregunta: ¿Existe una partición de en conjuntos disjuntos tal que la suma de los tamaños de los elementos en cada es ¿o menos?
Tenga en cuenta que en la literatura a menudo se utiliza una notación equivalente, donde y para cada . Además, la investigación está principalmente interesada en la variante de optimización, que solicita el menor valor posible de. Una solución es óptima si tiene un mínimo. La-valor para una solución óptima para un conjunto de elementos se denota por o solo si el conjunto de elementos se desprende del contexto.
Una posible formulación de programación lineal entera del problema es:
minimizar | ||
sujeto a | ||
dónde si bin se usa y si el artículo se pone en la papelera . [6]
Dureza del embalaje del contenedor
El problema del embalaje del contenedor es muy NP-completo . [5] Esto se puede probar reduciendo el problema de las 3 particiones fuertemente NP-completo al embalaje de contenedores. Por otro lado, se puede resolver en tiempo pseudo-polinomial para cada fijo y resoluble en tiempo polinomial para cada fijo . [5] Además, una reducción del problema de la partición muestra que no puede haber un algoritmo de aproximación con una relación de aproximación absoluta menor que a no ser que . [7]
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 el siguiente artículo o incluso si habrá otro. Yao [8] demostró en 1980 que no puede haber un algoritmo en línea con una relación competitiva asintótica menor que. Brown [9] y Liang [10] mejoraron este límite a. Posteriormente, este límite se mejoró parapor Vliet. [11] En 2012, Békési y Galambos volvieron a mejorar este límite inferior [12] para.
Algoritmos de aproximación para el embalaje de contenedores
Para medir el desempeño de un algoritmo de aproximación, hay dos razones de aproximación consideradas en la literatura. Para una lista determinada de elementos el número denota el número de bins usados cuando el algoritmo se aplica a la lista , tiempo denota el número óptimo para esta lista. La relación de rendimiento en el peor de los casos absolutos para un algoritmo Se define como
Por otro lado, la relación asintótica del peor de los casos Se define como
Además, se pueden restringir las listas a aquellas para las que todos los elementos tienen un tamaño de como máximo . Para tales listas, las relaciones de rendimiento de tamaño acotado se denotan como y .
Los algoritmos de aproximación para el embalaje en contenedores se pueden clasificar en dos categorías:
- Heurísticas online, 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 en línea de este problema.
- Heurística fuera de línea, que modifica la lista de elementos dada, 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 mientras mantienen la ventaja de su pequeña complejidad de tiempo. Una subcategoría de la heurística fuera de línea son los esquemas de aproximación asintótica. Estos algoritmos tienen una garantía de aproximación de la forma por alguna constante que puede depender de . Para un arbitrariamente grande estos algoritmos se acercan arbitrariamente a . Sin embargo, esto tiene el costo de una complejidad de tiempo (drásticamente) mayor en comparación con los enfoques heurísticos.
Heurística en línea
Johnson ha estudiado un conjunto diverso de heurísticas en línea y fuera de línea para el embalaje en contenedores. [13] Introdujo las siguientes dos caracterizaciones para la heurística en línea. Un algoritmo es un algoritmo de ajuste cualquiera (AF) si cumple la siguiente propiedad: Se abre un nuevo contenedor para un artículo considerado, solo si no cabe en un contenedor ya abierto. Por otro lado, un algoritmo es un algoritmo de casi cualquier ajuste (AAF) si tiene la propiedad adicional: si un contenedor es el contenedor único con el nivel más bajo distinto de cero, no se puede elegir a menos que el elemento no quepa en cualquier otro contenedor con un nivel distinto de cero. Demostró que cada algoritmo AAF tiene una garantía de aproximación de , lo que significa que tiene una relación de aproximación asintótica de como máximo y que hay listas para que tenga una relación de aproximación asintótica de al menos .
Un algoritmo en línea utiliza un espacio delimitado por k si, para cada nuevo artículo, el número de contenedores en los que puede estar empaquetado es como máximo k. [14] Ejemplos de estos algoritmos son Next-k-Fit y Harmonic-k.
Algoritmo | Garantía de aproximación | Lista de los peores casos | Complejidad temporal |
---|---|---|---|
Siguiente ajuste (NF) | [13] | [13] | |
Primer ajuste (FF) | [15] | [15] | [13] |
Mejor ajuste (BF) | [dieciséis] | [dieciséis] | [13] |
Peor ajuste (WF) | [13] | [13] | [13] |
Casi peor ajuste (AWF) | [13] | [13] | [13] |
Primer ajuste refinado (RFF) | [8] | (por ) [8] | [8] |
Armónico-k (Hk) | por [17] | [17] | [17] |
Armónico refinado (RH) | [17] | [17] | |
Armónico modificado (MH) | [18] | ||
Armónico modificado 2 (MH2) | [18] | ||
Armónico + 1 (H + 1) | [19] | ||
Armónico ++ (H ++) | [19] | [19] |
Siguiente ajuste (NF)
Next Fit (NF) es un algoritmo AF de espacio acotado con solo un contenedor parcialmente lleno que está abierto en cualquier momento. El algoritmo funciona de la siguiente manera. Considera los artículos en un orden definido por una lista.. Si un artículo cabe dentro del contenedor considerado actualmente, el artículo se coloca dentro de él. De lo contrario, el contenedor actual se cierra, se abre un nuevo contenedor y el artículo actual se coloca dentro de este nuevo contenedor.
Este algoritmo fue estudiado por Johnson en esta tesis doctoral [13] en el año 1973. Tiene las siguientes propiedades:
- El tiempo de ejecución puede estar limitado por , dónde es el número de elementos. [13]
- Para cada lista sostiene eso y por lo tanto . [13]
- Para cada existe una lista tal que y . [13]
- para todos . [13]
- para todos . [13]
- Para cada algoritmo que es un algoritmo AF sostiene que . [13]
La intuición a la prueba del límite superior. es el siguiente: El número de bins utilizados por este algoritmo no es más del doble del número óptimo de bins. En otras palabras, es imposible que 2 contenedores estén como mucho medio llenos porque tal posibilidad implica que en algún momento, exactamente un contenedor estaba como máximo medio lleno y se abrió uno nuevo para acomodar un artículo de tamaño como máximo.. Pero dado que el primero tiene al menos un espacio de, el algoritmo no abrirá un nuevo contenedor para ningún artículo cuyo tamaño sea como máximo . Solo después de que el contenedor se llene con más de o si un artículo con un tamaño mayor que llega, el algoritmo puede abrir un nuevo contenedor. Por lo tanto, si tenemos contenedores, al menos los contenedores están llenos a más de la mitad. Por lo tanto,. Porque es un límite inferior del valor óptimo , lo entendemos y por lo tanto . [20]
La familia de listas para las que sostiene que es dado por con . La solución óptima para esta lista tiene contenedores que contienen dos artículos con tamaño y un contenedor con artículos con tamaño (es decir, bins total), mientras que la solución generada por NF tiene contenedores con un artículo de tamaño y un artículo con talla .
Siguiente- k -Fit (NkF)
NkF funciona como NF, pero en lugar de mantener solo un contenedor abierto, el algoritmo mantiene el último los contenedores se abren y elige el primer contenedor en el que cabe el artículo.
Para el NkF ofrece resultados que se mejoran en comparación con los resultados de NF, sin embargo, aumentando a valores constantes mayores que no mejora el algoritmo más en su peor comportamiento. Si algoritmo es un algoritmo AAF y luego . [13]
Primer ajuste (FF)
First-Fit es un algoritmo de AF que procesa los elementos en un orden arbitrario dado . Para cada artículo en, intenta colocar el artículo en el primer contenedor que puede acomodarlo. Si no se encuentra ningún contenedor, abre un nuevo contenedor y coloca el artículo en el nuevo contenedor.
El primer límite superior de para FF fue probado por Ullman [21] en 1971. En 1972, este límite superior se mejoró apor Garey et al. [22] En 1976, fue mejorado por Garey et al. [23] a, que equivale a debido a la integralidad de y . La siguiente mejora, de Xia y Tan [24] en 2010, redujo el límite a. Finalmente en 2013, este límite se mejoró parapor Dósa y Sgall. [15] También presentan una lista de entrada de ejemplo., para eso coincide con este límite.
Mejor ajuste (BF)
Best-fit es un algoritmo AAF similar al First-fit. En lugar de colocar el siguiente artículo en el primer contenedor, donde cabe, se coloca dentro del contenedor que tiene la carga máxima, donde cabe el artículo.
El primer límite superior de para BF fue probado por Ullman [21] en 1971. Este límite superior se mejoró parapor Garey et al. [22] Posteriormente, fue mejorado por Garey et al. [23] a. Finalmente, este límite se mejoró parapor Dósa y Sgall. [16] También presentan una lista de entrada de ejemplo., para eso coincide con este límite.
Peor ajuste (WF)
Este algoritmo es similar a Best-fit. en lugar de colocar el artículo dentro del contenedor con la carga máxima, el artículo se coloca dentro del contenedor con la carga mínima.
Este algoritmo puede comportarse tan mal como Next-Fit y lo hará en la lista del peor de los casos para eso. . [13] Además, sostiene que. Dado que WF es un algoritmo AF, existe un algoritmo AF tal que. [13]
Casi peor ajuste (AWF)
AWF es un algoritmo AAF que considera los elementos en orden de una lista determinada . Intenta llenar el siguiente artículo dentro del segundo contenedor abierto más vacío (o contenedor más vacío si hay dos contenedores de este tipo). Si no encaja, intenta el más vacío, y si tampoco encaja allí, el algoritmo abre un nuevo contenedor. Como AWF es un algoritmo AAF, tiene una relación asintótica en el peor de los casos de. [13]
Primer ajuste refinado (RFF)
Los elementos se clasifican en cuatro clases. Un articulo se llama -trozo, -trozo, -pieza, o -pieza, si su tamaño está en el intervalo , , , o respectivamente. Del mismo modo, los contenedores se clasifican en cuatro clases. Dejarser un número entero fijo. El siguiente elemento se asigna debido a las siguientes reglas: Se coloca usando First-Fit en un contenedor en
- Clase 1, si es un -trozo,
- Clase 2, si es un -trozo,
- Clase 3, si es un -pieza, pero no elth -pieza vista hasta ahora, para cualquier número entero .
- Clase 1, si es el th - pieza vista hasta ahora,
- Clase 4, si es un -trozo.
Tenga en cuenta que este algoritmo no es un algoritmo de ajuste cualquiera, 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, [8] quien demostró que tiene una garantía de aproximación de y presentó una familia de listas con por .
Armónica- k
El algoritmo Harmonic- k divide el intervalo de tamaños armónicamente en piezas por y tal que . Un articulo se llama un -artículo, si . El algoritmo divide el conjunto de contenedores vacíos en clases infinitas por , un tipo de contenedor para cada tipo de artículo. Una papelera de tipo solo se usa para contenedores para empacar artículos de tipo . Cada contenedor de tipo por puede contener exactamente -artículos. El algoritmo ahora actúa de la siguiente manera: si el siguiente elemento es un -artículo para , el artículo se coloca en el primero (solo abierto) contenedor que contiene menos de pedazos o abre uno nuevo si no existe tal contenedor. Si el siguiente elemento es un -item, el algoritmo lo coloca en los contenedores de tipo utilizando Next-Fit.
Este algoritmo fue descrito por primera vez por Lee y Lee. [17] Tiene una complejidad temporal de y en cada paso, hay como máximo bins abiertos que se pueden usar potencialmente para colocar elementos, es decir, es un algoritmo de espacio delimitado por k. Además, estudiaron su razón de aproximación asintótica. Ellos definieron una secuencia, por y demostró que para sostiene eso . Para sostiene eso . Además, presentaron una familia de ejemplos del peor de los casos para ese
Armónico refinado (RH)
Refined-Harmonic combina ideas del algoritmo Harmonic-k con ideas de Refined-First-Fit. Coloca los elementos más grandes quesimilar a 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 más grandes que.
El algoritmo clasifica los elementos con respecto a los siguientes intervalos: , , , , , por , y . El algoritmo coloca el-artículos como en Harmonic-k, mientras que sigue una estrategia diferente para los elementos en y . Hay cuatro posibilidades para empacar-artículos y -artículos en contenedores.
- Un -bin contiene solo uno -Articulo.
- Un -bin contiene solo uno -Articulo.
- Un -bin contiene uno -artículo y uno -Articulo.
- Un -bin contiene dos -artículos.
Un -bin denota un bin que está designado para contener un segundo -Articulo. El algoritmo usa los números N_a, N_b, N_ab, N_bb y N_b 'para contar el número de bins correspondientes en la solución. Además, N_c = N_b + N_ab
Algoritmo refinado-armónico-k para una lista L = (i_1, \ dots i_n):1. N_a = N_b = N_ab = N_bb = N_b '= N_c = 02. Si i_j es una pieza I_k luego usa el algoritmo Harmonic-k para empaquetarlo3. de lo contrario, si i_j es un elemento I_a entonces si N_b! = 1, luego empaquete i_j en cualquier J_b-bin; Nótese bien--; N_ab ++; de lo contrario, coloque i_j en un contenedor nuevo (vacío); N_a ++;4. de lo contrario, si i_j es un elemento I_b entonces si N_b '= 1 luego coloque i_j en el I_b'-bin; N_b '= 0; N_bb ++;5. de lo contrario, si N_bb <= 3N_c luego coloque i_j en un nuevo contenedor y designelo como I_b'-bin; N_b '= 1 de lo contrario si N_a! = 0 luego coloque i_j en cualquier I_a-bin; N / A--; N_ab ++; N_c ++ de lo contrario, coloque i_j en un nuevo contenedor; N_b ++; N_c ++
Este algoritmo fue descrito por primera vez por Lee y Lee. [17] Demostraron que para sostiene eso .
Algoritmos sin conexión
Algoritmo | Garantía de aproximación | Peor caso |
---|---|---|
Disminución de primer ajuste (FFD) | [25] | [25] |
Disminución de primer ajuste modificado (MFFD) | [26] | [27] |
Hoberg y Rothvoss [28] |
Disminución del primer ajuste (FFD)
Este algoritmo funciona de forma análoga a First-Fit. Sin embargo, antes de comenzar a colocar los elementos, se ordenan en orden no creciente de sus tamaños. Este algoritmo se puede implementar para tener un tiempo de ejecución de como máximo.
En 1973, DS Johnson demostró en sus tesis doctorales [13] que. En 1985, BS Backer [29] dio una prueba un poco más simple y mostró que la constante aditiva no es más de 3. Yue Minyi [30] demostró que en 1991 y, en 1997, mejoró este análisis para junto con Li Rongheng. [31] En 2007 György Dósa [25] demostró el límite estrecho y presentó un ejemplo para el cual .
El ejemplo de límite inferior dado por Dósa [25] es el siguiente: Considere las dos configuraciones de ubicación y . Si hay 4 copias de y 2 copias de en la solución óptima, FFD calculará los siguientes contenedores: 4 contenedores con configuración , un contenedor con configuración , un contenedor con configuración , un contenedor con configuración , y un contenedor final con configuración , es decir, 8 contenedores en total, mientras que el óptimo tiene solo 6 contenedores. Por lo tanto, el límite superior es estrecho, porque. Este ejemplo se puede extender a todos los tamaños de. [25]
Disminución de primer ajuste modificado (MFFD)
La reducción de primer ajuste modificada (MFFD) [27] mejora la FFD para artículos de más de medio contenedor al clasificar los artículos por tamaño en cuatro clases de tamaño: grande, mediano, pequeño y minúsculo, correspondientes a artículos con tamaño> 1/2 contenedor,> 1/3 de recipiente,> 1/6 de recipiente y artículos más pequeños respectivamente. Luego procede a través de cinco fases:
- Asigne un contenedor para cada artículo grande, ordenado de mayor a menor.
- Continúe hacia adelante a través de los contenedores. En cada uno: Si el elemento mediano restante más pequeño no cabe, omita este contenedor. De lo contrario, coloque el elemento mediano restante más grande que se ajuste.
- Continúe hacia atrás a través de los contenedores que no contienen un artículo mediano. En cada uno: Si los dos artículos pequeños más pequeños que quedan no caben, omita este contenedor. De lo contrario, coloque el elemento pequeño restante más pequeño y el elemento pequeño restante más grande que quepa.
- Continúe hacia adelante a través de todos los contenedores. Si el artículo restante más pequeño de cualquier clase de tamaño no encaja, omita este contenedor. De lo contrario, coloque el artículo más grande que quepa y permanezca en este contenedor.
- Utilice FFD para empaquetar los artículos restantes en contenedores nuevos.
Este algoritmo fue estudiado por primera vez por Johnson y Garey [27] en 1985, donde demostraron que. Este límite fue mejorado en el año 1995 por Yue y Zhang [26] quienes demostraron que.
Esquemas de aproximación asintótica
Fernández de la Vega y Lueker [32] presentaron el primer PTAS para embalaje en contenedores. Para cada, su algoritmo encuentra una solución con tamaño como máximo y corre a tiempo , dónde denota una función que solo depende de .
Karmarkar y Karp [33] mejoraron la complejidad temporal de este algoritmo a polinomio en y . Su algoritmo encuentra una solución con tamaño como máximo.
Rothvoss [34] presentó un algoritmo que genera una solución con tamaño como máximo.
Hoberg y Rothvoss [35] mejoraron este algoritmo para generar una solución con tamaño como máximo. El algoritmo es aleatorio y su tiempo de ejecución es polinomial en el número total de elementos.
Algoritmo exacto
Martello y Toth [36] desarrollaron un algoritmo exacto para el problema de empaquetado de contenedores 1-D, llamado MTP. Una alternativa más rápida es el algoritmo Bin Completion propuesto por Korf en 2002 [37] y posteriormente mejorado. [38]
Schreiber y Korf presentaron una mejora adicional en 2013. [39] Se muestra que el nuevo algoritmo de finalización de contenedor mejorado es hasta cinco órdenes de magnitud más rápido que la finalización de contenedor en problemas no triviales con 100 elementos, y supera al BCP (rama -and-cut-and-price) de Belov y Scheithauer en problemas que tienen menos de 20 contenedores como solución óptima. Qué algoritmo 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.
Implementaciones
- El paquete de empaquetado contiene algoritmos codiciosos en Python para resolver dos problemas típicos de empaquetado de contenedores: (i) empaquetar artículos en un número constante de contenedores, (ii) empaquetar artículos en un número bajo de contenedores de tamaño constante. [40]
- El paquete OR-tools contiene algoritmos de empaquetado bin en C ++, con envoltorios en Python, C # y Java.
Problemas relacionados
En el problema del embalaje de contenedores, el tamaño de los contenedores es fijo y su número puede ampliarse (pero debe ser lo más pequeño posible).
Por el contrario, en el problema de la partición de números de múltiples vías , el número de contenedores es fijo y su tamaño se puede ampliar. El objetivo es encontrar una partición en la que los tamaños de los contenedores sean lo más parecidos posible (en la variante denominada problema de programación de multiprocesador o problema de intervalo mínimo , el objetivo es específicamente minimizar el tamaño del contenedor más grande).
En el problema de empaquetado inverso de contenedores , [41] 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 se puedan empaquetar en el número prescrito de contenedores.
En el problema de empaquetado del contenedor de recursos máximos , [42] el objetivo es maximizar el número de contenedores utilizados, de modo que, para algunos pedidos de contenedores, ningún artículo de un contenedor posterior quepa en un contenedor anterior. En un problema dual, el número de contenedores es fijo y el objetivo es minimizar el número total o el tamaño total de los artículos colocados en los contenedores, de modo que ningún artículo restante quepa en un contenedor sin llenar.
En el problema de la cubierta del contenedor , el tamaño del contenedor está delimitado desde abajo : 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 determinado.
En el problema de asignación equitativa de tareas indivisibles (una variante de la asignación equitativa de elementos ), los elementos representan tareas y hay diferentes personas, cada una de las cuales atribuye un valor de dificultad diferente a cada tarea. El objetivo es asignar a cada persona un conjunto de tareas con un límite superior en su valor de dificultad total (por lo tanto, cada persona corresponde a un contenedor). En este problema también se utilizan muchas técnicas de embalaje en contenedores. [43]
En el problema del corte con guillotina , tanto los artículos como los "contenedores" son rectángulos bidimensionales en lugar de números unidimensionales, y los artículos deben cortarse del contenedor utilizando cortes de extremo a extremo.
Referencias
- ^ 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.
- ^ Barrington, David Mix (2006). "Bin Packing" . Archivado desde el original el 16 de febrero de 2019 . Consultado el 27 de febrero de 2016 .
- ^ Lewis 2009
- ^ Sindelar, Sitaraman y Shenoy 2011 , págs. 367–378
- ^ a b c Garey, M. R .; Johnson, D. S. (1979). Victor Klee (ed.). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . Una serie de libros de ciencias matemáticas. San Francisco, California: W. H. Freeman and Co. págs. X + 338 . ISBN 0-7167-1045-5. Señor 0519066 .
- ^ Martello y Toth 1990 , p. 221
- ^ Vazirani, Vijay V. (14 de marzo de 2013). Algoritmos de aproximación . Springer Berlín Heidelberg. pag. 74. ISBN 978-3662045657.
- ^ a b c d e Yao, Andrew Chi-Chih (abril de 1980). "Nuevos algoritmos para el embalaje de contenedores". Revista de la ACM . 27 (2): 207–227. doi : 10.1145 / 322186.322187 . S2CID 7903339 .
- ^ Donna J, Brown (1979). "Un límite inferior para algoritmos de embalaje de contenedores unidimensionales en línea" (PDF) . Rept . Técnico
- ^ Liang, Frank M. (1980). "Un límite inferior para el embalaje de contenedores en línea". Cartas de procesamiento de información . 10 (2): 76–79. doi : 10.1016 / S0020-0190 (80) 90077-0 .
- ^ van Vliet, André (1992). "Un límite inferior mejorado para los algoritmos de empaquetado de contenedores en línea". Cartas de procesamiento de información . 43 (5): 277–284. doi : 10.1016 / 0020-0190 (92) 90223-I .
- ^ Balogh, János; Békési, József; Galambos, Gábor (julio de 2012). "Nuevos límites inferiores para ciertas clases de algoritmos de empaquetado de contenedores" . Informática Teórica . 440–441: 1–13. doi : 10.1016 / j.tcs.2012.04.017 .
- ^ a b c d e f g h i j k l m n o p q r s t u v w Johnson, David S (1973). "Algoritmos de empaquetado de contenedores casi óptimos" (PDF) . Instituto de Tecnología de Massachusetts .
- ^ 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 . ISBN 9781498770156.
- ^ a b c Dósa, György; Sgall, Jiri (2013). "Embalaje de contenedores First Fit: un análisis riguroso" . 30º Simposio Internacional sobre Aspectos Teóricos de la Informática (STACS 2013) . Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 20 : 538–549. doi : 10.4230 / LIPIcs.STACS.2013.538 .
- ^ a b c György, Dósa; Sgall, Jirí (2014). "Análisis óptimo del embalaje de contenedores de mejor ajuste". {Autómatas, lenguajes y programación - 41º Coloquio Internacional (ICALP)} . Apuntes de conferencias en Ciencias de la Computación. 8572 : 429–441. doi : 10.1007 / 978-3-662-43948-7_36 . ISBN 978-3-662-43947-0.
- ^ a b c d e f g Lee, CC; Lee, DT (julio de 1985). "Un simple algoritmo de empaquetado de contenedores en línea". Revista de la ACM . 32 (3): 562–572. doi : 10.1145 / 3828.3833 . S2CID 15441740 .
- ^ a b Ramanan, Prakash; Brown, Donna J; Lee, CC; Lee, DT (septiembre de 1989). "Envasado de contenedores en línea en tiempo lineal". Revista de algoritmos . 10 (3): 305–326. doi : 10.1016 / 0196-6774 (89) 90031-X . hdl : 2142/74206 .
- ^ a b c Seiden, Steven S. (2002). "Sobre el problema del embalaje de contenedores en línea". Revista de la ACM . 49 (5): 640–671. doi : 10.1145 / 585265.585269 . S2CID 14164016 .
- ^ Vazirani 2003 , p. 74.
- ^ a b Ullman, JD (1971). "El rendimiento de un algoritmo de asignación de memoria". Informe técnico 100 Princeton Univ .
- ^ a b Garey, M. R; Graham, R. L; Ullman, JD (1972). "Análisis del peor de los casos de algoritmos de asignación de memoria | Actas del cuarto simposio anual ACM sobre teoría de la computación". Actas del Cuarto Simposio Anual de ACM sobre Teoría de la Computación : 143–150. doi : 10.1145 / 800152.804907 . S2CID 26654056 .
- ^ a b Garey, M. R; Graham, R. L; Johnson, D. S; Yao, Andrew Chi-Chih (1976). "Programación con recursos limitados como embalaje en contenedores generalizados". Revista de Teoría Combinatoria, serie A . 21 (3): 257-298. doi : 10.1016 / 0097-3165 (76) 90001-7 . ISSN 0097-3165 .
- ^ Xia, Binzhou; Tan, Zhiyi (agosto de 2010). "Límites más estrictos del algoritmo First Fit para el problema de embalaje de contenedores". Matemáticas aplicadas discretas . 158 (15): 1668–1675. doi : 10.1016 / j.dam.2010.05.026 .
- ^ a b c d e Dósa, György (2007). "El límite estrecho del algoritmo de empaquetado decreciente de primer ajuste es FFD (I) ≤ 11 / 9OPT (I) + 6/9". Combinatoria, Algoritmos, Metodologías Probabilísticas y Experimentales. ESCAPE . doi : 10.1007 / 978-3-540-74450-4_1 .
- ^ a b Yue, Minyi; Zhang, Lei (julio de 1995). "Una prueba simple de la desigualdad MFFD (L) ≤ 71/60 OPT (L) + 1, L para el algoritmo de empaquetado de contenedores MFFD". Acta Mathematicae Applicatae Sinica . 11 (3): 318–330. doi : 10.1007 / BF02011198 . S2CID 118263129 .
- ^ a b c Johnson, David S; Garey, Michael R (octubre de 1985). "Un teorema de 7160 para el embalaje de contenedores" . Revista de complejidad . 1 (1): 65–106. doi : 10.1016 / 0885-064X (85) 90022-6 .
- ^ Hoberg, Rebecca; Rothvoss, Thomas (2017-01-01), "A Logarithmic Additive Integrality Gap for Bin Packing" , Actas del Simposio anual ACM-SIAM de 2017 sobre algoritmos discretos , Actas, Society for Industrial and Applied Mathematics, págs. 2616–2625, doi : 10.1137 / 1.9781611974782.172 , ISBN 978-1-61197-478-2, consultado el 22-11-2020
- ^ Baker, Brenda S. (1985). "Una nueva prueba para el algoritmo de embalaje de contenedores de reducción de primer ajuste". J. Algoritmos . 6 (1): 49–70. doi : 10.1016 / 0196-6774 (85) 90018-5 .
- ^ Yue, Minyi (octubre de 1991). "Una prueba simple de la desigualdad FFD (L) ≤ 11/9 OPT (L) + 1, ∀L para el algoritmo de empaquetado de contenedores FFD". Acta Mathematicae Applicatae Sinica . 7 (4): 321–331. doi : 10.1007 / BF02009683 . S2CID 189915733 .
- ^ Li, Rongheng; Yue, Minyi (agosto de 1997). "La prueba de FFD (L) <-OPT (L) + 7/9". Boletín de ciencia china . 42 (15): 1262–1265. Código Bibliográfico : 1997ChSBu..42.1262L . doi : 10.1007 / BF02882754 . S2CID 93280100 .
- ^ Fernández de la Vega, W .; Lueker, GS (1981). "El empaquetamiento de contenedores se puede resolver dentro de 1 + ε en tiempo lineal". Combinatorica . 1 (4): 349–355. doi : 10.1007 / BF02579456 . ISSN 1439-6912 . S2CID 10519631 .
- ^ Karmarkar, Narendra; Karp, Richard M. (noviembre de 1982). "Un esquema de aproximación eficiente para el problema de embalaje de contenedores unidimensionales" . 23º Simposio anual sobre los fundamentos de la informática (SFCS 1982) : 312–320. doi : 10.1109 / SFCS.1982.61 . S2CID 18583908 .
- ^ Rothvoß, T. (1 de octubre de 2013). "Aproximación del embalaje de contenedores dentro de los contenedores O (log OPT * Log Log OPT)" . 54º Simposio Anual de IEEE 2013 sobre los fundamentos de la informática : 20–29. arXiv : 1301.4010 . doi : 10.1109 / FOCS.2013.11 . ISBN 978-0-7695-5135-7. S2CID 15905063 .
- ^ Hoberg, Rebecca; Rothvoss, Thomas (2017-01-01), "A Logarithmic Additive Integrality Gap for Bin Packing" , Actas del Simposio anual ACM-SIAM de 2017 sobre algoritmos discretos , Actas, Society for Industrial and Applied Mathematics, págs. 2616–2625, doi : 10.1137 / 1.9781611974782.172 , ISBN 978-1-61197-478-2, S2CID 1647463 , consultado el 10 de febrero de 2021
- ^ Martello y Toth 1990 , págs. 237-240.
- ^ Korf 2002
- ^ RE Korf (2003), Un algoritmo mejorado para un empaquetado óptimo en contenedores . Actas de la Conferencia conjunta internacional sobre inteligencia artificial, (págs. 1252-1258)
- ^ Schreiber y Korf 2013
- ^ Vaccaro, Alessio (13 de noviembre de 2020). "🧱 4 pasos para asignar recursos fácilmente con Python & Bin Packing" . Medio . Consultado el 21 de marzo de 2021 .
- ^ Chung, Yerim; Park, Myoung-Ju (1 de enero de 2015). "Notas sobre problemas de embalaje de contenedores inversos" . Cartas de procesamiento de información . 115 (1): 60–68. doi : 10.1016 / j.ipl.2014.09.005 . ISSN 0020-0190 .
- ^ Boyar, Joan; Epstein, Leah; Favrholdt, Lene M .; Kohrt, Jens S .; Larsen, Kim S .; Pedersen, Morten M .; Wøhlk, Sanne (11 de octubre de 2006). "El problema de embalaje del contenedor de recursos máximos" . Informática Teórica . 362 (1): 127-139. doi : 10.1016 / j.tcs.2006.06.001 . ISSN 0304-3975 .
- ^ Huang, Xin; Lu, Pinyan (10 de noviembre de 2020). "Un marco algorítmico para aproximar la asignación de tareas de Maximin Share". arXiv : 1907.04505 [ cs.GT ].
Bibliografía
- Korf, Richard E. (2002), Un nuevo algoritmo para el empaquetado óptimo de contenedores. (PDF)
- Vazirani, Vijay V. (2003), Algoritmos de aproximación , Berlín: Springer, ISBN 3-540-65367-8
- Yue, Minyi (octubre de 1991), "Una prueba simple de la desigualdad FFD (L) ≤ 11/9 OPT (L) + 1, ∀L para el algoritmo de empaquetado de contenedores FFD", Acta Mathematicae Applicatae Sinica , 7 (4) : 321–331, doi : 10.1007 / BF02009683 , ISSN 0168-9673 , S2CID 189915733
- Dósa, György (2007). "El límite estrecho del algoritmo de empaquetado decreciente de primer ajuste es FFD (I) ≤ (11/9) OPT (I) +6/9". En Chen, Bo; Paterson, Mike; Zhang, Guochuan (eds.). Combinatoria, Algoritmos, Metodologías Probabilísticas y Experimentales . Apuntes de conferencias en Ciencias de la Computación. 7000 (2011) . Apuntes de conferencias en Ciencias de la Computación. 4614/2007. Springer Berlín / Heidelberg. págs. 1-11. doi : 10.1007 / 978-3-540-74450-4 . ISBN 978-3-540-74449-8. ISSN 0302-9743 .
- Xia, Binzhou; Tan, Zhiyi (2010), "Límites más estrictos del algoritmo First Fit para el problema de empaquetado de contenedores", Discrete Applied Mathematics , 158 (15): 1668–1675, doi : 10.1016 / j.dam.2010.05.026 , ISSN 0166 -218X
- Garey, Michael R .; Johnson, David S. (1985), "Un teorema 71/60 para el empaquetado de contenedores * 1", Journal of Complexity , 1 : 65-106, doi : 10.1016 / 0885-064X (85) 90022-6
- Yue, Minyi; Zhang, Lei (julio de 1995), "Una prueba simple de la desigualdad MFFD (L) ≤ 71/60 OPT (L) + 1, L para el algoritmo de empaquetado de contenedores MFFD", Acta Mathematicae Applicatae Sinica , 11 (3): 318–330, doi : 10.1007 / BF02011198 , ISSN 0168-9673 , S2CID 118263129
- Fernández de la Vega, W .; Lueker, GS (diciembre de 1981), "El empaquetamiento en contenedores se puede resolver dentro de 1 + ε en tiempo lineal", Combinatorica , Springer Berlin / Heidelberg, 1 (4): 349–355, doi : 10.1007 / BF02579456 , ISSN 0209-9683 , S2CID 10519631
- Lewis, R. (2009), "Un método de escalada de colinas de propósito general para problemas de agrupación mínima independientes de pedidos: un estudio de caso sobre coloración de gráficos y empaquetado en contenedores" (PDF) , Computers and Operations Research , 36 (7): 2295– 2310, doi : 10.1016 / j.cor.2008.09.004
- Martello, Silvano; Toth, Paolo (1990), "Problema de embalaje de contenedores" (PDF) , Problemas de mochila: algoritmos e implementaciones informáticas , Chichester, Reino Unido: John Wiley and Sons, ISBN 0471924202
- Michael R. Garey y David S. Johnson (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness. WH Freeman. ISBN 0-7167-1045-5 . A4.1: SR1, pág. 226.
- David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, MR Garey, Ronald L. Graham. Límites de rendimiento en el peor de los casos para algoritmos de empaque unidimensionales simples . SICOMP, Volumen 3, Número 4. 1974.
- Lodi A., Martello S., Monaci, M., Vigo, D. (2010) "Problemas de embalaje bidimensional de contenedores". En V.Th. Paschos (Ed.), Paradigmas de optimización combinatoria , Wiley / ISTE, págs. 107-129
- Dósa, György; Sgall, Jiří (2013). "Embalaje de contenedores First Fit: un análisis riguroso" . 30º Simposio Internacional sobre Aspectos Teóricos de la Informática (STACS 2013) . Dagstuhl, Alemania. págs. 538–549. ISBN 978-3-939897-50-7.
- Benkő A., Dósa G., Tuza Z. (2010) " Bin Packing / Covering with Delivery, Resolved with the Evolution of Algorithms ", Actas 2010 IEEE 5ta Conferencia Internacional sobre Computación Bioinspirada: Teorías y Aplicaciones, BIC-TA 2010 , Arte. No. 5645312, págs. 298-302.
- Sindelar, Michael; Sitaraman, Ramesh ; Shenoy, Prashant (2011), "Sharing-Aware Algorithms for Virtual Machine Colocation" (PDF) , Actas del 23 ° Simposio de ACM sobre paralelismo en algoritmos y arquitecturas (SPAA), San José, CA, junio de 2011 : 367–378
- Schreiber, Ethan L .; Korf, Richard E. (2013), Compleción mejorada de contenedores para un empaquetado óptimo de contenedores y partición de números , IJCAI '13, Beijing, China: AAAI Press, págs. 651–658, ISBN 978-1-57735-633-2
enlaces externos
- Optimización del embalaje de contenedores tridimensionales
- Implementación de 7 algoritmos clásicos de empaquetado de contenedores aproximados en C con resultados e imágenes
- PHP Class para empaquetar archivos sin exceder un límite de tamaño dado
- Una implementación de varias heurísticas de empaquetado de contenedores en Haskell , incluidas FFD y MFFD.
- Visualización de heurísticas para el empaquetado de contenedores 1D y 2D
- Marco de investigación de algoritmos de corte y embalaje , que incluye una serie de algoritmos de embalaje de contenedores y datos de prueba.
- Un algoritmo sencillo de empaquetado de contenedores en línea
- Fpart: herramienta de línea de comandos de código abierto para empaquetar archivos (con licencia C, BSD)
- Algoritmo solucionador de material de corte y empaquetado en contenedores