A defesa da Tese "Algoritmos para Problemas de Empacotamento" ocorreu no dia 05/12/2006.

Resumo

Neste trabalho estudamos diversos problemas de empacotamento considerados NP-difíceis.  Assumindo a hipótese de que $P \ne \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.  Neste trabalho apresentamos alguns algoritmos aproximados para problemas de empacotamento com aplicações práticas. Outra maneira de se lidar com problemas NP-difíceis é o desenvolvimento de heurísticas.  Neste trabalho também apresentamos heurísticas baseadas no método de geração de colunas para problemas de corte e empacotamento bidimensional. Resultados computacionais sugerem que tais heurísticas são eficientes e geram soluções de muito boa qualidade.