Solução do problema de corte bidimensional de peças retângulares tipo não-guilhotinado usando simulated annealing

Abstract

Os problemas de corte ótimo são considerados como clássicos dentro da pesquisa operacional, dado sua grande área de aplicação na industria e sua alta complexidade matemática e computacional. Um dos problemas mais conhecidos desta classe é o chamado Cutting Stock Problem, o qual permite dividir uma placa em varias peças de diversos tamanhos, com a finalidade de obter a configuração que maximize a área da placa que está sendo utilizada. Dado o nível de dificuldade e a grande quantidade de aplicações deste problemas em diversas áreas, existe muito interesse em criar novos procedimentos eficientes para resolver este tipo de problemas. Nesta dissertação, é apresentado o estado da arte dos diversos problemas de corte bidimensional de peças retangulares em uma única placa, em varias placas e em rolos, considerando a possibilidade de rotacionar as peças em um ângulo de 90 e com restrições de corte tipo não-guilhotinado. Além disso, são descritas as abordagens matemáticas aplicadas pelos diversos pesquisadores dedicados a resolver estes problemas. Este trabalho está focado em resolver exclusivamente o Cutting Stock Problem com e sem rotação de peças. Portanto, é proposto um tipo de codificação binária com vista a ser aplicada neste tipo de problema e resolvê-lo mediante o uso do algoritmo heurístico Bottom-Left, em conjunto com a metaheurística Simulated Annealing. Finalmente, para comprovar a eficiência da metodologia apresentada, foram utilizados alguns casos de estudo da literatura especializada, com diferentes níveis de complexidade. Para cada caso, são apresentados os resultados obtidos e é realizada uma comparação dos métodos de solução propostos para resolver o Cutting Stock Problem com e sem rotação de peças.

The problems of optimal cutting are considered as classic within the operational research, given their large area of application in industry and their high computational and mathematic complexity. One of the most well-known of this kind of problem is called the Cutting Stock Problem, which allows to divide a plate in several pieces of various sizes, in order to obtain the configuration that maximizes the area of the plate being used. Given the level of difficulty and the large number of applications of this problem in several areas, there is interest in creating new efficient procedures for solving this kind of problem. In this dissertation, it is presented the state of the art of the two-dimensional cutting problems of rectangular pieces on a single plate, in several plates and rollers, considering the possibility of rotating the pieces at an angle of 90 in which the cuts are restricted to non-guillotined type. Furthermore, the mathematical approaches applied by different researchers dedicated to solving these problems are described. This work is focused exclusively on solving the Cutting Stock Problem with and without rotating pieces. Therefore, a kind of binary encoding in order to be applied to this kind of problem and to solving it through the use of the Bottom-Left heuristic algorithm in conjunction with Simulated Annealing are proposed. Finally, to prove the efficiency of the presented methodology, some study cases from the specialized literature were used, with different levels of complexity. For each case, the results are presented and a comparison of the proposed solution methods for solving the Cutting Stock Problem with and without rotating pieces is performed.