Algoritmos de aproximação para problemas de empacotamento em faixa com restrições de descarregamento / Approximation algorithms for the strip packing problem with unloading constraints

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

25/03/2011

RESUMO

Neste trabalho estudamos problemas de empacotamento com restrições de descarregamento considerados NP-difíceis. Estes problemas possuem aplicações nas áreas de logística e roteamento. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes para resolver tais problemas. Uma das abordagens consideradas para tratar tais problemas é a de algoritmos de aproximação, que são algoritmos eficientes (complexidade de tempo polinomial) e que geram soluções com garantia de qualidade. Estudamos técnicas para o desenvolvimento de algoritmos aproximados e também alguns algoritmos para problemas de empacotamento online que podem ser utilizados na resolução do problema estudado. Propomos também algumas heurísticas para o problema e, além disto, provamos que duas destas heurísticas possuem garantias de aproximação com fatores constantes. Realizamos testes computacionais com estes algoritmos propostos. Dentre estes, a heurística GRASP foi a que obteve melhores resultados para as instâncias de teste consideradas.

ASSUNTO(S)

algoritmos problema de empacotamento algorithms packing problem

ACESSO AO ARTIGO

Documentos Relacionados