Texto completo
| |
| Autor(es): |
Thiago Alves de Queiroz
Número total de Autores: 1
|
| Tipo de documento: | Tese de Doutorado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2010-12-21 |
| Membros da banca: |
Flávio Keidi Miyazawa;
Glauber Ferreira Cintra;
Eduardo Candido Xavier;
Orlando Lee;
Horacio Hideki Yanasse
|
| Orientador: | Flávio Keidi Miyazawa |
| Resumo | |
Problemas de Corte e Empacotamento são, em sua maioria, NP-difíceis e não existem algoritmos exatos de tempo polinomial para tais se for considerado P ¿ NP. 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; 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 tenham demanda (não) unitária; cujos recipientes tenham tamanhos diferentes; cujos itens 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. Provamos uma questão em aberto levantada na literatura sobre cortes não-guilhotinados restritos a um conjunto de pontos. Uma extensiva série de testes computacionais considerando instâncias reais e várias outras geradas de forma aleatória foram realizados com os algoritmos desenvolvidos. Os resultados computacionais, sendo alguns deles comparados com a literatura, comprovam a validade dos algoritmos propostos e a sua aplicabilidade prática para resolver os problemas investigados (AU) | |
| Processo FAPESP: | 09/01129-1 - Roteamento de veículos de carga com restrições de empacotamento |
| Beneficiário: | Thiago Alves de Queiroz |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |