Algoritmos Branch-and-Price para o Problema de Empacotamento em Recipientes com Restrições de Classe

  • Yulle Glebbyo UNICAMP
  • Flávio K. Miyazawa UNICAMP
  • Rafael C. S. Schouery UNICAMP
  • Eduardo C. Xavier UNICAMP

Resumo


No problema de Empacotamento em Recipientes Com Restrições de Classe, um conjunto de itens de variados tamanhos e classes deve ser empacotado em recipientes, cada um com capacidade B e limite C na quantidade de classes diferentes acomodadas, minimizando o número de recipientes usados. Apresentamos algoritmos de Branch-and-Price para este problema, assim como algoritmos para o Problema da Mochila Com Restrições de Classe, que aparece como subproblema de pricing. Nos experimentos executados, o melhor algoritmo proposto resolveu 93% das instâncias em menos de 30 segundos.


 

Referências

Epstein, L., Imreh, C., and Levin, A. (2010). Class constrained bin packing revisited. Theoretical Computer Science, 411(34):3073–3089.

Gilmore, P. C. and Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6):849–859.

Shachnai, H. and Tamir, T. (2001). Polynomial time approximation schemes for class-constrained packing problems. Journal of Scheduling, 4(6):313–338.

Vance, P. H. (1998). Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational Optimimization and Applications, 9(3):211–228.

Vance, P. H., Barnhart, C., Johnson, E. L., and Nemhauser, G. L. (1994). Solving binary cutting stock problems by column generation and branch-and-bound. Computational Optimization and Applications, 3(2):111–130.

Xavier, E. C. and Miyazawa, F. K. (2008). The class constrained bin packing problem with applications to video-on-demand. Theoretical Computer Science, 393(1):240–259.
Publicado
04/07/2016
GLEBBYO, Yulle; MIYAZAWA, Flávio K.; SCHOUERY, Rafael C. S.; XAVIER, Eduardo C.. Algoritmos Branch-and-Price para o Problema de Empacotamento em Recipientes com Restrições de Classe. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2016 . p. 820-823. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2016.9833.