Algoritmos para Problemas de Empacotamento
Resumo
Estudamos diversos problemas de empacotamento considerados NP-difíceis. Assumimos a hipótese de que P ≠ NP e deste modo não existem algoritmos eficientes (complexidade de tempo polinomial) exatos para resolver tais problemas. Desta forma, apresentamos algoritmos aproximados (algoritmos eficientes e que geram soluções com garantia de qualidade) para problemas de empacotamento com aplicações práticas. Alguns dos fatores de aproximação apresentados são os melhores conhecidos para os problemas correspondentes. Também apresentamos heurísticas baseadas em programação linear usando a técnica de geração de colunas para problemas de empacotamento bidimensional. Os resultados computacionais sugerem que tais heurísticas obtêm soluções de muito boa qualidade para instâncias reais.
Referências
Cintra, G. F. (2004). Algoritmos para problemas de corte de guilhotina bidimensional. PhD thesis, Instituto de Matemática e Estatística, São Paulo.
Cintra, G. F., Miyazawa, F. K., Wakabayashi, Y., and Xavier, E. C. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, accepted.
Cintra, G. F., Miyazawa, F. K., Wakabayashi, Y., and Xavier, E. C. A note on the approximability of cutting stock problems. European Journal of Operational Research, to appear, DOI: 10.1016/j.ejor.2005.09.053.
Cintra, G. F. and Wakabayashi, Y. (2004). Dynamic programming and column generation based approaches for two-dimensional guillotine cutting problems. In Proceedings of WEA 2004: Workshop on Efficient and Experimental Algorithms, volume 3059 of Lecture Notes in Computer Science, pages 175–190.
Dawande, M., Kalagnanam, J., and Sethuranam, J. (1998). Variable sized bin packing with color constraints. Technical report, IBM, T.J. Watson Research Center, NY.
Dawande, M., Kalagnanam, J., and Sethuranam, J. (2001). Variable sized bin packing with color constraints. In Proceedings of the 1th Brazilian Symposium on Graph Algorithms and Combinatorics, volume 7 of Electronic Notes in Discrete Mathematics.
Ferreira, J. S., Neves, M. A., and Fonseca e Castro, P. (1990). A two-phase roll cutting problem. European J. Operational Research, 44:185–196.
Golubchik, L., Khanna, S., Khuller, S., Thurimella, R., and Zhu, A. (2000). Approximation algorithms for data placement on parallel disks. In Proceedings of SODA, pages 223–232.
Hochbaum, D. S. and Shmoys, D. B. (1987). Using dual approximation algorithms for schedulling problems: practical and theoretical results. Journal of the ACM, 34(1):144–162.
Hoto, R., Arenales, M., and Maculan, N. The one dimensional compartmentalized cutting stock problem: a case study. To appear in European Journal of Operational Research.
Kashyap, S. R. and Khuller, S. (2003). Algorithms for non-uniform size data placement on parallel disks. In Proceedings of FSTTCS, volume 2914 of Lecture Notes in Computer Science, pages 265–276.
Marques, F. P. and Arenales, M. The constrained compartmentalized knapsack problem. To appear in Computer & Operations Research.
Shachnai, H. and Tamir, T. (2001a). On two class-constrained versions of the multiple knapsack problem. Algorithmica, 29:442–467.
Shachnai, H. and Tamir, T. (2001b). Polynomial time approximation schemes for class-constrained packing problems. Journal of Scheduling, 4(6):313–338.
Shachnai, H. and Tamir, T. (2004). Tight bounds for online class-constrained packing. Theoretical Computer Science, 321(1):103–123.
Xavier, E. C. (2006). Algoritmos para Problemas de Empacotamento. PhD thesis, Universidade Estadual de Campinas. [link].
Xavier, E. C. and Miyazawa, F. K. A one-dimensional bin packing problem with shelf divisions. To appear in Discrete Applied Mathematics (Elsevier).
Xavier, E. C. and Miyazawa, F. K. (2005). A one-dimensional bin packing problem with shelf divisions. In 2nd Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2005), volume 19 of Electronic Notes in Discrete Mathematics.
Xavier, E. C. and Miyazawa, F. K. (2006a). Approximation schemes for knapsack problems with shelf divisions. Theoretical Computer Sciense, 352(1-3):71–84.
Xavier, E. C. and Miyazawa, F. K. (2006b). The class constrained bin packing problem with applications to video-on-demand. In Proceedings of the 12th Annual International Computing and Combinatorics Conference (COCOON’06), volume 4112 of Lecture Notes in Computer Science, pages 439–448.
Cintra, G. F., Miyazawa, F. K., Wakabayashi, Y., and Xavier, E. C. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, accepted.
Cintra, G. F., Miyazawa, F. K., Wakabayashi, Y., and Xavier, E. C. A note on the approximability of cutting stock problems. European Journal of Operational Research, to appear, DOI: 10.1016/j.ejor.2005.09.053.
Cintra, G. F. and Wakabayashi, Y. (2004). Dynamic programming and column generation based approaches for two-dimensional guillotine cutting problems. In Proceedings of WEA 2004: Workshop on Efficient and Experimental Algorithms, volume 3059 of Lecture Notes in Computer Science, pages 175–190.
Dawande, M., Kalagnanam, J., and Sethuranam, J. (1998). Variable sized bin packing with color constraints. Technical report, IBM, T.J. Watson Research Center, NY.
Dawande, M., Kalagnanam, J., and Sethuranam, J. (2001). Variable sized bin packing with color constraints. In Proceedings of the 1th Brazilian Symposium on Graph Algorithms and Combinatorics, volume 7 of Electronic Notes in Discrete Mathematics.
Ferreira, J. S., Neves, M. A., and Fonseca e Castro, P. (1990). A two-phase roll cutting problem. European J. Operational Research, 44:185–196.
Golubchik, L., Khanna, S., Khuller, S., Thurimella, R., and Zhu, A. (2000). Approximation algorithms for data placement on parallel disks. In Proceedings of SODA, pages 223–232.
Hochbaum, D. S. and Shmoys, D. B. (1987). Using dual approximation algorithms for schedulling problems: practical and theoretical results. Journal of the ACM, 34(1):144–162.
Hoto, R., Arenales, M., and Maculan, N. The one dimensional compartmentalized cutting stock problem: a case study. To appear in European Journal of Operational Research.
Kashyap, S. R. and Khuller, S. (2003). Algorithms for non-uniform size data placement on parallel disks. In Proceedings of FSTTCS, volume 2914 of Lecture Notes in Computer Science, pages 265–276.
Marques, F. P. and Arenales, M. The constrained compartmentalized knapsack problem. To appear in Computer & Operations Research.
Shachnai, H. and Tamir, T. (2001a). On two class-constrained versions of the multiple knapsack problem. Algorithmica, 29:442–467.
Shachnai, H. and Tamir, T. (2001b). Polynomial time approximation schemes for class-constrained packing problems. Journal of Scheduling, 4(6):313–338.
Shachnai, H. and Tamir, T. (2004). Tight bounds for online class-constrained packing. Theoretical Computer Science, 321(1):103–123.
Xavier, E. C. (2006). Algoritmos para Problemas de Empacotamento. PhD thesis, Universidade Estadual de Campinas. [link].
Xavier, E. C. and Miyazawa, F. K. A one-dimensional bin packing problem with shelf divisions. To appear in Discrete Applied Mathematics (Elsevier).
Xavier, E. C. and Miyazawa, F. K. (2005). A one-dimensional bin packing problem with shelf divisions. In 2nd Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2005), volume 19 of Electronic Notes in Discrete Mathematics.
Xavier, E. C. and Miyazawa, F. K. (2006a). Approximation schemes for knapsack problems with shelf divisions. Theoretical Computer Sciense, 352(1-3):71–84.
Xavier, E. C. and Miyazawa, F. K. (2006b). The class constrained bin packing problem with applications to video-on-demand. In Proceedings of the 12th Annual International Computing and Combinatorics Conference (COCOON’06), volume 4112 of Lecture Notes in Computer Science, pages 439–448.
Publicado
30/06/2007
Como Citar
XAVIER, E. C.; MIYAZAWA, F. K..
Algoritmos para Problemas de Empacotamento. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 20. , 2007, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 1966-1973.
ISSN 2763-8820.
