Corte con guillotina

Proceso de producción de pequeños artículos rectangulares de dimensiones fijas.

Un corte de guillotina: una hoja optimizada de rectángulos más pequeños que se puede dividir intacta mediante la serie correcta de cortes bisectores de extremo a extremo.

Un corte sin guillotina: estos rectángulos no se pueden separar haciendo cortes biseccionales simples a lo largo del plano.

El corte con guillotina es el proceso de producir pequeños elementos rectangulares de dimensiones fijas a partir de una hoja rectangular grande determinada, utilizando únicamente cortes de guillotina. Un corte con guillotina (también llamado corte de borde a borde ) es una línea recta que bisecta 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 láminas de vidrio se rayan 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 para hacer cajas. ^[2]

Existen diversos problemas de optimización relacionados con el corte con guillotina, como por ejemplo: maximizar el área total de las piezas producidas, o su valor total; minimizar la cantidad de desperdicio (partes no utilizadas) de la hoja grande, o el número total de hojas. Han sido estudiados 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 están fijadas de antemano. El desafío surge del hecho de que la hoja original podría no ser rectangular, sino que puede ser cualquier polígono rectilíneo. En particular, podría contener agujeros (que representan defectos en la materia prima). El objetivo de optimización suele ser minimizar la cantidad de pequeños rectángulos o minimizar la longitud total de los cortes.

Terminología y suposiciones

Los siguientes términos y notaciones 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 en bruto que se debe cortar. Se caracteriza por su ancho W ₀ y su altura H ₀ , que son los datos principales del problema.
• Los rectángulos pequeños , también llamados elementos , son los resultados requeridos del corte. Se caracterizan por su ancho w _i y su altura 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 simplemente patrón , es una disposición de pequeños rectángulos en la hoja de material. Puede darse 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 un patrón de este tipo, 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 uniendo dos rectángulos más pequeños. Debido a la restricción de guillotina, solo hay dos tipos de construcciones: en una construcción horizontal, el rectángulo combinado tiene ancho w _i + w _j y altura max( h _i , h _j ); en una construcción vertical, el rectángulo combinado tiene ancho max( w _i ,w _j ) y altura h _i + h _j . Cada patrón se puede representar como una secuencia recursiva de construcciones. Cada secuencia recursiva de construcciones 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, a partir del rectángulo original, algunos rectángulos más pequeños que tengan las dimensiones deseadas. A menudo se hacen las siguientes suposiciones: ^[2]

• Todos los cortes tienen un 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 sumando d a w _i y h _i para i en 0,..., m .
• Las dimensiones de destino no se pueden rotar, es decir, w por h no es del mismo tipo que h por w . Esto no pierde mucha generalidad, ya que la variante en la que se pueden rotar los rectángulos se puede reducir a la variante no rotable agregando los patrones rotados explícitamente.

Comprobación de un patrón determinado

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 coordenada inferior izquierda 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 haya dos rectángulos de entrada superpuestos en ambas dimensiones. Ben Messaoud, Chengbin y Espinouse ^[5] presentan una condición más fuerte, que es necesaria y suficiente. Los rectángulos de entrada están ordenados de izquierda a derecha, de modo que x ₁ ≤ ... ≤ x _m . Existe una permutación p en los índices de modo que, con esta permutación, los rectángulos se ordenarían de abajo a arriba, es decir, y _{p (1)} ≤ ... ≤ y _{p ( m )} . Dados cuatro índices i ₁ ≤ i ₂ y j ₁ ≤ j ₂ , el conjunto E( i ₁ , i ₂ , j ₁ , j ₂ ) contiene los índices de todos los rectángulos cuya esquina inferior izquierda está en el rectángulo [ x _{i 1} , x _{i 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 ₁ ≤ i ₂ y j ₁ ≤ j ₂ , se cumple al menos una de las siguientes condiciones para E( i ₁ , i ₂ , j ₁ , j ₂ ):

1. E( i ₁ , i ₂ , j ₁ , j ₂ ) contiene como máximo un elemento;
2. La unión de los segmentos horizontales ( x _i , x _i + w _i ), sobre todo i en E( i ₁ , i ₂ , j ₁ , j ₂ ), está formada por al menos dos intervalos disjuntos;
3. La unión de los segmentos verticales ( y _i , y _i + h _i ), sobre todo i en E( i ₁ , i ₂ , j ₁ , j ₂ ), está formada por al menos dos intervalos disjuntos.

La condición 2 implica que los rectángulos en E( i ₁ , i ₂ , j ₁ , j ₂ ) pueden separarse mediante un corte vertical (que pase entre los dos intervalos horizontales disjuntos); la condición 3 implica que los rectángulos en E( i ₁ , i ₂ , j ₁ , j ₂ ) 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 comprobar mediante el siguiente algoritmo.

• En cada iteración, divida un patrón dado, que contenga al menos dos rectángulos, en dos subpatrones disjuntos utilizando un corte de guillotina y repita el proceso en cada subpatrón.
• Deténgase cuando todos los subpatrones contengan un rectángulo (en cuyo caso la respuesta es "sí") o no sean posibles más cortes de guillotina (en cuyo caso la respuesta es "no").

Para encontrar un corte de guillotina para un patrón determinado se necesita lo siguiente:

• Determinar los m intervalos horizontales y ordenarlos de izquierda a derecha; determinar los m intervalos verticales y ordenarlos de abajo a arriba. Esto lleva tiempo O( m log m ).
• Fusionar intervalos horizontales superpuestos y fusionar intervalos verticales superpuestos. Esto lleva tiempo O( m ).
• Si, después de la fusión, hay al menos dos intervalos horizontales disjuntos, entonces es posible un corte de guillotina vertical; si hay al menos dos intervalos verticales disjuntos, entonces es posible un corte horizontal; de lo contrario, no es posible ningún corte.

El paso de ordenación 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 ² ).

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 se pueden separar mediante cortes de guillotina.

La condición necesaria y suficiente se puede utilizar para presentar el problema de corte en tiras con guillotina como un programa lineal entero mixto . ^{[5] : sec.5} Su modelo tiene 3 n ⁴ /4 variables binarias y 2 n ⁴ restricciones, y se considera que no es útil en la práctica.

Encontrar un patrón de corte óptimo

Se trata de variantes de los problemas de corte bidimensional , empaquetamiento en contenedores y empaquetamiento rectangular , donde los cortes están restringidos a ser cortes de guillotina. ^[6]

• En el problema básico ( no ponderado ) de corte con guillotina, el resultado requerido es una secuencia de cortes de guillotina que produzcan piezas de las dimensiones objetivo, de modo que se maximice el área total de las piezas producidas (equivalentemente, se minimice el desperdicio del rectángulo en bruto).
• 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 desperdicios) 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 existe 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 objetivo 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 de corte de tiras con 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 se minimice el material total utilizado (equivalentemente, la altura total). Es una variante del problema de empaquetamiento de tiras bidimensional .
• En el problema de minimización de existencias , hay una cantidad infinita de hojas de existencias de las mismas dimensiones y el objetivo es cortar todos los rectángulos de destino requeridos utilizando la menor cantidad posible de hojas. ^[5] Es una variante del problema de empaquetamiento en contenedores bidimensional . ^[7]
• El corte en guillotina en k etapas es una variante restringida del corte en guillotina en el que el corte se realiza en k etapas como máximo : en la primera etapa, solo se realizan cortes horizontales; en la segunda etapa, solo se realizan cortes verticales; y así sucesivamente.
  • En la variante de dos etapas, otra distinción 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 ubicaciones posiblemente diferentes (llamadas "libres"). ^[8]
• 1-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 2-simple es un patrón 1-simple tal que cada parte es en sí misma un patrón 1-simple. Los patrones de corte p -simples se pueden definir 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 tienen 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-hard . Debido a su importancia práctica, se han ideado varios algoritmos exactos y algoritmos de aproximación .

• Gilmore y Gomory ^{[11] [12]} presentaron una recursión de programación dinámica para cortes de guillotina tanto por etapas como sin etapas. Sin embargo, más tarde se demostró ^{[13] [2]} que ambos algoritmos contenían errores. Beasley ^[2] presentó un algoritmo de programación dinámica correcto.
• Herz ^[13] y Christofides y Whitlock ^[14] presentaron procedimientos de búsqueda de árboles para el corte con 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 de guillotina con doble restricción. Se trata de un algoritmo de ramificación y acotación de abajo hacia arriba que utiliza la búsqueda de mejor primero .
• Clautiaux, Jouglet y Moukrim ^[4] proponen un algoritmo exacto para el problema de decisión. Su algoritmo utiliza una representación compacta de clases de patrones de corte de guillotina, utilizando un gráfico dirigido que ellos llaman el 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, uno puede recuperar una secuencia de construcción recursiva que representa una clase de patrón de corte. Cada gráfico de guillotina contiene entre m y 2 arcos m -2. Un tipo especial de gráficos de guillotina llamados gráficos de guillotina normales tienen la propiedad interesante 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 ; hay una correspondencia uno a uno entre dichos gráficos y las clases de patrones de corte. Luego resuelven el problema de optimización utilizando 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 sobre cortes de guillotina restringidos sin etapas (con límites superiores de cantidad), tanto ponderados como no ponderados. Hay dos enfoques principales para soluciones exactas: programación dinámica y búsqueda de árbol (ramificación y límite). 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 inferiores y superiores 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, con 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 de material". Conferencia internacional IEEE de 2011 sobre ingeniería industrial y gestión de ingeniería . 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 de corte ortogonal de material". Revista internacional de informática cognitiva e inteligencia natural (IJCINI) 13, n.º 4 (2019): 91–111.

Implementaciones

• McHale y Shah ^[17] escribieron un programa Prolog que implementa un algoritmo que funciona en cualquier momento : genera soluciones aproximadamente óptimas en un tiempo determinado y luego las mejora si el usuario le concede más tiempo. El programa fue utilizado por un productor de papel especial y redujo el tiempo necesario para el diseño de hojas y el desperdicio.

Separación con guillotina

La separación por guillotina es un problema relacionado en el que la entrada es una colección de n objetos convexos disjuntos por pares en el plano, y el objetivo es separarlos utilizando 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 sea separable por guillotina.

Pach y Tardos ^[19] demostraron:

• Si todos los objetos tienen un tamaño similar, entonces 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 separable de tamaño . Demostración : construye una cuadrícula con un tamaño de celda de 8 R por 8 R. Mueve la cuadrícula de manera uniforme al azar. Cada objeto es intersectado por una línea horizontal con probabilidad 1/4 y por una línea vertical con probabilidad 1/4 también, por lo que el número esperado de objetos intersectados es . Por lo tanto, existen líneas de cuadrícula que se intersecan como máximo en objetos. 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. Elige un solo objeto de cada celda y sepáralo 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 ${\displaystyle {\frac {\pi r^{2}}{128R^{2}}}n\approx {\frac {1}{40.7(R/r)^{2}}}n}$ ${\displaystyle n/2}$ ${\displaystyle n/2}$ ${\displaystyle (8R)^{2}}$ ${\displaystyle \pi r^{2}}$ ${\displaystyle {\frac {(8R)^{2}}{\pi r^{2}}}}$ ${\displaystyle {\frac {n}{2}}/{\frac {(8R)^{2}}{\pi r^{2}}}={\frac {\pi r^{2}}{128R^{2}}}n.}$ ${\displaystyle {\frac {1}{27}}n.}$
• Si los objetos son segmentos de línea recta, entonces, en algunos casos, solo la mayoría de ellos pueden separarse. En particular, para cada entero positivo k , existe una familia de intervalos disjuntos tales que la mayoría de ellos pueden separarse. ${\displaystyle O(n^{\log _{3}{2}})\approx O(n^{0.63})}$ ${\displaystyle 3^{k}}$ ${\displaystyle 2^{k}}$
• En cualquier colección de n objetos convexos, al menos pueden separarse. ${\displaystyle \Omega (n^{1/3})}$
• En cualquier conjunto de n segmentos de línea recta, al menos se pueden separar. Conjeturan que el peor caso se puede alcanzar mediante segmentos de línea. ${\displaystyle \Omega (n^{1/2})}$
• En cualquier conjunto de n rectángulos paralelos a los ejes, al menos pueden separarse. Conjeturan que pueden separarse; esta conjetura aún está abierta. ${\displaystyle n/(2\log {n})}$ ${\displaystyle \Omega (n)}$
• En cualquier colección de objetos R - fat (el disco contenedor más pequeño es como máximo R veces el disco contenedor más grande), se pueden guardar al menos objetos , donde es una constante que depende solo de R. ${\displaystyle n/(c_{R}\log {n})}$ ${\displaystyle c_{R}}$
  • Un teorema análogo es válido también en dimensiones superiores: el número de objetos separables es . ${\displaystyle n/c(R,d)(\log {n})^{d}}$
• Todas estas subfamilias separables se pueden construir en tiempo . Si los objetos son polígonos con N lados en total, entonces las líneas de separación se pueden calcular en tiempo . ${\displaystyle O(n\log {n})}$ ${\displaystyle O(N+n\log {n})}$

Abed, Chalermsook, Correa, Karrenbauer, Pérez-Lantero, Soto y Wiese ^[20] demostraron:

• En cualquier colección de n cuadrados unitarios paralelos a los ejes, 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 los ejes, al menos n /81 pueden separarse.
• En cualquier colección de n cuadrados paralelos a los ejes con pesos, se puede separar al menos 4/729 del peso total.
• En cualquier colección de n cubos d- dimensionales paralelos a los ejes con pesos, se puede separar el peso total. ${\displaystyle 1/2^{O(d)}}$
• Respecto a la conjetura de que es posible separar rectángulos de ejes paralelos, si bien no la resuelven, muestran que, de ser correcta, entonces implica un algoritmo de aproximación O(1) al problema del máximo conjunto disjunto de rectángulos de ejes paralelos en el tiempo . ${\displaystyle \Omega (n)}$ ${\displaystyle O(n^{5})}$

Khan y Pittu ^[21] demostraron:

• Con rectángulos con ejes n paralelos, si solo se permiten etapas, entonces no es posible separar rectángulos. ${\displaystyle o(\log \log n)}$ ${\displaystyle \Omega (n)}$
• Cuando los rectángulos están ponderados, si solo se permiten etapas, entonces no es posible separarlos del peso. ${\displaystyle o(\log {n}/\log \log {n})}$ ${\displaystyle \Omega (n)}$
• Existe un algoritmo simple de dos etapas que separa rectángulos. El algoritmo divide los rectángulos en subconjuntos (llamados "niveles") y elige el nivel con el mayor número de rectángulos. Cada nivel se puede separar mediante dos cortes de guillotina. ^{[21] : Teoría 14} Un algoritmo mejorado puede separar rectángulos. ${\displaystyle n/(1+\log _{2}{n})}$ ${\displaystyle 1+\log _{2}{n}}$ ${\displaystyle n/\log _{3}{(n+2)}}$
• En cualquier colección de rectángulos gordos , se pueden separar. ${\displaystyle \Omega (n)}$
• En cualquier colección de n cuadrados paralelos a los ejes, al menos n /40 pueden estar separados.
• En cualquier colección de n cuadrados paralelos a los ejes 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 hiperplanos

Más variantes

Algunas variantes del problema estudiadas recientemente incluyen:

• Corte con 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

1. Tlilane, Lydia; Viaud, Quentin (18 de mayo de 2018). "Challenge ROADEF / EURO 2018 Cutting Optimization Problem Description" (PDF) . Desafío ROADEF/EURO . ROADEF . Consultado el 13 de junio de 2019 .
2. 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. S2CID  58059319.
3. 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] Archivado el 20 de diciembre de 2016 en Wayback Machine.
4. Clautiaux, François; Jouglet, Antoine; Moukrim, Aziz (17 de octubre de 2011). "Un nuevo modelo gráfico-teórico para el problema del corte con guillotina". INFORMS Journal on Computing . 25 (1): 72–86. doi :10.1287/ijoc.1110.0478. ISSN  1091-9856.
5. 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.
6. M. Hifi, R. M'Hallah y T. Saadi, Algoritmos aproximados y exactos para el problema de corte de material en guillotina bidimensional con doble restricción. Optimización computacional y aplicaciones, volumen 42, número 2 (2009), 303-326, doi :10.1007/s10589-007-9081-5
7. 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 empaquetamiento de bins bidimensional con orientación fija". Computers & Operations Research . 34 (8): 2223–2250. doi :10.1016/j.cor.2005.08.012. ISSN  0305-0548.
8. Russo, Mauro; Boccia, Maurizio; Sforza, Antonio; Sterle, Claudio (2020). "Problema de corte de guillotina bidimensional restringido: revisión y categorización de límites superiores". Transacciones internacionales en investigación operativa . 27 (2): 794–834. doi :10.1111/itor.12687. ISSN  1475-3995. S2CID  195551953.
9. Scheithauer, Guntram (1993). "Cálculo de patrones de corte de guillotina φ-simples óptimos" (PDF) . Revista de procesamiento de información y cibernética . 29 (2): 115–128.
10. Tarnowski, AG; Terno, J.; Scheithauer, G. (1994-11-01). "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.
11. Gilmore, PC; Gomory, RE (1965-02-01). "Problemas de corte de material en varias etapas de dos y más dimensiones". Investigación de operaciones . 13 (1): 94–120. doi :10.1287/opre.13.1.94. ISSN  0030-364X.
12. Gilmore, PC; Gomory, RE (1966-12-01). "La teoría y el cálculo de funciones de mochila". Investigación de operaciones . 14 (6): 1045–1074. doi :10.1287/opre.14.6.1045. ISSN  0030-364X.
13. Herz, JC (septiembre de 1972). "Procedimiento computacional recursivo para el corte de material bidimensional". IBM Journal of Research and Development . 16 (5): 462–469. doi :10.1147/rd.165.0462. ISSN  0018-8646.
14. Christofides, Nicos; Whitlock, Charles (1977-02-01). "Un algoritmo para problemas de corte bidimensionales". Investigación de operaciones . 25 (1): 30–44. doi :10.1287/opre.25.1.30. ISSN  0030-364X.
15. OBG Masden (1980), Documento de trabajo IMSOR, Universidad técnica de Dinamarca, Lyngby
16. Wang, PY (1 de junio de 1983). "Dos algoritmos para problemas de corte de material bidimensionales restringidos". Investigación de operaciones . 31 (3): 573–586. doi :10.1287/opre.31.3.573. ISSN  0030-364X.
17. Michael L. McHale, Roshan P. Shah Reducir la guillotina a su tamaño ideal. Revista PC AI, volumen 13, número 1, enero/febrero de 1999. http://www.amzi.com/articles/papercutter.htm
18. Problema presentado en ACCOTA '96, Aspectos combinatorios y computacionales de la topología y el álgebra de optimización, Taxco, México 1996
19. Pach, J.; Tardos, G. (2000). "Corte de vidrio". Geometría discreta y computacional . 24 (2–3): 481–496. doi : 10.1007/s004540010050 . ISSN  0179-5376. S2CID  1737527.
20. Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). Sobre secuencias de corte con guillotina. págs. 1-19. doi : 10.4230/LIPIcs.APPROX-RANDOM.2015.1 . ISBN 978-3-939897-89-7.
21. Khan, Arindam; Pittu, Madhusudhan Reddy (2020). Byrka, Jaros\law; Meka, Raghu (eds.). "Sobre la separabilidad de cuadrados y rectángulos mediante guillotina". Aproximación, aleatorización y optimización combinatoria. Algoritmos y técnicas (APPROX/RANDOM 2020) . Leibniz International Proceedings in Informatics (LIPIcs). 176. Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum für Informatik: 47:1–47:22. doi : 10.4230/LIPIcs.APPROX/RANDOM.2020.47 . ISBN . 978-3-95977-164-1.
22. Martin, Mateus; Oliveira, José Fernando; Silva, Elsa; Morabito, Reinaldo; Munari, Pedro (8 de noviembre de 2020). "Problemas de corte de guillotina tridimensionales 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. S2CID  228839108.
23. 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 empaquetamiento de bins de múltiples tamaños tridimensional (MBSBPP): un caso industrial tunecino". 2014 Conferencia internacional sobre tecnologías de control, decisión e información (CoDIT) . pp. 219–224. doi :10.1109/CoDIT.2014.6996896. ISBN 978-1-4799-6773-5.S2CID18598442  .​
24. Martin, Mateus; Hokama, Pedro HDB; Morabito, Reinaldo; Munari, Pedro (2020-05-02). "El problema de corte de guillotina bidimensional restringido con defectos: una formulación 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. S2CID  197434029.

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 de material". Conferencia internacional IEEE de 2011 sobre ingeniería industrial y gestión de ingeniería . IEEE, 2011.