Aplicação do método de decomposição de Benders para o problema de carregamento de paletes

Abstract

Cutting and packing problems are important in the production planning of various industrial segments involving goals such as minimizing the negative efects generated by waste of materials or idle spaces. The loss of material due to an inadequate programming of the cutting or packing patterns, can be substantial, and, in general, parts of these losses can be avoided only with a more eficient production planning, not resulting in additional investments in production processes. This study aimed at evaluating the performance of the Benders decomposition method, applied to the manufacturer and distributor pallet loading models. The manufacturer pallet loading model involves packing equal boxes on a pallet, so as to optimize its use. The distributor pallet loading model involves packing boxes of diferent sizes on a pallet, also a way to optimize its use. The approach based on Benders decomposition, defines a relaxation algorithm that partitions the original problem in two other problems easier to be solved. To check the effectiveness of the approach, computational tests were carried out by comparing the results with those obtained by a computational package composed of a modeling language (GAMS) and a last generation optimization solver (CPLEX ).