Made available in DSpace on 2016-06-02T19:51:37Z (GMT). No. of bitstreams: 1 2228.pdf: 979050 bytes, checksum: ffa6f96c8eada124b6f1e6ba3ebe02da (MD5) Previous issue date: 2008-12-11 / Financiadora de Estudos e Projetos / 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 ). / Os problemas de corte e empacotamento são importantes no planejamento da produção de vários segmentos industriais envolvendo objetivos como, por exemplo, minimizar os efeitos negativos gerados por desperdício de materiais ou espaços ociosos. As perdas de material, devido a uma programação pouco adequada dos padrões de corte ou empacotamento, podem ser substanciais, sendo que, em geral, parte destas perdas pode ser evitada apenas com uma programação da produção mais eficiente, não implicando em investimentos adicionais nos processos de produção. O objetivo deste estudo é verificar o desempenho do método de decomposição de Benders aplicado a modelos de carregamento de paletes do produtor e do distribuidor. O problema de carregamento de paletes do produtor envolve empacotar caixas iguais sobre um palete, de maneira a otimizar o aproveitamento deste. O problema de carregamento de paletes do distribuidor envolve empacotar caixas de tamanhos diferentes sobre um palete, também de maneira a otimizar o aproveitamento deste. A abordagem baseada na reformulação de Benders define um algoritmo de relaxação que particiona o problema original em dois outros problemas mais simples de serem resolvidos. Para verificar a eficiência da abordagem, realizaram-se testes computacionais, comparando os resultados obtidos com os obtidos pelo pacote computacional composto de uma linguagem de modelagem (GAMS) e um software de otimização de última geração (CPLEX).