stringtranslate.com

Problema de embalaje del contenedor

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

Computacionalmente, el problema es NP-hard , y el problema de decisión correspondiente , decidir si los elementos pueden caber en un número específico de contenedores, es NP-completo . A pesar de su dificultad en el peor de los casos, se pueden producir soluciones óptimas para instancias muy grandes del problema con algoritmos sofisticados. Además, existen muchos algoritmos de aproximación . Por ejemplo, el algoritmo de primer ajuste proporciona una solución rápida pero a menudo no óptima, que implica colocar cada elemento en el primer contenedor en el que encajará. Requiere Θ ( n  log  n ) tiempo, donde n es el número de elementos a empaquetar. El algoritmo puede hacerse mucho más efectivo ordenando primero la lista de elementos en orden decreciente (a veces conocido como el algoritmo decreciente de primer ajuste), aunque esto todavía no garantiza una solución óptima y para listas más largas puede aumentar el tiempo de ejecución del algoritmo. Sin embargo, se sabe que siempre existe al menos un ordenamiento de elementos que permite que el primer ajuste produzca una solución óptima. [6]

Existen muchas variantes de este problema, como el empaquetado en 2D, el empaquetado lineal, el empaquetado por peso, el empaquetado por costo, etc. El problema del empaquetado en contenedores también puede considerarse un caso especial del problema del stock de corte . Cuando el número de contenedores se limita a 1 y cada artículo se caracteriza tanto por un volumen como por un valor, el problema de maximizar el valor de los artículos que caben en el contenedor se conoce como el problema de la mochila .

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

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

Declaración formal

En Computers and Intractability [8] : 226,  Garey y Johnson enumeran el problema de empaquetamiento de contenedores bajo la referencia [SR1]. Definen su variante de decisión de la siguiente manera.

Instancia: Conjunto finito de elementos, un tamaño para cada uno , una capacidad de contenedor de número entero positivo y un número entero positivo .

Pregunta: ¿Existe una partición en conjuntos disjuntos tal que la suma de los tamaños de los elementos en cada uno sea o menor?

Tenga en cuenta que en la literatura a menudo se utiliza una notación equivalente, donde y para cada . Además, la investigación se interesa principalmente por la variante de optimización, que solicita el valor más pequeño posible de . Una solución es óptima si tiene un mínimo de . El valor de una solución óptima para un conjunto de elementos se denota por o simplemente si el conjunto de elementos se desprende claramente del contexto.

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

donde si se utiliza el contenedor y si el artículo se coloca en el contenedor . [9]

Dureza del embalaje del contenedor

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

Además, no puede haber ningún algoritmo de aproximación con una razón de aproximación absoluta menor que a menos que . Esto se puede demostrar mediante una reducción del problema de partición : [10] dada una instancia de Partición donde la suma de todos los números de entrada es , construya una instancia de empaquetamiento de bins en la que el tamaño del bin sea T . Si existe una partición igual de las entradas, entonces el empaquetamiento óptimo necesita 2 bins; por lo tanto, cada algoritmo con una razón de aproximación menor que 3/2 debe devolver menos de 3 contenedores, que deben ser 2 contenedores. Por el contrario, si no hay una partición equitativa de las entradas, entonces el empaquetamiento óptimo necesita al menos 3 contenedores.

Por otra parte, el empaquetamiento de contenedores se puede resolver en tiempo pseudopolinomial para cualquier número fijo de contenedores K , y se puede resolver en tiempo polinomial para cualquier capacidad fija de contenedor B. [8]

Algoritmos de aproximación para el empaquetamiento de contenedores

Para medir el rendimiento de un algoritmo de aproximación, en la literatura se consideran dos ratios de aproximación. Para una lista dada de elementos, el número denota el número de contenedores utilizados cuando se aplica el algoritmo a la lista , mientras que denota el número óptimo para esta lista. El ratio de rendimiento absoluto en el peor de los casos para un algoritmo se define como

Por otra parte, la razón asintótica del peor caso se define como

De manera equivalente, es el número más pequeño tal que existe alguna constante K, tal que para todas las listas L: [4]

.

Además, se pueden restringir las listas a aquellas en las que todos los elementos tienen un tamaño de como máximo . Para dichas listas, las relaciones de rendimiento de tamaño limitado se indican como y .

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

  1. Heurísticas en línea, que consideran los elementos en un orden determinado y los colocan uno por uno dentro de los contenedores. Estas heurísticas también son aplicables a la versión fuera de línea de este problema.
  2. Heurísticas fuera de línea, que modifican la lista dada de elementos, por ejemplo, ordenando los elementos por tamaño. Estos algoritmos ya no son aplicables a la variante en línea de este problema. Sin embargo, tienen una garantía de aproximación mejorada al tiempo que mantienen la ventaja de su pequeña complejidad temporal. Una subcategoría de heurísticas fuera de línea son los esquemas de aproximación asintótica. Estos algoritmos tienen una garantía de aproximación de la forma para alguna constante que puede depender de . Para un valor arbitrariamente grande, estos algoritmos se acercan arbitrariamente a . Sin embargo, esto tiene el costo de una complejidad temporal (drásticamente) mayor en comparación con los enfoques heurísticos.

Heurística en línea

En la versión en línea del problema de empaquetado de contenedores, los artículos llegan uno tras otro y la decisión (irreversible) de dónde colocar un artículo debe tomarse antes de saber cuál será el siguiente o incluso si habrá otro. David S. Johnson ha estudiado un conjunto diverso de heurísticas en línea y fuera de línea para el empaquetado de contenedores en su tesis doctoral. [11]

Algoritmos de clase única

Hay muchos algoritmos simples que utilizan el siguiente esquema general:

Los algoritmos difieren en el criterio con el que eligen el contenedor abierto para el nuevo artículo en el paso 1 (consulte las páginas vinculadas para obtener más información):

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 

Algoritmos refinados

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

Límites inferiores generales para algoritmos en línea

Yao [15] demostró en 1980 que no puede haber ningún algoritmo en línea con una relación competitiva asintótica menor que . Brown [17] y Liang [18] mejoraron este límite a1.536 35 . Posteriormente, este límite se mejoró a1.540 14 por Vliet. [19] En 2012, este límite inferior fue mejorado nuevamente por Békési y Galambos [20] a .

Tabla comparativa

Algoritmos offline

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

Aproximación multiplicativa

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

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

.

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

Fernández de la Vega y Lueker [29] presentaron un PTAS para empaquetamiento de bins. Para cada , su algoritmo encuentra una solución con tamaño como máximo y se ejecuta en tiempo , donde denota una función que solo depende de . Para este algoritmo, inventaron el método de redondeo de entrada adaptativo : los números de entrada se agrupan y se redondean al valor máximo en cada grupo. Esto produce una instancia con un pequeño número de tamaños diferentes, que se puede resolver exactamente utilizando el programa lineal de configuración . [30]

Aproximación aditiva

El algoritmo de empaquetamiento de contenedores Karmarkar-Karp encuentra una solución con un tamaño como máximo y se ejecuta en un polinomio de tiempo en n (el polinomio tiene un grado alto, al menos 8).

Rothvoss [31] presentó un algoritmo que genera una solución con un máximo de contenedores.

Hoberg y Rothvoss [32] mejoraron este algoritmo para generar una solución con un máximo de bins. El algoritmo es aleatorio y su tiempo de ejecución es polinómico en n .

Tabla comparativa

Algoritmos exactos

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

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

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

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

Empaquetamiento con fragmentación

El empaquetamiento de contenedores con fragmentación o el empaquetamiento de contenedores de objetos fragmentables es una variante del problema del empaquetamiento de contenedores en el que se permite dividir los elementos en partes y colocar cada parte por separado en un contenedor diferente. Dividir los elementos en partes puede permitir mejorar el rendimiento general, por ejemplo, minimizando el número total de contenedores. Además, el problema computacional de encontrar un cronograma óptimo puede volverse más fácil, ya que algunas de las variables de optimización se vuelven continuas. Por otro lado, dividir los elementos en partes puede ser costoso. El problema fue introducido por primera vez por Mandal, Chakrabary y Ghose. [38]

Variantes

El problema tiene dos variantes principales.

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

Complejidad computacional

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

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

Bertazzi, Golden y Wang [40] introdujeron una variante de BP-SIF con regla de división: se permite dividir un elemento de una sola manera según su tamaño. Esto es útil para el problema de enrutamiento de vehículos, por ejemplo. En su artículo, proporcionan el límite de rendimiento en el peor de los casos de la variante.

Shachnai, Tamir y Yehezkeli [41] desarrollaron esquemas de aproximación para BP-SIF y BP-SPF; un PTAS dual (un PTAS para la versión dual del problema), un PTAS asintótico llamado APTAS y un FPTAS asintótico dual llamado AFPTAS para ambas versiones.

Ekici [42] introdujo una variante de BP-SPF en la que algunos elementos están en conflicto y está prohibido agrupar fragmentos de elementos en conflicto en el mismo contenedor. Demostró que esta variante también es NP-hard.

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

Problemas relacionados

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

Rendimiento con tamaños de elementos divisibles

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

Restricciones de cardinalidad en los bins

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

Funciones no aditivas

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

Problemas relacionados

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

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

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

En el problema de empaquetamiento de contenedores de recursos máximos , [51] el objetivo es maximizar el número de contenedores utilizados, de modo que, para algún orden de los contenedores, ningún elemento de un contenedor posterior quepa en un contenedor anterior. En un problema dual, el número de contenedores es fijo y el objetivo es minimizar el número total o el tamaño total de los elementos colocados en los contenedores, de modo que ningún elemento restante quepa en un contenedor vacío.

En el problema de cubrimiento de contenedores , el tamaño del contenedor está limitado desde abajo : el objetivo es maximizar la cantidad de contenedores utilizados de modo que el tamaño total en cada contenedor sea al menos un umbral determinado.

En el problema de asignación justa e indivisible de tareas (una variante de la asignación justa de ítems ), los ítems representan tareas y hay distintas personas, cada una de las cuales atribuye un valor de dificultad diferente a cada tarea. El objetivo es asignar a cada persona un conjunto de tareas con un límite superior en su valor de dificultad total (por lo tanto, cada persona corresponde a un contenedor). En este problema también se utilizan muchas técnicas del empaquetamiento de contenedores. [52]

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

En el problema del embalaje egoísta , cada artículo es un jugador que quiere minimizar su coste. [53]

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

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

Recursos

Referencias

  1. ^ Martello, Silvano; Toth, Paolo (1990), "Problema de empaquetado de contenedores" (PDF) , Problemas de mochila: algoritmos e implementaciones informáticas , Chichester, Reino Unido: John Wiley and Sons, ISBN 0471924202
  2. ^ Korte, Bernhard; Vygen, Jens (2006). "Bin-Packing". Optimización combinatoria: teoría y algoritmos . Algoritmos y combinatoria 21. Springer. págs. 426–441. doi :10.1007/3-540-29297-7_18. ISBN 978-3-540-25684-7.
  3. ^ Barrington, David Mix (2006). «Bin Packing». Archivado desde el original el 16 de febrero de 2019. Consultado el 27 de febrero de 2016 .
  4. ^ abc Coffman Jr., Edward G.; Csirik, János; Galambos, Gábor; Martello, Silvano; Vigo, Daniele (2013), Pardalos, Panos M.; Du, Ding-Zhu; Graham, Ronald L. (eds.), "Algoritmos de aproximación de embalaje de contenedores: encuesta y clasificación", Manual de optimización combinatoria , Nueva York, NY: Springer, págs. 455–531, doi :10.1007/978-1-4419-7997 -1_35, ISBN 978-1-4419-7997-1, consultado el 8 de agosto de 2021
  5. ^ "DHCPv6-PD - Primeros pasos" . Consultado el 12 de junio de 2024 .
  6. ^ Lewis, R. (2009), "Un método de escalada de propósito general para problemas de agrupamiento mínimo independiente del orden: un estudio de caso sobre coloración de gráficos y empaquetamiento de bins" (PDF) , Computers and Operations Research , 36 (7): 2295–2310, doi :10.1016/j.cor.2008.09.004, S2CID  1577334
  7. ^ Sindelar, Michael; Sitaraman, Ramesh ; Shenoy, Prashant (2011), "Algoritmos que reconocen el uso compartido para la colocación de máquinas virtuales" (PDF) , Actas del 23.º Simposio de la ACM sobre paralelismo en algoritmos y arquitecturas (SPAA), San José, California, junio de 2011 : 367–378
  8. ^ abc Garey, M. R. ; Johnson, D. S. (1979). Victor Klee (ed.). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . Una serie de libros sobre las ciencias matemáticas. San Francisco, California: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5.Sr. 0519066  .
  9. ^ Martello y Toth 1990, pag. 221
  10. ^ Vazirani, Vijay V. (14 de marzo de 2013). Algoritmos de aproximación . Springer Berlin Heidelberg. pág. 74. ISBN 978-3662045657.
  11. ^ abcdefghijklmnop Johnson, David S (1973). "Algoritmos de empaquetamiento de contenedores casi óptimos" (PDF) . Instituto Tecnológico de Massachusetts .
  12. ^ Gonzalez, Teofilo F. (23 de mayo de 2018). Manual de algoritmos de aproximación y metaheurísticas. Volumen 2 Aplicaciones contemporáneas y emergentes . Taylor & Francis Incorporated. ISBN 9781498770156.
  13. ^ abc Dósa, György; Sgall, Jiri (2013). "Embalaje en contenedores First Fit: un análisis exhaustivo". 30º Simposio Internacional sobre Aspectos Teóricos de la Informática (STACS 2013) . 20 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 538–549. doi : 10.4230/LIPIcs.STACS.2013.538 .
  14. ^ abc György, Dósa; Sgall, Jirí (2014). "Análisis óptimo del empaquetamiento de bins de mejor ajuste". Autómatas, lenguajes y programación . Apuntes de clase en informática. Vol. 8572. págs. 429–441. doi :10.1007/978-3-662-43948-7_36. ISBN 978-3-662-43947-0. {{cite book}}: |journal=ignorado ( ayuda )
  15. ^ abcde Yao, Andrew Chi-Chih (abril de 1980). "Nuevos algoritmos para el empaquetamiento de contenedores". Revista de la ACM . 27 (2): 207–227. doi : 10.1145/322186.322187 . S2CID  7903339.
  16. ^ abcdefg Lee, CC; Lee, DT (julio de 1985). "Un algoritmo simple de empaquetamiento de contenedores en línea". Revista de la ACM . 32 (3): 562–572. doi : 10.1145/3828.3833 . S2CID  15441740.
  17. ^ Donna J, Brown (1979). "Un límite inferior para algoritmos de empaquetamiento de contenedores unidimensionales en línea" (PDF) . Informe técnico . Archivado (PDF) del original el 17 de marzo de 2022.
  18. ^ Liang, Frank M. (1980). "Un límite inferior para el empaquetamiento de contenedores en línea". Cartas de procesamiento de información . 10 (2): 76–79. doi :10.1016/S0020-0190(80)90077-0.
  19. ^ van Vliet, André (1992). "Un límite inferior mejorado para algoritmos de empaquetamiento de contenedores en línea". Information Processing Letters . 43 (5): 277–284. doi :10.1016/0020-0190(92)90223-I.
  20. ^ Balogh, János; Békési, József; Galambos, Gábor (julio de 2012). "Nuevos límites inferiores para determinadas clases de algoritmos de embalaje de contenedores". Informática Teórica . 440–441: 1–13. doi : 10.1016/j.tcs.2012.04.017 .
  21. ^ ab Ramanan, Prakash; Brown, Donna J; Lee, CC; Lee, DT (septiembre de 1989). "Empaquetado de contenedores en línea en tiempo lineal". Journal of Algorithms . 10 (3): 305–326. doi :10.1016/0196-6774(89)90031-X. hdl : 2142/74206 .
  22. ^ abc Seiden, Steven S. (2002). "Sobre el problema del empaquetamiento de contenedores en línea". Revista de la ACM . 49 (5): 640–671. doi :10.1145/585265.585269. S2CID  14164016.
  23. ^ abc Dósa, György (2007). "El límite estricto del algoritmo de empaquetamiento de bins decreciente de primer ajuste es FFD(I) ≤ 11/9\mathrm{OPT}(I) + 6/9". Combinatoria, algoritmos, metodologías probabilísticas y experimentales. ESCAPE . doi :10.1007/978-3-540-74450-4_1.
  24. ^ Baker, BS; Coffman, Jr., EG (1981-06-01). "Un límite asintótico ajustado para el empaquetamiento de bins de ajuste siguiente decreciente". Revista SIAM sobre métodos algebraicos y discretos . 2 (2): 147–152. doi :10.1137/0602019. ISSN  0196-5212.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  25. ^ Csirik, J.; Galambos, G.; Frenk, JBG; Frieze, AM; Rinnooy Kan, AHG (1986-11-01). "Un análisis probabilístico de la heurística de empaquetamiento de bins decreciente del siguiente ajuste". Operations Research Letters . 5 (5): 233–236. doi :10.1016/0167-6377(86)90013-1. hdl : 1765/11645 . ISSN  0167-6377. S2CID  50663185.
  26. ^ Fisher, David C. (1988-12-01). "Next-fit empaqueta una lista y su reverso en el mismo número de contenedores". Operations Research Letters . 7 (6): 291–293. doi :10.1016/0167-6377(88)90060-0. ISSN  0167-6377.
  27. ^ ab Johnson, David S; Garey, Michael R (octubre de 1985). "Un teorema 7160 para empaquetamiento de bins". Journal of Complexity . 1 (1): 65–106. doi : 10.1016/0885-064X(85)90022-6 .
  28. ^ ab Yue, Minyi; Zhang, Lei (julio de 1995). "Una prueba simple de la desigualdad MFFD(L) ≤ 71/60 OPT(L) + 1,L para el algoritmo de empaquetamiento de bins MFFD". Acta Mathematicae Applicatae Sinica . 11 (3): 318–330. doi :10.1007/BF02011198. S2CID  118263129.
  29. ^ Fernandez de la Vega, W.; Lueker, GS (1981). "El empaquetamiento de bins puede resolverse dentro de 1 + ε en tiempo lineal". Combinatorica . 1 (4): 349–355. doi :10.1007/BF02579456. ISSN  1439-6912. S2CID  10519631.
  30. ^ Claire Mathieu. "Algoritmos de aproximación, parte I, semana 3: empaquetamiento de contenedores". Coursera . Archivado desde el original el 15 de julio de 2021.
  31. ^ por Rothvoß, T. (1 de octubre de 2013). "Aproximación del empaquetamiento de bins dentro de bins O(log OPT · Log Log OPT)". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . págs. 20–29. arXiv : 1301.4010 . doi :10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7.S2CID15905063  .​
  32. ^ ab Hoberg, Rebecca; Rothvoss, Thomas (1 de enero de 2017), "Una brecha de integralidad aditiva logarítmica para empaquetamiento de bins", Actas del Simposio anual ACM-SIAM de 2017 sobre algoritmos discretos , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 2616–2625, arXiv : 1503.08796 , doi : 10.1137/1.9781611974782.172 , ISBN 978-1-61197-478-2, Número de identificación del sujeto  1647463
  33. ^ Karmarkar, Narendra; Karp, Richard M. (noviembre de 1982). "Un esquema de aproximación eficiente para el problema de empaquetamiento de bins unidimensional". 23.° Simposio Anual sobre Fundamentos de la Ciencia de la Computación (SFCS 1982) : 312–320. doi :10.1109/SFCS.1982.61. S2CID  18583908.
  34. ^ Martello y Toth 1990, págs. 237-240.
  35. ^ Korf, Richard E. (2002). Un nuevo algoritmo para el empaquetamiento óptimo de contenedores (PDF) . AAAI-02.
  36. ^ RE Korf (2003), Un algoritmo mejorado para el empaquetamiento óptimo de contenedores . Actas de la Conferencia conjunta internacional sobre inteligencia artificial (págs. 1252-1258).
  37. ^ Schreiber, Ethan L.; Korf, Richard E. (2013), "Completado de bin mejorado para empaquetamiento de bin óptimo y partición de números" (PDF) , Actas de la vigésimo tercera conferencia conjunta internacional sobre inteligencia artificial , IJCAI '13, Beijing, China: AAAI Press, págs. 651–658, ISBN 978-1-57735-633-2
  38. ^ ab Mandal, CA; Chakrabarti, PP; Ghose, S. (1998-06-01). "Complejidad del empaquetamiento de contenedores de objetos fragmentables y una aplicación". Computers & Mathematics with Applications . 35 (11): 91–97. doi :10.1016/S0898-1221(98)00087-X. ISSN  0898-1221.
  39. ^ Nir Menakerman y Raphael Rom "Bin Packing with Item Fragmentation". Algorithms and Data Structures, 7º Taller Internacional, WADS 2001, Providence, RI, EE.UU., 8-10 de agosto de 2001, Actas.
  40. ^ Bertazzi, Luca; Golden, Bruce; Wang, Xingyin (31 de mayo de 2019). "El problema del empaquetamiento de contenedores con fragmentación de elementos: un análisis del peor caso". Matemáticas aplicadas discretas . Reunión GO X, Rigi Kaltbad (Suiza), 10-14 de julio de 2016. 261 : 63–77. doi : 10.1016/j.dam.2018.08.023 . ISSN  0166-218X. S2CID  125361557.
  41. ^ Shachnai, Hadas; Tamir, Tami; Yehezkely, Omer (2006). "Esquemas de aproximación para empaquetamiento con fragmentación de ítems". En Erlebach, Thomas; Persinao, Giuseppe (eds.). Aproximación y algoritmos en línea . Apuntes de clase en informática. Vol. 3879. Berlín, Heidelberg: Springer. págs. 334–347. doi :10.1007/11671411_26. ISBN . 978-3-540-32208-5.
  42. ^ Ekici, Ali (1 de febrero de 2021). "Problema de empaquetamiento de contenedores con conflictos y fragmentación de elementos". Computers & Operations Research . 126 : 105113. doi :10.1016/j.cor.2020.105113. ISSN  0305-0548. S2CID  225002556.
  43. ^ Casazza, Marco; Ceselli, Alberto (1 de junio de 2014). "Algoritmos de programación matemática para problemas de empaquetamiento de contenedores con fragmentación de ítems". Computers & Operations Research . 46 : 1–11. doi :10.1016/j.cor.2013.12.008. ISSN  0305-0548.
  44. ^ Malaguti, Enrico; Monaci, Michele; Paronuzzi, Paolo; Pferschy, Ulrich (16 de marzo de 2019). "Optimización de enteros con valores fraccionarios penalizados: el caso Knapsack". Revista Europea de Investigación Operativa . 273 (3): 874–888. doi :10.1016/j.ejor.2018.09.020. hdl : 11585/657029 . ISSN  0377-2217. S2CID  31722681.
  45. ^ Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Empaquetado de contenedores con tamaños de elementos divisibles". Journal of Complexity . 3 (4): 406–428. doi :10.1016/0885-064X(87)90009-4. ISSN  0885-064X.
  46. ^ Krause, KL; Shen, VY; Schwetman, HD (1975-10-01). "Análisis de varios algoritmos de planificación de tareas para un modelo de sistemas informáticos multiprogramados". Revista de la ACM . 22 (4): 522–550. doi : 10.1145/321906.321917 . ISSN  0004-5411. S2CID  10214857.
  47. ^ Kellerer, H.; Pferschy, U. (1999-01-01). "Problemas de bin-packing con restricciones de cardinalidad". Anales de Investigación de Operaciones . 92 : 335–348. doi :10.1023/A:1018947117526. ISSN  1572-9338. S2CID  28963291.
  48. ^ ab Anily, Shoshana; Bramel, Julien; Simchi-Levi, David (1994-04-01). "Análisis del peor caso de heurísticas para el problema de empaquetamiento de contenedores con estructuras de costos generales". Investigación de operaciones . 42 (2): 287–298. doi :10.1287/opre.42.2.287. ISSN  0030-364X.
  49. ^ Cohen, Maxime C.; Keller, Philipp W.; Mirrokni, Vahab; Zadimoghaddam, Morteza (1 de julio de 2019). "Sobrecompromiso en servicios en la nube: empaquetado de contenedores con restricciones aleatorias". Management Science . 65 (7): 3255–3271. arXiv : 1705.09335 . doi :10.1287/mnsc.2018.3091. ISSN  0025-1909. S2CID  159270392.
  50. ^ Chung, Yerim; Park, Myoung-Ju (1 de enero de 2015). "Notas sobre problemas de empaquetamiento inverso". Cartas de procesamiento de la información . 115 (1): 60–68. doi :10.1016/j.ipl.2014.09.005. ISSN  0020-0190.
  51. ^ 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.
  52. ^ Huang, Xin; Lu, Pinyan (10 de noviembre de 2020). "Un marco algorítmico para aproximar la asignación de tareas con la máxima participación". arXiv : 1907.04505 [cs.GT].
  53. ^ Ma, Ruixin; Dósa, György; Han, Xin; Ting, Hing-Fung; Ye, Deshi; Zhang, Yong (1 de agosto de 2013). "Una nota sobre un problema de empaquetamiento egoísta". Revista de optimización global . 56 (4): 1457–1462. doi :10.1007/s10898-012-9856-9. ISSN  0925-5001. S2CID  3082040.
  54. ^ Lodi A., Martello S., Monaci, M., Vigo, D. (2010) "Problemas de empaquetamiento de bins bidimensionales". En V.Th. Paschos (Ed.), Paradigms of Combinatorial Optimization , Wiley/ISTE, págs. 107–129
  55. ^ Optimización del embalaje tridimensional de contenedores mediante simulación
  56. ^ Benkő A., Dósa G., Tuza Z. (2010) "Empaquetado/cubrimiento de contenedores con entrega, resuelto con la evolución de algoritmos", Actas 2010 IEEE 5.ª Conferencia internacional sobre computación bioinspirada: teorías y aplicaciones, BIC-TA 2010 , art. n.º 5645312, págs. 298-302.