Corte con guillotina

Un corte imposible con guillotina: estos rectángulos "no pueden" separarse únicamente a base de cortes bisecantes a lo largo del plano

El corte con guillotina es el proceso de producir formas rectangulares pequeñas 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 bisectriz recta que va desde un borde de un rectángulo existente hasta el borde opuesto, de manera similar a lo que hace una guillotina para papel.

El corte con guillotina es particularmente común en la industria del vidrio. Las láminas de vidrio se marcan en líneas horizontales y verticales y luego se rompen según estas líneas para obtener paneles más pequeños.^[1] El procedimiento también es útil para cortar placas de acero, cortar láminas de madera para fabricar muebles, y para cortar el cartón empleado en la fabricación de cajas.^[2]

Existen varios problema de optimización relacionados con el corte con guillotina, tales como maximizar el área total de las piezas producidas o su valor total; o también minimizar la cantidad de desperdicios (partes no utilizadas) de la hoja grande, o el número total de hojas. Se han estudiado en geometría discreta, investigación de operaciones e ingeniería industrial.^[3]

Un problema relacionado pero diferente es la partición con guillotina. En este problema, las dimensiones de los rectángulos pequeños no están fijadas de antemano. El desafío surge del hecho de que la hoja original puede 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 el número de rectángulos pequeños o minimizar la longitud total de los cortes.

Terminología y supuestos[editar]

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 común, es la hoja rectangular en bruto que se debe cortar. Se caracteriza por su ancho W₀ y alto H₀, que son las entradas principales del problema.
Los rectángulos pequeños, también llamados elementos, son las salidas requeridas del corte. Se caracterizan por su ancho w_i y alto h_i y por 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) suele denominarse 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 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 generar un nuevo rectángulo uniendo 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 un ancho máximo(w_i,w_j) y una altura h_i+h_j. Cada patrón se puede representar como una secuencia recursiva de construcciones, que 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 deseadas. A menudo se hacen las siguientes suposiciones:^[2]

Todos los cortes tienen ancho cero. Esto no supone mucha pérdida de 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 de destino no se pueden rotar, es decir, w-by-h no es el mismo tipo que h-by-w. Esto tampoco supone una pérdida de generalidad significativa, ya que la variante en la que los rectángulos se pueden rotar se puede reducir a la variante no rotativa agregando explícitamente los patrones rotados.

Comprobación de un patrón dado[editar]

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 único rectángulo de cada dimensión objetivo). El objetivo es decidir si este patrón se puede implementar utilizando únicamente cortes de guillotina y, de ser así, encontrar una secuencia para 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] fijaron una condición más fuerte, que es a la vez 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 sobre los índices tal que, con esta permutación, los rectángulos quedarían ordenados de abajo hacia arriba, es decir, y_p₍₁₎ = ... = 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₁,x_i₂] X [y_p_(j1),y_p_(j2)]. Un patrón de corte es un patrón de guillotina si y solo si, para todas las cuaternas de índices i₁ = i₂ y j₁ = j₂, al menos se cumple una de las siguientes condiciones para E(i₁,i₂,j₁,j₂):

E(i₁,i₂,j₁,j₂) contiene como máximo un elemento
La unión de los segmentos horizontales (x_i, x_i+w_i), sobre todas las i en E(i₁,i₂ ,j₁,j₂), se compone de al menos dos intervalos disjuntos
La unión de los segmentos verticales (y_i, y_i+h_i), sobre todas las i en E(i₁,i₂ ,j₁,j₂), se compone de 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 va entre los dos intervalos horizontales). La condición 3 implica que los rectángulos en E(i₁,i₂,j₁,j₂) se pueden separar 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 con guillotina.

Esta condición se puede verificar mediante el siguiente algoritmo:

En cada iteración, divídase un patrón determinado, que contenga al menos dos rectángulos, en dos subpatrones separados usando un corte de guillotina y repítase 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 sea "no").

Encontrar un corte con guillotina para un patrón determinado se realiza de la siguiente manera:

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

La ordenación de los pasos 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 pueden separarse mediante cortes con guillotina.

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

Encontrar un patrón de corte óptimo[editar]

Estas son variantes de los problemas bidimensionales de corte de material, empaquetado en contenedores y empaquetado de rectángulos, donde los cortes están obligados a ser cortes con guillotina.^[6]

En el problema de corte con guillotina básico ("no ponderado"), el resultado requerido es una secuencia de cortes que producen piezas de las dimensiones objetivo, de manera que se maximiza el área total de las piezas producidas (equivalentemente, que se minimicen los desechos del proceso).
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 mediante cortes de guillotina.^[4]
En el problema del 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 el material total utilizado (equivalentemente, la altura total) se minimice. Es una variante del Problema de empaquetado en tiras bidimensional.
En el problema de minimización de material, hay un número infinito de hojas de material de las mismas dimensiones y el objetivo es cortar todos los rectángulos objetivo necesarios utilizando el menor número posible de hojas.^[5] Es una variante del problema de empaquetado en contenedores bidimensional.^[7]
El corte con guillotina en k etapas es una variante restringida del corte con guillotina, en la que el corte se realiza como máximo en k etapas: en la primera etapa, solo se realizan cortes horizontales; en la segunda etapa solo se realizan cortes verticales; etcétera.
- En la variante de 2 etapas, otra distinción es si todas las tiras resultantes de la primera etapa se cortan en los mismos lugares (llamados "1 grupo") o en dos lugares diferentes (llamados "2 grupos") o en posiblemente diferentes ubicaciones (llamadas "libres").^[8]
1-corte con guillotina simple es una variante restringida del corte de guillotina en la que cada corte separa un solo rectángulo.
- Un 2-corte con guillotina simple es un patrón de 1 simples, de modo que cada parte es en sí mismo un patrón de p 1-cortes simples: los patrones de corte simples se pueden definir de forma recursiva.^[9]

Algoritmos de optimización[editar]

El caso especial en el que solo hay un tipo (es decir, todos los rectángulos objetivo son idénticos y están en la misma orientación) se denomina problema de "carga de palet con guillotina". Tarnowski, Terno y Scheithauer^[10] idearon 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] desarrollaron un sisteam de programación dinámica recursivo para el corte con 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] idearon procedimientos de búsqueda en árbol para el corte con guillotina sin etapas.
Masden^[15] y Wang^[16] presentaron algoritmos heurísticos.
Hiffi, M'Hallah y Saadi^[6] propusieron un algoritmo para el problema del corte con guillotina doblemente restringido. Es un algoritmo de ramificación y poda ascendente que utiliza la mejor primera búsqueda.
Clautiaux, Jouglet y Moukrim^[4] propusieron un algoritmo exacto para el problema de decisión. Su algoritmo utiliza una representación compacta de clases de patrones de corte con guillotina, utilizando un grafo dirigido al que llaman "grafo de guillotina". Cada arco en este grafo está coloreado en uno de dos colores: "horizontal" o "vertical". Cada ciclo dirigido monocromático en este grafo 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 grafo de guillotina contiene entre m y 2m-2 arcos. Un tipo especial de grafos de guillotina llamados "grafos de guillotina normales" tienen la interesante propiedad de contener un camino hamiltoniano único. La clasificación de los vértices según este circuito convierte al grafo en un "grafo de guillotina normal bien ordenado". Existe una correspondencia uno a uno entre dichos grafos y las clases de patrones de corte. Entonces, resuelven el problema de optimización utilizando programación con restricciones en el espacio de grafos de guillotina normales bien ordenados.
Russo, Boccia, Sforza y Sterle^[8] revisan más de 90 artículos que tratan sobre el corte con guillotina restringido 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 en árbol" (ramificación y vinculación). Los enfoques de búsqueda en á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 superior e inferior para recortar el espacio de búsqueda de manera eficiente. Estos límites a menudo provienen de soluciones a variantes relacionadas, como 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 del material de corte ortogonal". Conferencia Internacional IEEE 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 del material de corte ortogonal". Revista Internacional de Informática Cognitiva e Inteligencia Natural (IJCINI) 13, no. 4 (2019): 91-111.

Desarrollos[editar]

McHale and Shah^[17] escribió un programa Prolog que contiene un algoritmo anytime: 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 y, al mismo tiempo, ha reducido el desperdicio.

Separación con guillotina[editar]

La separación con guillotina es un problema relacionado en el que la entrada es una colección de n formas convexas separadas por pares en el plano, y el objetivo es separarlos usando una secuencia de cortes de guillotina. Obviamente, puede que no sea posible separarlas todas. Jorge Urrutia Galicia planteó la cuestión de si es posible separar una fracción constante de ellos,^[18] es decir, si existe una constante c tal que, en cualquier colección de tamaño n, hay un subconjunto de tamaño cn que es separable con guillotina.

Pach y Tardos^[19] demostraron que:

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

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

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

Khan y Pittu^[21] demostraron:

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

Véase también[editar]

Más variantes[editar]

Algunas variantes del problema 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[editar]

↑ Tlilane, Lydia; Viaud, Quentin (18 de mayo de 2018). «Challenge ROADEF / EURO 2018 Cutting Optimization Problem Description». Challenge ROADEF/EURO. ROADEF. Consultado el 13 de junio de 2019.
↑ ^a ^b ^c ^d Beasley, J. E. (1 de abril de 1985). «Algorithms for Unconstrained Two-Dimensional Guillotine Cutting». Journal of the Operational Research Society 36 (4): 297-306. ISSN 0160-5682. S2CID 58059319. doi:10.1057/jors.1985.51.
↑ Gerhard Wäscher, Heike Haußner, Holger Schumann, An improved typology of cutting and packing problems, 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). «A New Graph-Theoretical Model for the Guillotine-Cutting Problem». INFORMS Journal on Computing 25 (1): 72-86. ISSN 1091-9856. doi:10.1287/ijoc.1110.0478.
↑ ^a ^b ^c Ben Messaoud, Said; Chu, Chengbin; Espinouse, Marie-Laure (16 de noviembre de 2008). «Characterization and modelling of guillotine constraints». European Journal of Operational Research (en inglés) 191 (1): 112-126. ISSN 0377-2217. doi:10.1016/j.ejor.2007.08.029.
↑ ^a ^b M. Hifi, R. M’Hallah and T. Saadi, Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem. Computational Optimization and Applications, Volume 42, Number 2 (2009), 303-326, doi 10.1007/s10589-007-9081-5
↑ Carlier, Jacques; Clautiaux, François; Moukrim, Aziz (1 de agosto de 2007). «New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation». Computers & Operations Research (en inglés) 34 (8): 2223-2250. ISSN 0305-0548. doi:10.1016/j.cor.2005.08.012.
↑ ^a ^b Russo, Mauro; Boccia, Maurizio; Sforza, Antonio; Sterle, Claudio (2020). «Constrained two-dimensional guillotine cutting problem: upper-bound review and categorization». International Transactions in Operational Research (en inglés) 27 (2): 794-834. ISSN 1475-3995. S2CID 195551953. doi:10.1111/itor.12687.
↑ Scheithauer, Guntram (1993). «Computation of optimal φ-simple guillotine cutting patterns». Journal of Information Processing and Cybernetics 29 (2): 115-128.
↑ Tarnowski, A. G.; Terno, J.; Scheithauer, G. (1 de noviembre de 1994). «A Polynomial Time Algorithm For The Guillotine Pallet Loading Problem». INFOR: Information Systems and Operational Research 32 (4): 275-287. ISSN 0315-5986. doi:10.1080/03155986.1994.11732257.
↑ Gilmore, P. C.; Gomory, R. E. (1 de febrero de 1965). «Multistage Cutting Stock Problems of Two and More Dimensions». Operations Research 13 (1): 94-120. ISSN 0030-364X. doi:10.1287/opre.13.1.94.
↑ Gilmore, P. C.; Gomory, R. E. (1 de diciembre de 1966). «The Theory and Computation of Knapsack Functions». Operations Research 14 (6): 1045-1074. ISSN 0030-364X. doi:10.1287/opre.14.6.1045.
↑ ^a ^b Herz, J. C. (September 1972). «Recursive Computational Procedure for Two-dimensional Stock Cutting». IBM Journal of Research and Development 16 (5): 462-469. ISSN 0018-8646. doi:10.1147/rd.165.0462.
↑ Christofides, Nicos; Whitlock, Charles (1 de febrero de 1977). «An Algorithm for Two-Dimensional Cutting Problems». Operations Research 25 (1): 30-44. ISSN 0030-364X. doi:10.1287/opre.25.1.30.
↑ O. B. G. Masden (1980), IMSOR working paper, Technical university of Denmark, Lyngby
↑ Wang, P. Y. (1 de junio de 1983). «Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems». Operations Research 31 (3): 573-586. ISSN 0030-364X. doi:10.1287/opre.31.3.573.
↑ Michael L. McHale, Roshan P. Shah Cutting the Guillotine Down to Size. PC AI magazine, Volume 13, Number 1 Jan/Feb 99. http://www.amzi.com/articles/papercutter.htm
↑ Problem presented at ACCOTA '96, Combinatorial and Computational Aspects of Optimization Topology and Algebra, Taxco, Mexico 1996
↑ Pach, J.; Tardos, G. (2000). «Cutting Glass». Discrete and Computational Geometry (en inglés) 24 (2–3): 481-496. ISSN 0179-5376. S2CID 1737527. doi:10.1007/s004540010050.
↑ Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). On Guillotine Cutting Sequences. pp. 1-19. ISBN 978-3-939897-89-7. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.1.
↑ ^a ^b Khan, Arindam; Pittu, Madhusudhan Reddy (2020). «On Guillotine Separability of Squares and Rectangles». En Byrka, Jaros\law; Meka, Raghu, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs) (Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik) 176: 47:1-47:22. ISBN 978-3-95977-164-1. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.47.
↑ Martin, Mateus; Oliveira, José Fernando; Silva, Elsa; Morabito, Reinaldo; Munari, Pedro (8 de noviembre de 2020). «Three-dimensional guillotine cutting problems with constrained patterns: MILP formulations and a bottom-up algorithm». Expert Systems with Applications (en inglés) 168: 114257. ISSN 0957-4174. S2CID 228839108. doi:10.1016/j.eswa.2020.114257.
↑ Baazaoui, M.; Hanafi, S.; Kamoun, H. (1 de noviembre de 2014). «A Mathematical formulation and a lower bound for the three-dimensional multiple-bin-size bin packing problem (MBSBPP): A Tunisian industrial case». 2014 International Conference on Control, Decision and Information Technologies (CoDIT). pp. 219-224. ISBN 978-1-4799-6773-5. S2CID 18598442. doi:10.1109/CoDIT.2014.6996896.
↑ Martin, Mateus; Hokama, Pedro H. D. B.; Morabito, Reinaldo; Munari, Pedro (2 de mayo de 2020). «The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm». International Journal of Production Research 58 (9): 2712-2729. ISSN 0020-7543. S2CID 197434029. doi:10.1080/00207543.2019.1630773.

Bibliografía[editar]

Abou Msabah, Slimane, and Ahmed Riadh Baba-Ali. "A new guillotine placement heuristic combined with an improved genetic algorithm for the orthogonal cutting-stock problem." 2011 IEEE International Conference on Industrial Engineering and Engineering Management. IEEE, 2011.

Datos: Q5616328

[1] Tlilane, Lydia; Viaud, Quentin (18 de mayo de 2018). «Challenge ROADEF / EURO 2018 Cutting Optimization Problem Description». Challenge ROADEF/EURO. ROADEF. Consultado el 13 de junio de 2019.

[:0-2] Beasley, J. E. (1 de abril de 1985). «Algorithms for Unconstrained Two-Dimensional Guillotine Cutting». Journal of the Operational Research Society 36 (4): 297-306. ISSN 0160-5682. S2CID 58059319. doi:10.1057/jors.1985.51.

[3] Gerhard Wäscher, Heike Haußner, Holger Schumann, An improved typology of cutting and packing problems, European Journal of Operational Research 183 (2007) 1109–1130, [1]

[:3-4] Clautiaux, François; Jouglet, Antoine; Moukrim, Aziz (17 de octubre de 2011). «A New Graph-Theoretical Model for the Guillotine-Cutting Problem». INFORMS Journal on Computing 25 (1): 72-86. ISSN 1091-9856. doi:10.1287/ijoc.1110.0478.

[:4-5] Ben Messaoud, Said; Chu, Chengbin; Espinouse, Marie-Laure (16 de noviembre de 2008). «Characterization and modelling of guillotine constraints». European Journal of Operational Research (en inglés) 191 (1): 112-126. ISSN 0377-2217. doi:10.1016/j.ejor.2007.08.029.

[:2-6] M. Hifi, R. M’Hallah and T. Saadi, Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem. Computational Optimization and Applications, Volume 42, Number 2 (2009), 303-326, doi 10.1007/s10589-007-9081-5

[7] Carlier, Jacques; Clautiaux, François; Moukrim, Aziz (1 de agosto de 2007). «New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation». Computers & Operations Research (en inglés) 34 (8): 2223-2250. ISSN 0305-0548. doi:10.1016/j.cor.2005.08.012.

[:5-8] Russo, Mauro; Boccia, Maurizio; Sforza, Antonio; Sterle, Claudio (2020). «Constrained two-dimensional guillotine cutting problem: upper-bound review and categorization». International Transactions in Operational Research (en inglés) 27 (2): 794-834. ISSN 1475-3995. S2CID 195551953. doi:10.1111/itor.12687.

[9] Scheithauer, Guntram (1993). «Computation of optimal φ-simple guillotine cutting patterns». Journal of Information Processing and Cybernetics 29 (2): 115-128.

[10] Tarnowski, A. G.; Terno, J.; Scheithauer, G. (1 de noviembre de 1994). «A Polynomial Time Algorithm For The Guillotine Pallet Loading Problem». INFOR: Information Systems and Operational Research 32 (4): 275-287. ISSN 0315-5986. doi:10.1080/03155986.1994.11732257.

[11] Gilmore, P. C.; Gomory, R. E. (1 de febrero de 1965). «Multistage Cutting Stock Problems of Two and More Dimensions». Operations Research 13 (1): 94-120. ISSN 0030-364X. doi:10.1287/opre.13.1.94.

[12] Gilmore, P. C.; Gomory, R. E. (1 de diciembre de 1966). «The Theory and Computation of Knapsack Functions». Operations Research 14 (6): 1045-1074. ISSN 0030-364X. doi:10.1287/opre.14.6.1045.

[:1-13] Herz, J. C. (September 1972). «Recursive Computational Procedure for Two-dimensional Stock Cutting». IBM Journal of Research and Development 16 (5): 462-469. ISSN 0018-8646. doi:10.1147/rd.165.0462.

[14] Christofides, Nicos; Whitlock, Charles (1 de febrero de 1977). «An Algorithm for Two-Dimensional Cutting Problems». Operations Research 25 (1): 30-44. ISSN 0030-364X. doi:10.1287/opre.25.1.30.

[15] O. B. G. Masden (1980), IMSOR working paper, Technical university of Denmark, Lyngby

[16] Wang, P. Y. (1 de junio de 1983). «Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems». Operations Research 31 (3): 573-586. ISSN 0030-364X. doi:10.1287/opre.31.3.573.

[17] Michael L. McHale, Roshan P. Shah Cutting the Guillotine Down to Size. PC AI magazine, Volume 13, Number 1 Jan/Feb 99. http://www.amzi.com/articles/papercutter.htm

[18] Problem presented at ACCOTA '96, Combinatorial and Computational Aspects of Optimization Topology and Algebra, Taxco, Mexico 1996

[19] Pach, J.; Tardos, G. (2000). «Cutting Glass». Discrete and Computational Geometry (en inglés) 24 (2–3): 481-496. ISSN 0179-5376. S2CID 1737527. doi:10.1007/s004540010050.

[20] Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). On Guillotine Cutting Sequences. pp. 1-19. ISBN 978-3-939897-89-7. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.1.

[:6-21] Khan, Arindam; Pittu, Madhusudhan Reddy (2020). «On Guillotine Separability of Squares and Rectangles». En Byrka, Jaros\law; Meka, Raghu, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs) (Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik) 176: 47:1-47:22. ISBN 978-3-95977-164-1. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.47.

[22] Martin, Mateus; Oliveira, José Fernando; Silva, Elsa; Morabito, Reinaldo; Munari, Pedro (8 de noviembre de 2020). «Three-dimensional guillotine cutting problems with constrained patterns: MILP formulations and a bottom-up algorithm». Expert Systems with Applications (en inglés) 168: 114257. ISSN 0957-4174. S2CID 228839108. doi:10.1016/j.eswa.2020.114257.

[23] Baazaoui, M.; Hanafi, S.; Kamoun, H. (1 de noviembre de 2014). «A Mathematical formulation and a lower bound for the three-dimensional multiple-bin-size bin packing problem (MBSBPP): A Tunisian industrial case». 2014 International Conference on Control, Decision and Information Technologies (CoDIT). pp. 219-224. ISBN 978-1-4799-6773-5. S2CID 18598442. doi:10.1109/CoDIT.2014.6996896.

[24] Martin, Mateus; Hokama, Pedro H. D. B.; Morabito, Reinaldo; Munari, Pedro (2 de mayo de 2020). «The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm». International Journal of Production Research 58 (9): 2712-2729. ISSN 0020-7543. S2CID 197434029. doi:10.1080/00207543.2019.1630773.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]