Tarea de corte de guillotina

El problema del corte en guillotina  es un problema de geometría combinatoria , cercano al problema de los problemas de corte y empaque en contenedores [1] . La cuestión del problema es cómo sacar el máximo número de hojas de tamaño rectangular a partir de una hoja de mayor tamaño, realizando únicamente cortes de guillotina , es decir, cortes rectos de borde a borde.

Al igual que el problema del corte, es un problema NP-completo . Existe una serie de algoritmos aproximados y exactos para resolver el problema del corte en guillotina [2] [3] [4] .

La tarea de corte con guillotina es importante en la producción de láminas de vidrio: las láminas de vidrio se muescan horizontal y verticalmente y luego se rompen a lo largo de la muesca.

Notas

1. ↑ 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]  (enlace no disponible)
2. ↑ Michael L. McHale, Roshan P. Shah Cortando la guillotina a medida. Revista PC AI, volumen 13, número 1, enero/febrero de 1999. http://www.amzi.com/articles/papercutter.htm Archivado el 29 de noviembre de 2014 en Wayback Machine .
3. ↑ M. Hifi, R. M'Hallah y T. Saadi, Algoritmos aproximados y exactos para el problema del 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
4. ↑ François Clautiaux, Antoine Jouglet, Aziz Moukrim, Un nuevo modelo teórico gráfico para el problema del corte con guillotina. INFORMA Revista de Computación Octubre 2011 ijoc.1110.0478 pp. 1-15