Defesa de Dissertação de Mestrado: André Willik Valenti
Document Actions
Defesa de Dissertação de Mestrado: Jefferson Luiz Moisés da Silveira
Algoritmos de Aproximação para Problemas de Empacotamento em Faixa com Restrições de Descarregamento.
| What | Defesa de Mestrado |
|---|---|
| When |
25/03/2011 from 16:00 to 18:00 |
| Where | Sala 322 - IC 3 |
| Add event to calendar |
vCal
iCal
|
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 != N P , 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 efcientes (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 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.
Concurso Público para Professor Doutor - MS-3
