El corte con guillotina es el proceso de producir pequeños artículos rectangulares de dimensiones fijas a partir de una hoja rectangular grande dada, utilizando solo cortes de guillotina. Un corte de guillotina (también llamado corte de borde a borde ) es una línea recta que se biseca desde un borde de un rectángulo existente hasta el borde opuesto, de manera similar a una guillotina de papel .
El corte con guillotina es particularmente común en la industria del vidrio . Las hojas de vidrio se marcan a lo largo de líneas horizontales y verticales, y luego se rompen a lo largo de estas líneas para obtener paneles más pequeños. [1] También es útil para cortar placas de acero , cortar láminas de madera para hacer muebles y cortar cartón en cajas. [2]
Existen varios problemas de optimización relacionados con el corte con guillotina, tales como: maximizar el área total de las piezas producidas, o su valor total; minimice la cantidad de desperdicio (partes no utilizadas) de la hoja grande, o el número total de hojas. Se han estudiado en geometría combinatoria , investigación de operaciones e ingeniería industrial . [3]
Un problema relacionado pero diferente es la partición de guillotina . En ese problema, las dimensiones de los pequeños rectángulos no se fijan de antemano. El desafío proviene del hecho de que la hoja original puede no ser rectangular, puede ser cualquier polígono rectilíneo. En particular, puede contener agujeros (que representan defectos en la materia prima). El objetivo de la optimización suele ser minimizar el número de pequeños rectángulos o minimizar la longitud total de los cortes.
Terminología y supuestos
Los siguientes términos y anotaciones se utilizan a menudo en la literatura sobre corte con guillotina.
- El rectángulo grande , también llamado hoja de stock , es la hoja rectangular sin procesar que debe cortarse. Se caracteriza por su ancho W 0 y alto H 0 , que son las principales entradas al problema.
- Los pequeños rectángulos , también llamados elementos , son las salidas requeridas del corte. Se caracterizan por su ancho w i y alto h i y para i en 1, ..., m , donde m es el número de rectángulos. A menudo, se permite tener varios rectángulos de las mismas dimensiones; en este caso, el par de dimensiones ( w i , h i ) a menudo se denomina tipo .
- Un patrón de corte , a menudo llamado patrón simple , es una disposición de pequeños rectángulos en la hoja de papel. Puede expresarse como una secuencia de puntos ( x i , y i ), para i en 1, ..., m , donde ( x i , y i ) es la coordenada inferior izquierda del rectángulo i . En tal patrón, el rectángulo i ocupa un segmento horizontal ( x i , x i + w i ) y un segmento vertical ( y i , y i + h i ).
- Una construcción se refiere a la construcción de un nuevo rectángulo adjuntando dos rectángulos más pequeños. Debido a la restricción de la guillotina, solo hay dos tipos de construcciones: en una construcción horizontal, el rectángulo combinado tiene un ancho w i + w j y una altura máxima ( h i , h j ); en una construcción vertical, el rectángulo combinado tiene ancho máximo ( w i , w j ) y alto h i + h j . Cada patrón se puede representar como una secuencia recursiva de compilaciones. Cada secuencia recursiva de compilaciones corresponde a muchos patrones diferentes, que tienen una estructura combinatoria equivalente; el conjunto de todos los patrones correspondientes a la misma construcción recursiva se denomina clase de corte de guillotina . [4]
Algunos problemas aceptan entradas adicionales, como se explica a continuación. El objetivo es cortar, del rectángulo en bruto, algunos rectángulos más pequeños que tengan las dimensiones objetivo. A menudo se hacen las siguientes suposiciones: [2]
- Todos los cortes tienen ancho cero. Esto no pierde mucha generalidad, ya que si cada corte tiene un ancho fijo de d > 0, entonces el problema se puede reducir a la variante de ancho cero simplemente agregando d a w i y h i para i en 0, ... , m .
- Las dimensiones objetivo no se pueden rotar, es decir, w -by- h no es del mismo tipo que h -by- w . Esto no pierde mucha generalidad, ya que la variante en la que se pueden rotar rectángulos, se puede reducir a la variante no rotatoria agregando los patrones rotados explícitamente.
Verificando un patrón dado
En el problema de verificación de patrones , hay un patrón de corte dado como una secuencia de puntos ( x i , y i ), para i en 1, ..., m , donde ( x i , y i ) es la parte inferior izquierda coordenada del rectángulo i (hay un solo rectángulo de cada dimensión objetivo). El objetivo es decidir si este patrón se puede implementar utilizando solo cortes de guillotina y, de ser así, encontrar una secuencia de dichos cortes.
Una condición necesaria obvia es que no se superpongan dos rectángulos de entrada en ambas dimensiones. Ben Messaoud, Chengbin y Espinouse [5] presentan una condición más fuerte, necesaria y suficiente. Los rectángulos de entrada están ordenados de izquierda a derecha, de modo que x 1 ≤ ... ≤ x m . Hay una permutación p en los índices tal que, con esta permutación, los rectángulos se ordenarían de abajo hacia arriba, es decir, y p (1) ≤ ... ≤ y p ( m ) . Dados cuatro índices i 1 ≤ i 2 y j 1 ≤ j 2 , el conjunto E ( i 1 , i 2 , j 1 , j 2 ) contiene los índices de todos los rectángulos cuya esquina inferior izquierda está en el rectángulo [ x i 1 , x yo 2 ] X [ y p ( j 1) , y p ( j 2) ]. Un patrón de corte es un patrón de guillotina si y solo si, para todos los cuatrillizos de índices i 1 ≤ i 2 y j 1 ≤ j 2 , se cumple al menos una de las siguientes condiciones para E ( i 1 , i 2 , j 1 , j 2 ):
- E ( i 1 , i 2 , j 1 , j 2 ) contiene como máximo un elemento;
- La unión de los segmentos horizontales ( x i , x i + w i ), sobre todo i en E ( i 1 , i 2 , j 1 , j 2 ), se compone de al menos dos intervalos disjuntos;
- La unión de los segmentos verticales ( y i , y i + h i ), sobre todo i en E ( i 1 , i 2 , j 1 , j 2 ), se compone de al menos dos intervalos disjuntos.
La condición 2 implica que los rectángulos en E ( i 1 , i 2 , j 1 , j 2 ) pueden estar separados por un corte vertical (que va entre los dos intervalos horizontales disjuntos); La condición 3 implica que los rectángulos en E ( i 1 , i 2 , j 1 , j 2 ) pueden separarse mediante un corte horizontal. Todas las condiciones juntas implican que, si cualquier conjunto de rectángulos adyacentes contiene más de un elemento, entonces pueden separarse mediante algún corte de guillotina.
Esta condición se puede verificar mediante el siguiente algoritmo.
- En cada iteración, divida un patrón dado, que contenga al menos dos rectángulos, en dos subpatrones separados utilizando un corte de guillotina, y repita en cada subpatrón.
- Deténgase cuando todos los subpatrones contienen un rectángulo (en cuyo caso la respuesta es "sí") o no son posibles más cortes de guillotina (en cuyo caso la respuesta es "no").
Encontrar un corte de guillotina para un patrón dado se hace de la siguiente manera:
- Determine los m intervalos horizontales y ordénelos de izquierda a derecha; Determine los m intervalos verticales y ordénelos de abajo hacia arriba. Esto lleva O ( m log m ) tiempo.
- Fusionar intervalos horizontales superpuestos y fusionar intervalos verticales superpuestos. Esto lleva O ( m ) tiempo.
- Si, después de la fusión, hay al menos dos intervalos horizontales separados, entonces es posible un corte de guillotina vertical; si hay al menos dos intervalos verticales separados, entonces es posible un corte horizontal; de lo contrario, no es posible ningún corte.
El paso de pedido se realiza una vez y el paso de fusión se realiza m -1 veces. Por lo tanto, el tiempo de ejecución de todo el algoritmo es O ( m 2 ).
Cuando el algoritmo devuelve "sí", también produce una secuencia de cortes de guillotina; cuando devuelve "no", también produce subconjuntos específicos de rectángulos que no pueden separarse mediante cortes de guillotina.
La condición necesaria y suficiente se puede utilizar para presentar el problema de corte de tiras de guillotina como un programa lineal de enteros mixtos . [5] : SEC.5 Su modelo tiene 3 n 4 /4 variables binarias y 2 n 4 limitaciones, y no se considera útil en la práctica.
Encontrar un patrón de corte óptimo
Estas son variantes del material de corte bidimensional , el empaquetado en contenedores y los problemas del empaque rectangular , donde los cortes están limitados a ser cortes de guillotina. [6]
- En el problema básico de corte con guillotina ( no ponderado ), la salida requerida es una secuencia de cortes de guillotina que producen piezas de las dimensiones objetivo, de modo que el área total de las piezas producidas se maximiza (de manera equivalente, se minimiza el desperdicio del rectángulo crudo) .
- En la variante ponderada , para cada dimensión objetivo i , también hay un valor v i . El objetivo es entonces maximizar el valor total de las piezas producidas. La variante no ponderada (minimización de residuos) se puede reducir a la variante ponderada haciendo que el valor de cada dimensión objetivo sea igual a su área ( v i = h i * w i ).
- En la variante restringida , para cada dimensión objetivo i , hay un límite superior b i en el número de piezas que se pueden producir de ese tipo.
- En la variante doblemente restringida , para cada dimensión objetivo i hay un límite inferior a i y un límite superior b i en el número de piezas producidas.
- La variante binaria es una variante restringida en la que cada dimensión de destino debe aparecer como máximo una vez (es decir, el límite superior es 1). Este caso está asociado con un problema de decisión , donde el objetivo es decidir si es posible producir un solo elemento de cada dimensión objetivo utilizando cortes de guillotina. [4]
- En el problema del corte de tiras de guillotina , el rectángulo grande tiene una altura infinita (pero un ancho fijo), y el objetivo es cortar un solo rectángulo de cada tipo, de modo que el material total utilizado (equivalentemente, la altura total) se minimice. Es una variante del problema de empaquetado de tiras bidimensional .
- En el problema de minimización de stock , hay un número infinito de hojas de stock de las mismas dimensiones, y el objetivo es cortar todos los rectángulos de destino necesarios utilizando la menor cantidad posible de hojas. [5] Es una variante del problema de embalaje bidimensional en contenedores . [7]
- El corte en guillotina en k etapas es una variante restringida del corte en guillotina donde el corte se realiza en la mayoría de las etapas k : en la primera etapa, solo se hacen cortes horizontales; en la segunda etapa, solo se realizan cortes verticales; y así.
- En la variante de 2 etapas, una distinción adicional es si todas las tiras resultantes de la primera etapa se cortan en las mismas ubicaciones (llamadas "1 grupo") o en dos ubicaciones diferentes (llamadas "2 grupos") o en posiblemente diferentes ubicaciones (llamadas "gratuitas"). [8]
- El corte con guillotina simple es una variante restringida del corte con guillotina en el que cada corte separa un solo rectángulo.
- Un corte de guillotina de 2 simples es un patrón de 1 simple, de modo que cada parte es en sí misma un patrón de 1 simple. p -se pueden definir patrones de corte simples de forma recursiva. [9]
Algoritmos de optimización
El caso especial en el que solo hay un tipo (es decir, todos los rectángulos de destino son idénticos y están en la misma orientación) se denomina problema de carga de paletas de guillotina . Tarnowski, Terno y Scheithauer [10] presentan un algoritmo de tiempo polinomial para resolverlo.
Sin embargo, cuando hay dos o más tipos, todos los problemas de optimización relacionados con el corte con guillotina son NP difíciles . Debido a su importancia práctica, se han ideado varios algoritmos exactos y algoritmos de aproximación .
- Gilmore y Gomory [11] [12] presentaron una recursividad de programación dinámica tanto para el corte de guillotina por etapas como para las que no lo son. Sin embargo, más tarde se demostró [13] [2] que ambos algoritmos contenían errores. Beasley [2] presentó un algoritmo de programación dinámico correcto.
- Herz [13] y Christofides y Whitlock [14] presentaron procedimientos de búsqueda de árboles para cortes de guillotina sin etapas.
- Masden [15] y Wang [16] presentaron algoritmos heurísticos .
- Hiffi, M'Hallah y Saadi [6] proponen un algoritmo para el problema de corte con guillotina doblemente restringido. Es un algoritmo de enlace y ramificación de abajo hacia arriba que utiliza la búsqueda del mejor primero .
- Clautiaux, Jouglet y Moukrim [4] proponen un algoritmo exacto para el problema de decisión. Su algoritmo usa una representación compacta de clases de patrones de corte de guillotina, usando un gráfico dirigido que ellos llaman gráfico de guillotina . Cada arco en este gráfico está coloreado en uno de dos colores: "horizontal" o "vertical". Cada ciclo dirigido monocromático en este gráfico corresponde a una construcción. Al contraer repetidamente ciclos monocromáticos, se puede recuperar una secuencia de construcción recursiva que representa una clase de patrón de corte. Cada gráfico de guillotina contiene entre my 2 m -2 arcos. Un tipo especial de gráficos de guillotina llamados gráficos de guillotina normales tienen la interesante propiedad de contener un circuito hamiltoniano único . Ordenar los vértices de acuerdo con este circuito hace que el gráfico sea un gráfico de guillotina normal bien ordenado ; existe una correspondencia uno a uno entre tales gráficos y clases de patrones de corte. Luego resuelven el problema de optimización utilizando la programación de restricciones en el espacio de gráficos de guillotina normales bien ordenados.
- Russo, Boccia, Sforza y Sterle [8] revisan más de 90 artículos que tratan del corte con guillotina restringido sin etapas (con límites superiores de cantidad), tanto ponderados como no ponderados. Hay dos enfoques principales para las soluciones exactas: programación dinámica y búsqueda de árbol (ramificar y enlazar). Los enfoques de búsqueda de árbol se clasifican además como de abajo hacia arriba (comenzando con rectángulos individuales y usando compilaciones para construir la hoja completa) o de arriba hacia abajo . En todos los enfoques, es importante encontrar buenos límites inferior y superior para recortar el espacio de búsqueda de manera eficiente. Estos límites a menudo provienen de soluciones a variantes relacionadas, por ejemplo, variantes sin restricciones, por etapas y sin guillotina.
- Abou Msabah, Slimane y Ahmed Riadh Baba-Ali. "Una nueva heurística de colocación de guillotina combinada con un algoritmo genético mejorado para el problema de corte ortogonal". 2011 IEEE International Conference on Industrial Engineering and Engineering Management . IEEE, 2011.
- Abou-Msabah, Slimane, Ahmed-Riadh Baba-Ali y Basma Sager. "Un algoritmo genético de estabilidad controlada con la nueva heurística de colocación de guillotina BLF2G para el problema del material de corte ortogonal". Revista Internacional de Informática Cognitiva e Inteligencia Natural (IJCINI) 13, no. 4 (2019): 91-111.
Implementaciones
- McHale y Shah [17] escribieron un programa Prolog que implementa un algoritmo en cualquier momento : genera soluciones aproximadamente óptimas en un período de tiempo determinado y luego las mejora si el usuario permite más tiempo. El programa fue utilizado por un productor de papel especial y ha reducido el tiempo necesario para el diseño de las hojas al tiempo que reduce el desperdicio.
Separación de guillotina
La separación de guillotina es un problema relacionado en el que la entrada es una colección de n objetos convexos separados por pares en el plano, y el objetivo es separarlos mediante una secuencia de cortes de guillotina. Obviamente, puede que no sea posible separarlos todos. Jorge Urrutia Galicia preguntó [18] si es posible separar una fracción constante de ellos, es decir, si existe una constante c tal que, en cualquier colección de tamaño n, haya un subconjunto de tamaño cn que sean guillotina- separable.
Pach y Tardos [19] demostraron:
- Si todos los objetos tienen un tamaño similar, se puede separar una fracción constante de ellos. Formalmente, si todos los objetos contienen un círculo de radio r y están contenidos en un círculo de radio R , entonces hay un conjunto de tamaño separable.. Prueba : construya una cuadrícula con un tamaño de celda de 8 R por 8 R. Mueva la cuadrícula de manera uniforme al azar. Cada objeto está cruzado por una línea horizontal con probabilidad 1/4 y con una línea vertical con probabilidad 1/4 también, por lo que el número esperado de objetos cruzados es. Por lo tanto, existen líneas de cuadrícula que se cruzan como máximoobjetos. Dado que el área de cada celda de la cuadrícula es y el área de cada objeto es al menos , cada celda contiene como máximo objetos. Elija un solo objeto de cada celda y sepárelo de los otros objetos en la misma celda. El número total de objetos separados de esta manera es al menos Un argumento similar para el caso de los cuadrados unitarios da
- Si los objetos son segmentos de línea recta, en algunos casos, solo como máximo de ellos se pueden separar. Particularmente, para cada entero positivo k , hay una familia de intervalos disjuntos tales que a lo sumo de ellos se pueden separar.
- En cualquier colección de n objetos convexos, al menos se puede separar.
- En cualquier colección de n segmentos de línea recta, al menosse puede separar. Conjeturan que el peor de los casos se puede lograr mediante segmentos de línea.
- En cualquier colección de n rectángulos paralelos a ejes, al menosse puede separar. Ellos conjeturan quese puede separar; esta conjetura sigue abierta.
- En cualquier colección de objetos R - grasa (el disco que contiene más pequeño es como máximo R veces el disco contenido más grande), al menos los objetos se pueden guardar, donde es una constante que depende sólo de R .
- Un teorema análogo también es válido en dimensiones superiores: el número de objetos separables es .
- Todas estas subfamilias separables se pueden construir a tiempo . Si los objetos son polígonos con N lados en total, entonces las líneas de separación se pueden calcular a tiempo.
Abed, Chalermsook, Correa, Karrenbauer, Pérez-Lantero, Soto y Wiese [20] demostraron:
- En cualquier colección de n cuadrados unitarios paralelos, al menos n / 2 pueden separarse, y hay casos en los que como máximo n / 2 pueden separarse.
- En cualquier colección de n cuadrados paralelos a ejes, se puede separar al menos n / 81.
- En cualquier colección de n cuadrados paralelos con pesos, se pueden separar al menos 4/729 del peso total.
- En cualquier colección de n cubos d- dimensionales paralelos con pesos, del peso total se puede separar.
- Respecto a la conjetura de que es posible separar ejes-rectángulo paralelo, si bien no lo resuelven, muestran que, si es correcto, implica un algoritmo de aproximación O (1) al problema de máximo conjunto disjunto de ejes-rectángulos paralelos en el tiempo.
Khan y Pittu [21] demostraron:
- Con n rectángulos paralelos a ejes, si solo las etapas están permitidas, entonces no es posible separar rectángulos.
- Cuando se ponderan los rectángulos, si solo las etapas están permitidas, entonces no es posible separar del peso.
- Hay un algoritmo simple de 2 etapas que separa rectángulos.
- En cualquier colección de rectángulos gordos, se puede separar.
- En cualquier colección de n cuadrados paralelos a ejes, se puede separar al menos n / 40.
- En cualquier colección de n cuadrados paralelos con pesos, se puede separar al menos una fracción 1/80 del peso total.
Ver también:
- Separador geométrico
- Teorema de separación de hiperplano
Más variantes
Algunas variantes del problema estudiadas recientemente incluyen:
- Corte de guillotina en tres dimensiones. [22] [23]
- Corte con guillotina cuando el rectángulo en bruto puede tener defectos, pero los rectángulos producidos deben estar libres de defectos. [24]
Referencias
- ^ Tlilane, Lydia; Viaud, Quentin (18 de mayo de 2018). "Desafío ROADEF / EURO 2018 Descripción del problema de optimización de corte" (PDF) . Desafío ROADEF / EURO . ROADEF . Consultado el 13 de junio de 2019 .
- ^ a b c d Beasley, JE (1 de abril de 1985). "Algoritmos para corte de guillotina bidimensional sin restricciones" . Revista de la Sociedad de Investigación Operativa . 36 (4): 297-306. doi : 10.1057 / jors.1985.51 . ISSN 0160-5682 .
- ^ Gerhard Wäscher, Heike Haußner, Holger Schumann, Una tipología mejorada de problemas de corte y empaque, European Journal of Operational Research 183 (2007) 1109-1130, [1]
- ^ a b c Clautiaux, François; Jouglet, Antoine; Moukrim, Aziz (17 de octubre de 2011). "Un nuevo modelo teórico de gráficos para el problema de corte de guillotina" . INFORMA Revista de Computación . 25 (1): 72–86. doi : 10.1287 / ijoc.1110.0478 . ISSN 1091-9856 .
- ^ a b c Ben Messaoud, Said; Chu, Chengbin; Espinouse, Marie-Laure (16 de noviembre de 2008). "Caracterización y modelado de restricciones de guillotina" . Revista europea de investigación operativa . 191 (1): 112–126. doi : 10.1016 / j.ejor.2007.08.029 . ISSN 0377-2217 .
- ^ a b M. Hifi, R. M'Hallah y T. Saadi, algoritmos aproximados y exactos para el problema de material de corte de guillotina bidimensional con doble restricción. Aplicaciones y optimización computacional, Volumen 42, Número 2 (2009), 303-326, doi : 10.1007 / s10589-007-9081-5
- ^ Carlier, Jacques; Clautiaux, François; Moukrim, Aziz (1 de agosto de 2007). "Nuevos procedimientos de reducción y límites inferiores para el problema de embalaje bidimensional de contenedores con orientación fija" . Investigación de Computación y Operaciones . 34 (8): 2223–2250. doi : 10.1016 / j.cor.2005.08.012 . ISSN 0305-0548 .
- ^ a b Russo, Mauro; Boccia, Maurizio; Sforza, Antonio; Sterle, Claudio (2020). "Problema de corte de guillotina bidimensional restringido: revisión de límite superior y categorización" . Transacciones internacionales en investigación operativa . 27 (2): 794–834. doi : 10.1111 / itor.12687 . ISSN 1475-3995 .
- ^ http://www.math.tu-dresden.de/~scheith/ABSTRACTS/PREPRINTS/93-COM.pdf
- ^ Tarnowski, AG; Terno, J .; Scheithauer, G. (1 de noviembre de 1994). "Un algoritmo de tiempo polinomial para el problema de carga de paletas de guillotina" . INFOR: Sistemas de información e investigación operativa . 32 (4): 275-287. doi : 10.1080 / 03155986.1994.11732257 . ISSN 0315-5986 .
- ^ Gilmore, PC; Gomory, RE (1 de febrero de 1965). "Problemas de material de corte de varias etapas de dos y más dimensiones" . Investigación operativa . 13 (1): 94-120. doi : 10.1287 / opre.13.1.94 . ISSN 0030-364X .
- ^ Gilmore, PC; Gomory, RE (1 de diciembre de 1966). "La teoría y el cálculo de las funciones de la mochila" . Investigación operativa . 14 (6): 1045–1074. doi : 10.1287 / opre.14.6.1045 . ISSN 0030-364X .
- ^ a b Herz, JC (septiembre de 1972). "Procedimiento computacional recursivo para corte de stock bidimensional" . Revista de investigación y desarrollo de IBM . 16 (5): 462–469. doi : 10.1147 / rd.165.0462 . ISSN 0018-8646 .
- ^ Christofides, Nicos; Whitlock, Charles (1 de febrero de 1977). "Un algoritmo para problemas de corte bidimensionales" . Investigación operativa . 25 (1): 30–44. doi : 10.1287 / opre.25.1.30 . ISSN 0030-364X .
- ^ OBG Masden (1980), documento de trabajo IMSOR, Universidad técnica de Dinamarca, Lyngby
- ^ Wang, PY (1 de junio de 1983). "Dos algoritmos para problemas de material de corte bidimensional restringido" . Investigación operativa . 31 (3): 573–586. doi : 10.1287 / opre.31.3.573 . ISSN 0030-364X .
- ^ Michael L. McHale, Roshan P. Shah Cortando la guillotina a medida. Revista PC AI, Volumen 13, Número 1, enero / febrero de 99. http://www.amzi.com/articles/papercutter.htm
- ^ Problema presentado en ACCOTA '96, Aspectos combinatorios y computacionales de la topología y álgebra de optimización, Taxco, México 1996
- ^ Pach, J .; Tardos, G. (2000). "Cortar vidrio" . Geometría discreta y computacional . 24 (2–3): 481–496. doi : 10.1007 / s004540010050 . ISSN 0179-5376 .
- ^ Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A .; Wiese, Andreas (2015). Sobre secuencias de corte de guillotina . págs. 1–19. doi : 10.4230 / LIPIcs.APPROX-RANDOM.2015.1 . ISBN 978-3-939897-89-7.
- ^ Khan, Arindam; Pittu, Madhusudhan Reddy (2020). Byrka, ley de Jaros; Meka, Raghu (eds.). "Sobre la separabilidad de la guillotina de cuadrados y rectángulos" . Aproximación, Aleatorización y Optimización Combinatoria. Algoritmos y Técnicas (APROX / ALEATORIO 2020) . Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 176 : 47: 1–47: 22. doi : 10.4230 / LIPIcs.APPROX / RANDOM.2020.47 . ISBN 978-3-95977-164-1.
- ^ Martín, Mateus; Oliveira, José Fernando; Silva, Elsa; Morabito, Reinaldo; Munari, Pedro (8 de noviembre de 2020). "Problemas de corte de guillotina tridimensional con patrones restringidos: formulaciones MILP y un algoritmo de abajo hacia arriba" . Sistemas expertos con aplicaciones . 168 : 114257. doi : 10.1016 / j.eswa.2020.114257 . ISSN 0957-4174 .
- ^ Baazaoui, M .; Hanafi, S .; Kamoun, H. (1 de noviembre de 2014). "Una formulación matemática y un límite inferior para el problema de embalaje de contenedores de tamaño múltiple de contenedores tridimensionales (MBSBPP): un caso industrial de Túnez" . Conferencia internacional de 2014 sobre tecnologías de la información, la toma de decisiones y el control (CoDIT) : 219–224. doi : 10.1109 / CoDIT.2014.6996896 . ISBN 978-1-4799-6773-5.
- ^ Martín, Mateus; Hokama, Pedro HDB; Morabito, Reinaldo; Munari, Pedro (2 de mayo de 2020). "El problema de corte de guillotina bidimensional restringido con defectos: una formulación de ILP, una descomposición de Benders y un algoritmo basado en CP" . Revista Internacional de Investigación en Producción . 58 (9): 2712–2729. doi : 10.1080 / 00207543.2019.1630773 . ISSN 0020-7543 .
Abou Msabah, Slimane y Ahmed Riadh Baba-Ali. "Una nueva heurística de colocación de guillotina combinada con un algoritmo genético mejorado para el problema de corte ortogonal". 2011 IEEE International Conference on Industrial Engineering and Engineering Management . IEEE, 2011.