Orientadores: Flávio Keidi Miyazawa, Rafael Crivellari Saliba Schouery, Eduardo CandidoDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: 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 minutosAbstract: 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 minutesMestradoCiência da ComputaçãoMestre em Ciência da Computação2014/25892-41406898, 1364128FAPESPCAPES