GERAÇÃO COLUNAS E GRASP REATIVO PARA O PROBLEMA DE CORTE UNIDIMENSIONAL

Este trabalho aborda o Problema de Corte Unidimensional e propõe dois algoritmos, sendo um heurístico e o outro híbrido, para sua resolução. Utilizando os principais elementos do algoritmo híbrido GRASP-1D em sua implementação, o algoritmo GR1d se diferencia com uma abordagem reativa que identifica inicialmente o parâmetro de aleatoriedade α que melhor se adequa a instância corrente. Já o algoritmo híbrido GCH1d caracteriza-se como híbrido porque é inicializado com a técnica Geração de Colunas, onde subproblema é um problema de programação inteira, resolvido de forma exata para retornar o padrão de corte maximal. Se a solução ótima do PL Mestre não é inteira, determina-se a demanda do problema residual que deve ser resolvido pela heurística GR1d. Com o objetivo de avaliar o desempenho destes algoritmos, testes são executados instâncias reais. Ao confrontar os resultados com algoritmos híbridos GRASP-1D, ALG HB1 e ALG HB2, contatou-se um desempenho significativo do algoritmo GCH1d.