Problema de Corte de Estoque Unidimensional com Sobras Aproveitáveis: Solução via Metaheurística GRASP
DOI:
https://doi.org/10.5540/tema.2020.021.03.441Palavras-chave:
Problema de corte de estoque unidimensional, sobras aproveitáveis, metaheurística, GRASP.Resumo
Neste artigo apresentamos um estudo sobre o Problema de Corte de Estoque com Sobras Aproveitáveis (PCESA) unidimensional. O Problema de Corte de Estoque (PCE) consiste em cortar um conjunto de objetos, disponíveis me estoque, para produzir um conjunto de itens em quantidades e tamanhos especificados. O PCESA é um PCE no qual nem todas as sobras de um processo de corte são consideradas perdas, ou seja, quando uma sobra for maior que um determinado comprimento, ela retorna ao estoque para ser usada nos processos de corte subsequentes. O objetivo do problema abordado é a minimização da perda de material e da quantidade de retalhos (sobras) gerados no PCESA unidimensional. O estoque inicial é composto de objetos padronizados e de retalhos resultantes de cortes anteriores. Para resolver este problema, duas heurísticas e três versões da metaheurística Greedy Randomized Adaptive Search Procedure (GRASP) foram desenvolvidas. Testes computacionais foram realizados para os procedimentos propostos em instâncias da literatura. As abordagens propostas para a solução apresentaram boas soluções em relação ao número de sobras geradas.
Referências
A. R. Brown, “Optimum packing and depletion: the computer in space and resource usage problem,” Macdonald and Co., 1971.
M. N. Arenales, A. C. Cherri, D. N. d. Nascimento, and A. Vianna, “A new mathematical model for the cutting stock/leftover problem,” Pesquisa Operacional, vol. 35, no. 3, pp. 509–522, 2015.
A. C. Cherri, M. N. Arenales, and H. H. Yanasse, “The one-dimensional cutting stock problem with usable leftover–a heuristic approach,” European Journal of Operational Research, vol. 196, no. 3, pp. 897–908, 2009.
A. C. Cherri, M. N. Arenales, and H. H. Yanasse, “The usable leftover onedimensional cutting stock problem—a priority-in-use heuristic,” International Transactions in Operational Research, vol. 20, no. 2, pp. 189–199, 2013.
M. Gradišar, J. Jesenko, and G. Resinovic, “Optimization of roll cutting in clothing industry,” Computers & Operations Research, vol. 24, no. 10, pp. 945–953, 1997.
S. Koch, S. König, and G. Wäscher, “Integer linear programming for a cutting problem in the wood-processing industry: a case study,” International Transactions in Operational Research, vol. 16, no. 6, pp. 715–726, 2009.
G. M. Roodman, “Near-optimal solutions to one-dimensional cutting stock problems,” Computers & operations research, vol. 13, no. 6, pp. 713–719, 1986.
A. C. Cherri, M. N. Arenales, H. H. Yanasse, K. C. Poldi, and A. C. G. Vianna, “The one-dimensional cutting stock problem with usable leftovers–a survey,” European Journal of Operational Research, vol. 236, no. 2, pp. 395–402, 2014.
M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness. WH Free. Co., São Francisco, 1979.
M. G. Resende and J. P. de Sousa, Metaheuristics: computer decision-making, vol. 86. Springer Science & Business Media, 2013.
T. A. Feo and M. G. Resende, “Greedy randomized adaptive search procedures,” Journal of global optimization, vol. 6, no. 2, pp. 109–133, 1995.
E. V. Neto, A. S. Velasco, and G. G. de Paula Junior, “Algoritmos grasp
híbridos para o problema de corte unidimensional,” 2013.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Política para Periódicos de Acesso Livre
Autores que publicam nesta revista concordam com os seguintes termos:
- Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
- Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
- Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).
- Esta é uma revista de acesso aberto, o que significa que todo o conteúdo é livremente disponível gratuitamente para o usuário ou sua instituição. Os usuários estão autorizados a ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outro propósito legal, sem pedir permissão prévia do editor ou do autor. Isso está de acordo com a definição de acesso aberto do BOAI.
Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.