Resumo: Neste trabalho é realizado um estudo experimental de técnicas de otimização para gerar soluções eficientes para o problema do corte bidimensional, que pode ser definido como: dado um número finito n de itens retangulares de largura li, comprimento Ci e demanda di, a serem obtidos de retângulos maiores de dimensão LxC, encontrar padrões de corte que atendam a uma demanda de itens utilizando o menor número possível de retângulos maiores. O problema foi formulado através de um modelo de programação linear inteira. Para obter soluções de custo reduzido para o problema, aplicamos o método de geração de colunas, obtendo então soluções viáveis para o problema relaxado do programa linear inteiro. Utilizamos um algoritmo de aproximação para obter uma solução inicial de qualidade e métodos de arredondamento com tratamento de problema residual para transformar a solução fracionária em soluções viáveis para o problema. Finalmente, diversos estudos são realizados através de testes computacionais Ver menos

Abstract: In this work we describe an experimental study of optimization techniques to generate efficient results for the two-dimensional cutting stock problem which can be defined as follows: given a finite number n of rectangular items of width li, length Ci and demand di, to be cut from larger rectangles with dimensions LxC, find cutting pattems which attend the demand of the requested items minimizing the number of larger rectangles. The problem is formulated as an integer programming mode!. To obtain solutions with reduced cost to the problem, we apply the column generation method, obtaining feasible solutions for the relaxed integer programo We use an approximation algorithm to generate a good initial solution and rounding techniques with treatment of the residual problem to transform the fractional solution into feasible solutions to the problem. Finally, several studies are realized through computational experiments Ver menos