Algoritmos Branch-and-Price para o Problema de Empacotamento em Recipientes com Restrições de Classe
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.
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
Como Citar
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.
