Problema da guilhotina
O problema da guilhotina é um problema de geometria combinatória e na indústria, como de impressão e outras.
Intimamente relacionado com problemas de empacotamento e, especificamente, com problemas de corte e empacotamento de bins, que é a questão de como obter o número máximo de folhas de um tamanho retangular a partir de uma folha maior, apenas com cortes ortogonais que bissectam um componente da folha são permitidos, como em uma guilhotina de corte de papel.
O problema da guilhotina é importante na usinagem de vidro. As folhas de vidro são marcadas ao longo de linhas horizontais e verticais e, em seguida, ao longo destas linhas quebradas para obter painéis menores.
Como problema de corte, é NP-difícil, mas várias soluções aproximadas e exata tem sido concebidas.[1][2][3]
Referências
- ↑ 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
- ↑ 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
- ↑ François Clautiaux, Antoine Jouglet, Aziz Moukrim, A New Graph-Theoretical Model for the Guillotine-Cutting Problem. INFORMS Journal on Computing October 2011 ijoc.1110.0478 pp. 1–15
Ligações externas editar
- Glauber F. Cintra; O Problema de Corte de Guilhotina com Placas Variadas - www.ime.usp.br
- Glauber F. Cintra; Algorítimos para Problemas de Corte de Guilhotina Bidimensional; Tese - www.ime.usp.br