Geração de padrões de cortes bidimensionais guilhotinados restritos via programação dinâmica e busca em grafo-e/ou
Generation of constrained two-dimensional guillotine cutting patterns via dynamic programming and and/or-graph search
Morabito, Reinaldo; Pureza, Vitoria
http://dx.doi.org/10.1590/S0103-65132007000100003
Prod, vol.17, n1, p.33-51, 2007
Resumo
Um método heurístico para geração de padrões de cortes bidimensionais guilhotinados restritos, baseado no método exato de Christofides e Hadjiconstantinou (1995) foi proposto em Silveira e Morabito (2002). O método combina uma relaxação do espaço de estados de uma formulação de programação dinâmica, um procedimento do tipo otimização do subgradiente e uma heurística de factibilização. Neste trabalho, o método de Silveira e Morabito é modificado com a utilização de uma heurística de factibilização mais efetiva que a anterior, e com uma abordagem de busca em grafo-e/ou para geração de boas soluções iniciais. Resultados computacionais de exemplos da literatura e gerados aleatoriamente indicam que o método refinado tem desempenho bem superior ao anterior, e é competitivo diante de outros métodos propostos na literatura.
Palavras-chave
Problemas de corte, padrões de cortes bidimensionais guilhotinados restritos, programação dinâmica, heurísticas
Abstract
A heuristic method for generating constrained two-dimensional guillotine cutting patterns based on the exact method by Christofides and Hadjiconstantinou (1995) was presented in Silveira and Morabito (2002). The method combines a state space relaxation of a dynamic programming formulation, a subgradient optimization procedure and an inner heuristic that turn infeasible solutions provided in each step of the optimization procedure into feasible solutions. In this work, the method of Silveira and Morabito is modified by using a more effective inner heuristic, and an and/or-graph search approach in order to generate good initial solutions. Results for benchmark and randomly generated instances indicate that the refined method's performance is superior to the previous one, and it is competitive face to other methods proposed in the literature.
Keywords
Cutting problems, constrained two-dimensional guillotine cutting patterns, dynamic programming, heuristics
References
ALVAREZ-VALDÉS , R.; PARAJÓN, A.; TAMARIT, J. A Tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Computers and Operations Research, 29, p. 925-947, 2002.
ARENALES, M.; MORABITO, R.; YANASSE, H. Cutting and packing problems. Pesquisa Operacional, 19(2), 107-299, 1999.
BEASLEY, J. E. Algorithms for unconstrained two-dimensional guilhotine cutting. Journal of the Operational Research Society, 36(4), 297-306, 1985.
BISCHOFF, E.; WAESCHER, G. Cutting and packing. European Journal of Operational Research, n. 84, v. 3, 1995.
CHRISTOFIDES, N.; Hadjiconstantinou, E. (1995). An Exact Algorithm for Orthogonal 2-D Cutting Problems Using Guillotine Cuts. European Journal of Operational Research 83, 21-38.
CHRISTOFIDES, N.; WHITLOCK, C. An algorithm for two-dimensional cutting problems. Operations Research, v. 25, n. 1, p. 30-44, 1977.
CUNG, V., HIFI. M.; LE CUN, B. Constrained two-dimensional guillotine cutting stock problems: A best-first branch-and-bound algorithm. International Transactions in Operational Research, v. 7, p. 185-201, 2000.
DAZA, V. P., ALVARENGA, A. G.; DIEGO, J. Exact solutions for constrained two-dimensional cutting problems. European Journal of Operational Research, v. 84, p. 633-644, 1995.
DOWSLAND, K.; DOWSLAND, W. Packing problems. European Journal of Operational Research, v. 56, p. 2-14, 1992.
DYCKHOFF, H.; FINKE, U. Cutting and Packing in Production and Distribution: Typology and Bibliography. Heidelberg: Springler-Verlag, 1992.
DYCKHOFF, H.; SCHEITHAUER, G.; TERNO, J. (1997). Cutting and Packing. In: Amico, M.; Maffioli, F.; Martello, S. (Ed.) Annoted Bibliographies in Combinatorial Optimization. New York: John Wiley & Sons, p. 393-414, 1997.
DYCKHOFF, H.; WAESCHER, G. Cutting and packing. European Journal of Operational Research, v. 44, n. 2, 1990.
FAYARD, D.; HIFI, M.; ZISSIMOPOULOS, V. An efficient approach for large-scale two-dimensional guillotine cutting stock problems. Journal of the Operational Research Society, v. 49, p. 1270-1277, 1998.
HIFI, M. An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional cutting stock. Computers and Operations Research, v. 24, n. 8, p. 727-736, 1997.
HIFI, M. Special issue: Cutting and packing problems. Studia Informatica Universalis, v. 2, n. 1, p. 1-161, 2002.
LODI, A.; MARTELLO, S.; MONACI, M. Two-dimensional packing problems: a survey. European Journal of Operational Research, v. 141, p. 241-252, 2002.
LUCENA, A. Relax and Cut Algorithms (submetido para publicação), 2004.
MARTELLO, S. Special issue: Knapsack, packing and cutting, Part I: One dimensional knapsack problems. INFOR, v. 32, n. 3, 1994a.
MARTELLO, S. Special issue: Knapsack, packing and cutting, Part II: Multidimensional knapsack and cutting stock problems. INFOR, v. 32, n. 4, 1994b.
MORABITO, R.; ARENALES, M. Um exame dos problemas de corte e empacotamento. Pesquisa Operacional, v. 12, n. 1, p. 1-20, 1992.
MORABITO, R.; ARENALES, M. Staged and constrained two-dimensional guilhotine cutting problems: An AND/OR-graph approach. European Journal of Operational Research, v. 94, p. 548-560, 1996.
MORNAR, V.; KHOSHNEVIS, B. A cutting stock procedure for printed circuit board production. Computers and Industrial Engineering, v. 32, n. 1, p. 57-66, 1997.
MUKHACHEVA, E. A. Decision Making under Conditions of Uncertainty: Cutting _packing Problems. The International Scientific Collection, Ufa, Russia, 1997.
OLIVEIRA, J. F.; FERREIRA, J. S. An improved version of Wang's algorithm for two-dimensional cutting problems. European Journal of Operational Research, v. 44, p. 256-266, 1990.
OLIVEIRA, J. F.; WAESCHER, G. Special Issue on Cutting and Packing. European Journal of Operational Research (a aparecer), 2006.
PARADA, V.; SEPULVEDA, M.; SOLAR, M.; GOMES, A. Solution for the constrained guillotine cutting problem by simulated annealing. Computers and Operations Research, v. 25, n. 1, p. 37-47, 1998.
SICUP Special Interest Group on Cutting and Packing. Available in:
SILVEIRA, R.; MORABITO, R. Um método heurístico baseado em programação dinâmica para o problema de corte bidimensional guilhotinado restrito. Gestão & Produção, v. 9, n. 1, p. 78-92, 2002.
SWEENEY, P.; PATERNOSTER, E. Cutting and packing problems: a categorized, application-oriented research bibliography. Journal of the Operational Research Society, v. 43, p. 691-706, 1992.
VASKO, F. J. A computational improvement to Wang's two-dimensional cutting stock algorithm. Computers and Industrial Engineering, v. 16, n. 1, p. 109-115, 1989.
VIANNA, A. Extensões da abordagem em grafo-e/ou para problemas de corte e empacotamento, Tese de doutorado, ICMSC-USP, São Carlos, 2000.
VISWANATHAN, K. V.; BAGCHI, A. Best-first search methods for constrained two-dimensional cutting stock problems. Operations Research, v. 41, n. 4, p. 768-776, 1993.
WANG, P. Y. Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems. Operations Research, v. 31, p. 573-586, 1983.
WANG, P.Y.; WAESCHER, G. Cutting and packing. European Journal of Operational Research, v. 141, n. 2, p. 239-469, 2002.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email