Relax-and-Fix Aplicado ao Problema de Corte de Estoque com Data de Entrega

Abstract

O Problema de Corte de Estoque (PCE) consiste em cortar um conjunto de objetos disponíveis em estoque para produzir um conjunto de itens em quantidades e comprimentos especificados, otimizando, em geral, um objetivo relacionado com as perdas de materiais, como a minimização do número de objetos cortados. O presente artigo propõe uma extensão deste problema, que acrescenta, aos pedidos, uma data de entrega. A abordagem mais utilizada na literatura para a resolução do PCE é o método simplex com geração de colunas proposto por Gilmore e Gomory [5], [6]. Devido à complexidade computacional para resolução de problemas de grande dimensão usando esta abordagem, neste trabalho é proposta uma heurística Relax-and-Fix para sua resolução. Resultados computacionais mostram que a fase de geração de colunas gera bons padrões de corte que podem ser usados na fase da solução inteira e que a heurística Relax-and-Fix gera soluções com a mesma qualidade das soluções obtidas pelo CPLEX, em um menor tempo computacional médio.