logo_uerj.gif (2426 bytes)

UERJ/IME/CCCOMP
Tese de Mestrado: Meta-Heurísticas Para o Problema de Empacotamento                                 2D e 3D(pdf)
Autor: Anderson Zudio de Moraes
Orientadores: Igor Machado Coelho
                         Paulo Eustáquio Duarte Pinto


Resumo:

O problema de empacotamento consiste em empacotar, ortogonalmente e sem sobreposição, um conjunto de itens na menor quantidade de caixas possível. As versões bi e tridimensional do problema generalizam o caso bem conhecido unidimensional, um dos primeiros problemas da classe NP-Difícil. Esta dissertação estuda a versão clássica dos problemas de empacotamento bidimensional e tridimensional, considerando os casos com itens de orientação fixa e com rotação. O problema tem várias aplicações industriais, e o caso de orientação fixa se relaciona a outros problemas complexos como os de corte, repartição e agendamento. Várias heurísticas são propostas e combinadas com meta-heurísticas para resolver instâncias de grande porte do problema com soluções de boa qualidade. Extensivos testes computacionais são realizados com 820 instâncias padrões utilizadas em vários trabalhos na literatura. Os resultados computacionais obtidos pela melhor abordagem deste trabalho, denominada BRKGA-VCD, demonstram que o método proposto obtém soluções de qualidade superior ou equivalente aos algoritmos estado da arte encontrados na literatura, melhorando o melhor resultado conhecido para este conjunto de instâncias.

Programas de apoio:

Última atualização: 31/07/2013


home
Home

topo
Topo