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
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.