Proposal for a heuristic approach for generation of two-dimensional irregular cutting layout

O problema abordado neste trabalho consiste em fornecer um leiaute formado pelo posicionamento de um conjunto de itens sobre a área de um objeto receptor, de modo que todos os itens fiquem completamente posicionados no interior da superfície do recipiente, e que não haja sobreposição entre os itens. É tratado o contexto mais específico em que apenas duas dimensões são consideradas dos objetos relacionados, e o recipiente é retangular, supostamente limitado apenas por sua largura. Neste trabalho, é feita a proposta de uma nova abordagem construtiva para fornecer soluções para o problema de corte e empacotamento, formada pela combinação de elementos de outras técnicas de resolução do mesmo problema. O novo método inclui heurísticas para ordenação da sequência de itens a posicionar, regras de determinação da posição que cada item deve ocupar, e uma técnica de compactação de leiaute baseada em programação linear. Este trabalho contém a descrição detalhada desta abordagem, bem como os experimentos realizados e os resultados obtidos. Os melhores resultados estão comparados a outros métodos construtivos encontrados na literatura, superando-os para 11 das 14 instâncias avaliadas. A contribuição desta pesquisa está na introdução de um novo método para a resolução de problemas de corte e empacotamento, possibilitando a realização de outros trabalhos que explorem a adaptação da abordagem proposta para sua aplicação em procedimentos de busca para obter melhores soluções.The problem addressed in this dissertation consists in providing a layout formed by positi- oning a set of items on the area of a large container object, so that all items are completely positioned in the interior surface of the container, and that there is no overlap between the items. We dealt with a more specific context in which only two dimensions are conside- red for the related objects, and the container is rectangular, supposedly limited only by its width. In this work, we propose a new constructive approach to provide solutions to the cutting and packing problem, formed by combining elements of other techniques for the same problem. The new method includes heuristics for ordering the sequence of items being placed, rules for determining the position that each item should occupy, and a layout compaction technique based on linear programming. We present a detailed description of this approach, as well as some experiments and results. The best results obtained are compared to other construction methods found in literature, overcoming them in 11 out of 14 instances. The contribution of this research is an introduction of a new method for solving cutting and packing problems, enabling the conduction of other works that can explore and adapt the proposed approach for application procedures aiming for better solutions