Uma Heurística Baseada em Programação Dinâmica para o Problema de Corte Bidimensional

N. S. Assis, S. Rangel

Abstract


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%.

Keywords


problema de corte bidimensional restrito; programação dinâmica; heurística

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.




DOI: https://doi.org/10.5540/tcam.2022.023.04.00683

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia