HEURÍSTICA PARA O PROBLEMA DE CORTE UNIDIMENSIONAL COM SOBRAS APROVEITÁVEIS

Os problemas de corte de estoque são problemas de otimização que consistem em produzir um conjunto de itens demandados a partir do corte de objetos disponíveis em estoque, otimizando uma função objetivo. O problema de corte de estoque com sobras aproveitáveis (PCESA) difere do problema clássico de corte de estoque por permitir que sobras sejam geradas durante o processo de corte para atender demandas futuras, não sendo computadas como perdas.
Neste trabalho é proposto um procedimento heurístico visando a obtenção de soluções inteiras para instâncias do PCESA unidimensional a partir do modelo matemático proposto por Arenales et al. (2015). Neste modelo, as sobras são consideradas durante o processo de corte, possuindo comprimentos e quantidades limitadas previamente. O método de geração de colunas de Gilmore e Gomory (1963) foi utilizado para resolver a relaxação linear deste problema e os resultados indicaram forte relação entre quantidade de sobras geradas e redução da perda.
No procedimento heurístico proposto, após a obtenção da solução ótima contínua, os padrões de corte gerados são ordenados de modo não-crescente, de acordo com a frequência na qual devem ser cortados e respeitando as seguintes prioridades dos padrões: perda nula sem gerar sobras, perda nula gerando sobras e perda não nula ordenada de modo não-decrescente.
O procedimento consiste em arredondar o valor da frequência para o inteiro superior ao fracionário obtido e testar a factibilidade certificando-se que excessos de itens não sejam gerados ou sejam utilizados mais objetos do que os disponíveis em estoque. Caso resulte em uma solução infactível, a frequência é reduzida em uma unidade até que os excessos de itens sejam eliminados. Demanda e estoque são atualizados e repete-se o processo de arredondamento para o segundo padrão de corte, e assim por diante, até que o último padrão da lista seja analisado. Ao fim deste processo, uma demanda residual é gerada e o problema residual é resolvido utilizando o procedimento descrito anteriormente até que a demanda residual seja nula e uma solução inteira para o problema inicial seja obtida.
Para avaliar o desempenho do procedimento, testes computacionais foram realizados com instâncias da literatura e mostraram um bom desempenho do método proposto. A implementação foi desenvolvida na linguagem de programação C++ juntamente com o solver CPLEX versão 12.8.