Texto completo
| |
| Autor(es): |
Yulle Glebbyo Felipe Borges
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2016-09-12 |
| Membros da banca: |
Flávio Keidi Miyazawa;
Kelly Cristina Poldi;
Fábio Luiz Usberti
|
| Orientador: | Rafael Crivellari Saliba Schouery; Flávio Keidi Miyazawa; Eduardo Candido Xavier |
| Resumo | |
No problema de Empacotamento em Recipientes com Restrições de Classe (CCBPP, do inglês Class Constrained Bin Packing Problem), um conjunto de itens de variados tama- nhos e classes deve ser empacotado no menor número de recipientes possível, cada um com uma capacidade e com um limite na quantidade de classes diferentes que podem ser acomodadas. Este problema possui aplicações em diversas áreas, como na manufatura de embalagens, na indústria têxtil e em aplicações multimídia, por exemplo. Nesta dissertação, apresentamos uma família de algoritmos exatos baseados em Branch- and-Price para o CCBPP, assim como algoritmos exatos para algumas variações do Pro- blema da Mochila Com Restrições de Classe (CCKP, do inglês Class Constrained Knap- sack Problem), que aparecem como subproblema na resolução do CCBPP através do método Branch-and-Price. Como, ao nosso conhecimento, não existem abordagens para soluções exatas para o CCBPP na literatura, propomos adaptações de instâncias popu- lares para o Problema de Empacotamento em Recipientes (BPP, do inglês Bin Packing Problem) para que possamos validar nossos algoritmos a partir de experimentos empíricos. Nosso melhor algoritmo encontrou soluções ótimas para 92% das instâncias propostas em até 30 segundos, e para 98% das instâncias dentro de um tempo limite imposto de 15 minutos (AU) | |
| Processo FAPESP: | 14/25892-4 - Problemas de corte de estoque com restrições de classe |
| Beneficiário: | Yulle Glebbyo Felipe Borges |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |