miniaturadaimagem|Chapa otimizada com retângulos menores que podem ser formados a partir de cortes de 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.
Como problema de corte, é NP-difícil, mas várias soluções aproximadas e exata tem sido concebidas.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.htmM. 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-5Franç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
Definição Um corte de guilhotina é um corte paralelo a um dos lados e percorre de um lado até o outro. Cada maneira de se cortar é chamado de um padrão de corte (ou simplesmente padrão), normalmente representado através de coordenadas cartesianas. Ao cortar, pode-se obter um resto utilizável ou que será descartado como sucata.
Como problema de corte, é NP-difícil, mas várias soluções aproximadas e exata tem sido concebidas.
História Os problemas da guilhotina em uma e duas dimensões são estudadas desde a década de 1960.
Aplicações O problema aparece em uma vasta diversidade de processos industriais que usufruem de materiais como papel, vidro, aço, madeira e tecido que precisam ser cortados em pedaços menores, atendando-se aos diferentes tamanhos e quantidades pedidas. Na usinagem de vidro, por exemplo, 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.
Afim de que empresas apresentem vantagens sobre outras, surge o interesse para que o custo operacional seja o menor possível e que, ao mesmo tempo, as sobras possam ser utilizadas no futuro, assim, o estudo sobre o problema da guilhotina se faz necessário.
Bibliografia
Glauber F. Cintra; Algorítimos para Problemas de Corte de Guilhotina Bidimensional; Tese - www.ime.usp.br
Categoria:Geometria discreta Categoria:Problemas matemáticos Categoria:Otimização