Resumo: Os problemas de empacotamento irregular são uma classe ampla de problemas de otimização que envolve a determinação do layout de um conjunto de peças menores irregulares sobre um contêiner, chamado de objeto, de tal forma que um layout final pode ser alcançado, por exemplo, ao minimizar o espaço ocioso no objeto. A complexidade combinatória envolvida na determinação do melhor layout é um desafio a ser superado nas metodologias de resolução para esses problemas. Adicionalmente, é preciso lidar com a dificuldade computacional de implementar cada detalhe geométrico para eliminar qualquer sobreposição entre peças e manter completamente cada peça no interior do objeto. Uma grande parte das metodologias de resolução combina sofisticados modelos matemáticos, incluindo a representação precisa da geometria, com técnicas de aprendizado de máquina, heurísticas e meta-heurísticas, além do uso de softwares avançados de resolução. Esta dissertação apresenta um estudo sobre ferramentas computacionais na resolução dos problemas de corte e empacotamento irregular en faixas e apresenta uma nova metodologia de representação do problema baseada na sua geometria, que forneceu suporte para elaborar um novo método de resolução e também pode ser usada na proposição de modelos matemáticos, bem como no desenvolvimento de novas técnicas de solução, para as aplicações práticas da indústria. Mais especificamente, o método de resolução proposto neste trabalho consiste de uma heurística bioinspirada na interação gravitacional de corpos e baseada em formulações de hipóteses de melhoria tal que a sua rotina evolui por meio da validação dessas hipóteses e da incorporação de algumas técnicas da literatura. Resumidamente, um pré-processamento ordena a sequência de posicionamento das peças de acordo com o valor decrescente das áreas, então uma solução inicial é construída posicionando as peças em grupos ou por camadas e, finalmente, esta solução é otimizada com o uso de uma metaheurística de recozimento simulado. O desempenho computacional também foi melhorado ao incluir uma estratégia de escolha dinâmica de orientações permitidas. A heurística de interação gravitacional teve bom desempenho na resolução de instâncias da literatura e a metodologia proposta de representação tem potencial para avanços Ver menos

Abstract: Nesting problems are a broad class of optimization problems that involve determining the layout of a set of smaller irregular pieces within a container, referred to as the object, in such a way that a final layout can be obtained, for example, by minimizing idle space within the object. The combinatorial complexity involved in determining the best layout is a challenge to be overcome in the solution methodologies for these problems. Additionally, it is necessary to deal with the computational difficulty of implementing each geometric detail to eliminate any overlap between pieces and to completely keep each piece within the object. A large part of the solution methodologies combines sophisticated mathematical models, including precise geometry representation, with machine learning techniques, heuristics, and metaheuristics, as well as the use of advanced solution software. This dissertation presents a study on computational tools for solving irregular cutting and packing problems and introduces a new methodology for representing the problem based on its geometry. This methodology provided support for developing a new resolution method and can also be used in the formulation of mathematical models as well as in the development of new solution techniques for practical industrial applications. More specifically, the resolution method proposed in this work consists of a bio-inspired heuristic based on the gravitational interaction of bodies and on the formulation of improvement hypotheses such that its routine evolves through the validation of these hypotheses and the incorporation of some techniques from the literature. In summary, a pre-processing step orders the sequence of piece placements according to decreasing area values, then an initial solution is constructed by placing the pieces in groups or layers, and finally, this solution is optimized using a simulated annealing metaheuristic. Computational performance was also enhanced by including a strategy for the dynamic selection of permitted orientations. The gravitational interaction heuristic performed well in solving instances from the literature, and the proposed representation methodology has potential for further advancements Ver menos