Algoritmos para problemas de empacotamento / Algorithms for packing problems

AUTOR(ES)

Eduardo Candido Xavier

DATA DE PUBLICAÇÃO

2006

RESUMO

In this work we study several packing problems that are NP-hard. If we consider that P ? NP, we know that there are no efficient (polynomial time complexity) exact algorithms to solve these problems. One way to deal with these kind of problems is to use approximation algorithms, that are efficient algorithms that produce solutions with quality guarantee. We present several approximation algorithms for some packing problems that have practical applications. Another way to deal with NP-hard problems is to develop heuristics. We also consider column generation based heuristics for packing problems. In this case, we present column generation algorithms for some two dimensional packing problems and also present computational tests with the proposed algorithms. The computational results shows that the heuristics are efficient and produce solutions of very good quality

ASSUNTO(S)

algorithms combinatorial optimization algoritmos otimização combinatoria heuristica heuristics

Documentos Relacionados

• Algoritmos para problemas de corte e empacotamento
• Algoritmos de aproximação para problemas de empacotamento em faixa com restrições de descarregamento
• Algoritmos para problemas de grafos com incertezas
• Algoritmos para problemas de escalonamento em grades
• Algoritmos para resolução do problema de empacotamento de conjuntos utilizando poliedros quase inteiros