Defesa de Tese de Doutorado: Diego Zuquim Guimarães Garcia
Document Actions
Defesa de Tese de Doutorado: Thiago Alves de Queiroz
Algoritmos para Problemas de Corte e Empacotamento.
| What | Defesa de Doutorado |
|---|---|
| When |
21/12/2010 from 14:00 to 18:00 |
| Where | Auditório do IC - Sala 85 - IC 2 |
| Add event to calendar |
vCal
iCal
|
Problemas de Corte e Empacotamento são, em sua maioria, NP-difíceis e, se for considerado que P ≠ NP, temos que não existem algoritmos exatos de tempo polinomial para tais. Aplicações práticas envolvendo estes problemas incluem a alocação de recursos para computadores; o corte de chapas de ferro, de madeira, de vidro, de alumínio, peças em couro, etc.; a estocagem de objetos; e, o carregamento de objetos dentro de contêineres ou caminhões-baú.
Nesta tese investigamos problemas de Corte e Empacotamento NP-difíceis, nas suas versões bi- e tridimensionais, considerando diversas restrições práticas impostas a tais, a saber: que permitem a rotação ortogonal dos itens da instância; cujos cortes sejam feitos por uma guilhotina; cujos cortes sejam feitos por uma guilhotina respeitando um número máximo de estágios de corte; cujos cortes sejam não-guilhotinados;
cujos itens da instância tenham demanda (não) unitária; cuja instância de entrada considere recipientes de diferentes tamanhos; cujos itens da instância sejam representados por polígonos convexos e não-convexos (formas irregulares); cujo empacotamento respeite critérios de estabilidade para corpos rígidos; cujo empacotamento satisfaça uma dada ordem de descarregamento; e, cujos empacotamentos intermediários e final tenham seu centro de gravidade dentro de uma região considerada “segura”'.
Para estes problemas foram propostos algoritmos baseados em programação dinâmica; modelos de programação inteira; técnicas do tipo branch-and-cut; heurísticas, incluindo as baseadas na técnica de geração de colunas; e, meta-heurísticas como o GRASP. Resultados teóricos também foram obtidos, tal que provamos uma questão em aberto recentemente levantada na literatura sobre cortes não-guilhotinados restritos a um conjunto de pontos.
Uma extensiva série de testes computacionais com os algoritmos desenvolvidos considerando instâncias reais e várias outras geradas de forma aleatória foram realizados. Os resultados computacionais, sendo alguns deles comparados com a literatura, comprovam a validade das algoritmos propostos e a sua aplicabilidade prática para resolver os problemas investigados.
Concurso Público para Professor Doutor - MS-3
