Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/321614
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: Branch-and-price algorithms for the class constrained bin packing problem = Algoritmos branch-and-price para o problema de empacotamento em recipientes com restrições de classe
Title Alternative: Algoritmos branch-and-price para o problema de empacotamento em recipientes com restrições de classe
Author: Borges, Yulle Glebbyo Felipe, 1992-
Advisor: Miyazawa, Flávio Keidi, 1970-
Abstract: 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

Abstract: In the Class Constrained Bin Packing Problem (CCBPP), a set of items of various sizes and classes must be packed into the smallest number of bins possible, each bin with a capacity and with a bound on the amount of different classes that can be packed in it. This problem has applications in many areas, such as packages manufacturing, the textile industry, and in multimedia applications. In this dissertation, we present a family of exact algorithms based on Branch-and-Price for the CCBPP, as well as exact algorithms for a few variations of the Class Constrained Knapsack Problem (CCKP), that appears as a subproblem in the resolution of the CCBPP with Branch-and-Price. Since, to the best of our knowledge, there are no exact solution approaches to the CCBPP in the literature, we propose adaptations of popular instances for the Bin Packing Problem (BPP) so that we can validate our algorithms through empirical experiments. Our best algorithm found an optimal solution for 92% of the proposed instances in up to 30 seconds, and for 98% of the instances in an imposed time limit of 15 minutes
Subject: Otimização combinatória
Problemas de empacotamento
Programação linear
Programação inteira
Language: Inglês
Editor: [s.n.]
Citation: BORGES, Yulle Glebbyo Felipe. Branch-and-price algorithms for the class constrained bin packing problem = Algoritmos branch-and-price para o problema de empacotamento em recipientes com restrições de classe. 2016. 1 recurso online ( 60 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/321614>. Acesso em: 31 ago. 2018.
Date Issue: 2016
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Borges_YulleGlebbyoFelipe_M.pdf950.97 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.