A construção de planos de empacotamento retangular bidimensional com uso do Problema da Mochila

Abstract

Este estudo propõe o desenvolvimento de um método heurístico para a produção de planos de empacotamento para o Problema de Empacotamento Retangular. O método é construtivo, dividindo-se em sub-procedimentos, e fazendo uso auxiliar do Problema da Mochila para formar soluções. O empacotamento retangular consiste na alocação de itens retangulares em um retângulo de dimensões superiores fixas, chamado de folha de estoque, onde o plano de empacotamento é uma estrutura de organização dos itens dentro da folha que é alcançada produzindo-se coordenadas de localização para cada item dentro dos limites da folha. O método desenvolvido é inspirado por dois trabalhos da literatura como ponto de partida, mas tendo um caráter mais simplificado para construção da solução, utilizando de forma auxiliar o método exato de mochila 0-1 e sua versão de relaxação, a mochila fracionária. Nos principais resultados alcançados, obteve-se planos de empacotamento com mais de 90% de ocupação das folhas utilizadas em um tempo de resposta mais rápido em comparação com a literatura considerada para diversos casos de teste.

Abstract: This study proposes the development of a heuristic method for producing packing plans for the Rectangular Packing Problem. The method is constructive, divided into sub-procedures, and makes auxiliary use of the Knapsack Problem to form solutions. Rectangular packing consists of allocating rectangular items to a rectangle of fixed higher dimensions, called a stock sheet, where the packing plan is a structure for organizing the items within the sheet, achieved by producing location coordinates for each item within the sheet?s boundaries. The developed method is inspired by two studies in the literature as a starting point, but has a more simplified approach to constructing the solution, using the exact 0-1 knapsack method and its relaxation version, the fractional knapsack, as an auxiliary method. The main results achieved include obtaining packing plans with over 90% occupancy of the used sheets in a faster response time compared to the literature considered for several test cases.