Uma Heurística Baseada em Programação Dinâmica para o Problema de Corte Bidimensional
DOI:
https://doi.org/10.5540/tcam.2022.023.04.00683Keywords:
problema de corte bidimensional restrito, programação dinâmica, heurísticaAbstract
Problemas de corte e empacotamento fazem parte do processo de planejamento da produção em muitas indústrias (e.g. papel, vidro, moveis). Em algumas dessas indústrias, um objeto retangular grande deve ser cortado em itens retangulares menores e existe uma capacidade limitada para o estoque dos itens. Nesse caso, surge o problema de corte bidimensional de alocação de objeto único restrito (2DSLOPP). Alguns autores têm proposto algoritmos de programação dinâmica para resolver o problema no caso irrestrito. Para o caso restrito essa técnica ainda apresenta alguns desafios devido à dimensão do espaço de estados. Nesse artigo propõem-se duas heurísticas baseadas em programação dinâmica e no método de Gilmore e Gomory para resolver o 2DSLOPP restrito considerando restrições especiais associadas ao equipamento de corte. São apresentados resultados do estudo computacional realizado com três conjuntos de instâncias que mostram a eficiência da proposta. Em particular para instâncias similares às encontradas na indústria moveleira foram obtidas soluções com gap máximo médio de 4.4%.References
A. C. Cherri and M. N. Arenales, “O problema de corte de estoque com rea-proveitamento das sobras de material–heurística ffd modificada,” inAnais doXXXVII Simpósio Brasileiro de Pesquisa Operacional, Gramado, pp. 1700–1711, 2005.
G. Wäscher, H. Haußner, and H. Schumann, “An improved typology of cuttingand packing problems,”European journal of operational research, vol. 183,no. 3, pp. 1109–1130, 2007.
N. Christofides and C. Whitlock, “An algorithm for two-dimensional cuttingproblems,”Operations Research, vol. 25, no. 1, pp. 30–44, 1977.
P. C. Gilmore and R. E. Gomory, “Multistage cutting stock problems of twoand more dimensions,”Operations research, vol. 13, no. 1, pp. 94–120, 1965.
P. C. Gilmore and R. E. Gomory, “The theory and computation of knapsackfunctions,”Operations Research, vol. 14, no. 6, pp. 1045–1074, 1966.
J. C. Herz, “Recursive computational procedure for two-dimensional stock cut-ting,”IBM Journal of Research and Development, vol. 16, no. 5, pp. 462–469,1972.
P. Y. Wang, “Two algorithms for constrained two-dimensional cutting stockproblems,”Operations Research, vol. 31, no. 3, pp. 573–586, 1983.18.
F. J. Vasko, “A computational improvement to wang’s two-dimensional cuttingstock algorithm,”Computers Industrial Engineering, vol. 16, no. 1, pp. 109–115, 1989.
J. F. Oliveira and J. S. Ferreira, “An improved version of wang’s algorithm fortwo-dimensional cutting problems,”European Journal of Operational Research,vol. 44, no. 2, pp. 256–266, 1990.
M. Russo, M. Boccia, A. Sforza, and C. Sterle, “Constrained two-dimensionalguillotine cutting problem: upper-bound review and categorization,”Interna-tional Transactions in Operational Research, vol. 27, no. 2, pp. 794–834, 2020.
A. S. Velasco and E. Uchoa, “Improved state space relaxation for constrainedtwo-dimensional guillotine cutting problems,”European Journal of OperationalResearch, vol. 272, no. 1, pp. 106–120, 2019.
R. J. Silveira and R. Morabito, “Um método heurístico baseado em programa-ção dinâmica para o problema de corte bidimensional guilhotinado restrito,”Gestão Produção, vol. 9, pp. 78–92, 2002.
N. Christofides and E. Hadjiconstantinou, “An exact algorithm for orthogonal2-d cutting problems using guillotine cuts,”European Journal of OperationalResearch, vol. 83, no. 1, pp. 21–38, 1995.
D. Fayard, M. Hifi, and V. Zissimopoulos, “An efficient approach for large-scaletwo-dimensional guillotine cutting stock problems,”Journal of the OperationalResearch Society, vol. 49, no. 12, pp. 1270–1277, 1998.
M. Martin, E. Birgin, R. Lobato, R. Morabito, and P. Munari, “Models forthe two-dimensional rectangular single large placement problem with guillo-tine cuts and constrained pattern,”International Transactions in OperationalResearch, vol. 27, pp. 767–793, 2019.
S. Rangel, “O problema do corte bidimensional,” Master’s thesis, UniversidadeEstadual de Campinas, 1990.
C. Perin and S. Rangel, “O problema do corte bidimensional,” inAnais doCongresso Nacional de Matemática Aplicada e Computacional, (São José doRio Preto - SP), pp. 131–134, 1989.
G. Scheithauer,Introduction to Cutting and Packing Optimization: Problems,Modeling Approaches, Solution Methods, vol. 263. Springer, 2017.
M. Arenales, R. Morabito, V. Armentano, and H. Yanasse,Pesquisa operacio-nal: para cursos de engenharia. Elsevier Brasil, 2015.
R. Andonov, V. Poirriez, and S. Rajopadhye, “Unbounded knapsack problem:Dynamic programming revisited,”European Journal of Operational Research,vol. 123, no. 2, pp. 394–407, 2000.19.
E. Horowitz and S. Sahni, “Computing partitions with applications to the knap-sack problem,”J. ACM, vol. 21, no. 2, p. 277–292, 1974.
A. Lodi and M. Monaci, “Integer linear programming models for 2-staged two-dimensional knapsack problems,”Mathematical Programming, vol. 94, no. 2,pp. 257–278, 2003.
L. L. S. Costa, “Um estudo sobre o problema de corte de estoque bidimensional2-estágios,” Master’s thesis, IMECC - UNICAMP, Campinas - SP, 2016.
N. S. Assis, “O problema de corte de estoque bidimensional: geração de padrõesde corte 2-estágios restritos,” Master’s thesis, Universidade Estadual Paulista,2019.
M. Martin, R. Morabito, and P. Munari, “A bottom-up packing approachfor modeling the constrained two-dimensional guillotine placement problem,”Computers Operations Research, vol. 115, p. 104851, 2020.
P. B. Castellucci, “Julia e jump: Novas ferramentas para programação matemá-tica,”Pesquisa Operacional para o Desenvolvimento, vol. 9, no. 2, pp. 48–61,2017.
ILOG,CPLEX Reference Manual. url:https://www.ibm.com/br-pt/products/ilog-cplex-optimization-studio. Acesso em: 22 de julho de2021. IBM, 12.1 ed., 2009.
OR-Library,“Copyright (c) (2010) (j e beasley).” url:http://people.brunel.ac.uk/ mastjjb/jeb/info.html. Acesso em: 4 de no-vembro de 2019, 1990.
E. Silva, J. F. Oliveira, and G. Wäscher, “2dcpackgen: A problem generator fortwo-dimensional rectangular cutting and packing problems,”European Journalof Operational Research, vol. 237, no. 3, pp. 846–856, 2014.
J. Borges, “Um estudo sobre métodos de solução para o problema de corte deestoque biobjetivo,” Master’s thesis, UNESP, São Jose do Rio Preto - SP, 2021.
M. Mrad, I. Meftahi, and M. Haouari, “A branch-and-price algorithm for thetwo-stage guillotine cutting stock problem,”Journal of the Operational Rese-arch Society, vol. 64, no. 5, pp. 629–637, 2013.
P. A. MUNARI-JUNIOR, “Comparação de softwares científicos utilizando per-fis de desempenho: automatização dos cálculos pela planilha perfis,” 2009.
Downloads
Published
How to Cite
Issue
Section
License
Copyright
Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.
Intellectual Property and Terms of Use
The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.
The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.
