Problemas de empacotamento consistem em colocar, de uma forma econômica, uma coleção de objetos dentro de recipientes. Esses problemas podem diferir em duas linhas conforme o objetivo do problema de otimização em questão. Em uma destas linhas, o objetivo é minimizar o número de recipientes usados para empacotar os objetos. Em outra linha, os objetos devem ser empacotados em apenas um recipiente, sendo que este recipiente tem apenas uma dimensão ilimitada e todas as outras são limitadas. Neste caso, o objetivo é minimizar o `tamanho' do empacotamento com relação à dimensão ilimitada do recipiente.
Nesta tese investigamos as versões em que os objetos e os recipientes são bi- ou tridimensionais, e de `formas ortogonais'. Assim, os objetos são retângulos ou caixas retangulares e os recipientes são faixas, placas, caixas de altura ilimitada ou caixas de dimensões finitas (contêineres). Além disso, todos os empacotamentos devem ser ortogonais. Abordamos os seguintes problemas: o problema de empacotamento em faixa, o problema de empacotamento em placas, o problema de empacotamento tridimensional e o problema de empacotamento em contêineres. Esses problemas são NP-difíceis, não aproximáveis --em termos absolutos-- além de certas constantes. Apresentamos algoritmos de aproximação para esses problemas e estudamos o seu desempenho assintótico. Descrevemos algoritmos on-line e off-line tanto para o caso orientado como para o caso em que rotações ortogonais são permitidas.
Para o problema de empacotamento em faixa, apresentamos um algoritmo com limite de desempenho assintótico não maior que 1,62 e outro, on-line, cujo limite de desempenho assintótico é 1,75. Ambos para o caso onde rotações são permitidas. Para o problema de empacotamento em placas, apresentamos um algoritmo com limite de desempenho assintótico não maior que 2,64 e outro, on-line, com limite de desempenho assintótico não maior que 3,25. Ambos também para o caso onde rotações ortogonais são permitidas. Para o problema de empacotamento tridimensional para o caso orientado, apresentamos um algoritmo com limite de desempenho assintótico não maior que 2,67. Para o caso onde rotações em torno do eixo da altura são permitidas, apresentamos um algoritmo com um limite de desempenho assintótico 2,67 e outro, on-line, com um limite de desempenho assintótico 3,25. Para o problema de empacotamento em contêineres onde rotações são permitidas, apresentamos um algoritmo com um limite de desempenho assintótico 4,89 e para o caso on-line, um algoritmo com limite de desempenho assintótico não maior que 6,25.
Os limites acima ou são novos ou são melhores que os encontrados na literatura. Além disso, apresentamos resultados que relacionam a complexidade dos problemas da versão orientada com a versão em que rotações ortogonais são permitidas. Também apresentamos vários algoritmos de aproximação para casos particulares destes problemas: empacotamento de quadrados, de cubos e de objetos `pequenos'. Para esses casos, os algoritmos que obtivemos têm limites de desempenho melhores que os acima mencionados.
Palavras-chave: problemas de empacotamento, algoritmos de aproximação, limite de desempenho assintótico.
Orientadora de tese: YOSHIKO WAKABAYASHI.
Back to Flávio Keidi Miyazawa's Homepage
This document was generated using the LaTeX2HTML translator Version 96.1-h (September 30, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.