Uma proposta de solução via Local Branching do Problema de Corte de Estoque com Data de Entrega e Setup de troca de Padrão de corte

Autores

  • Elisama de Araújo Silva Oliveira
  • Elisangela Martins de Sá
  • Sérgio Ricardo de Souza
  • Elizabeth Fialho Wanner

DOI:

https://doi.org/10.5540/03.2022.009.01.0325

Palavras-chave:

Problema de corte, Data de Entrega, Atraso, Adiantamento, Setup, Local Branching.

Resumo

Este artigo apresenta o Problema de Corte de Estoque com Datas de entregas e Setup de troca de padrão de corte (PCE-DDS). Este problema é uma extensão do clássico Problema de Corte de Estoque (PCE), em que as datas de entrega são incorporadas aos pedidos e os setups de trocas de padrão na máquina de corte são adicionados ao tempo de conclusão do pedido. Apesar do PCE ser extensivamente estudado, não foram encontrados, na literatura, trabalhos que abordem, conjuntamente, a inclusão de datas de entrega e tempos de setup para trocade padrões. Este  artigo propõe uma metodologia para a solução do PCE-DDS. Consideramos uma versão simples do PCE e, como hipótese, que o tempo para cortar qualquer padrão de corte é o mesmo. A metodologia proposta é dividida em três fases: na primeira fase, o problema relaxado é resolvido pelo método simplex com geração de colunas, obtendo uma solução viável fracionada; na segunda fase, a heurística Relax-and-Fix é aplicada às colunas encontradas na fase anterior para se encontrar uma solução inteira; na terceira fase, a matheurística Local Branching é usada para melhorar a solução obtida na segunda fase. Os resultados computacionais são comparados com a solução fornecida pelo solver CPLEX e mostram que a proposta de abordagem de resolução apresenta soluções de melhor  qualidade que as fornecidas pelo solver.

Downloads

Não há dados estatísticos.

Biografia do Autor

Elisama de Araújo Silva Oliveira

MMC/CEFET, Belo Horizonte, MG

 

Elisangela Martins de Sá

MMC/CEFET, Belo Horizonte, MG

 

Sérgio Ricardo de Souza

MMC/CEFET, Belo Horizonte, MG

Elizabeth Fialho Wanner

MMC/CEFET, Belo Horizonte, MG

Referências

Claudio Arbib e Fabrizio Marinelli. “Maximum lateness minimization in one-dimensional bin packing”. Em: Omega 68 (2017), pp. 76–84.

Claudio Arbib e Fabrizio Marinelli. “On cutting stock with due dates”. Em: Omega 46 (2014), pp. 11–20.

Matteo Fischetti e Andrea Lodi. “Local branching”. Em: Mathematical programming 98.1- 3 (2003), pp. 23–47.

T. Gau e G. Wäscher. “CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem”. Em: European Journal of Operational Research 84.3 (1995), pp. 572–579.

Paul C. Gilmore e Ralph E. Gomory. “A linear programming approach to the cutting stock problem – Part II”. Em: Operations research 11.6 (1963), pp. 863–888.

Paul C. Gilmore e Ralph E. Gomory. “A linear programming approach to the cutting-stock problem”. Em: Operations research 9.6 (1961), pp. 849–859.

Harald Reinertsen e Thomas WM Vossen. “The one-dimensional cutting stock problem with due dates”. Em: European Journal of Operational Research 201.3 (2010), pp. 701–711.

Laurence A. Wolsey. Integer Programming. New York, NY, EUA: John Wiley & Sons, 1998

Downloads

Publicado

2022-12-08

Edição

Seção

Trabalhos Completos