Uma heurística VNS baseada em memória e Path-Relinking para o problema de sequenciamento em uma máquina com data de entrega comum

Este trabalho propõe uma heurística Variable Neighborhood Search (VNS) com estrutura de memória e busca local intensificada pelo método Path-Relinking. Essa estratégia é empregada para a otimização do problema de sequenciamento de tarefas em uma máquina com data de entrega comum. Nesse problema, um conjunto de tarefas, com data de entrega comum, devem ser realizadas em uma única máquina; e todas as tarefas concluídas antes ou após a data de entrega geram custos adicionais que devem ser minimizados. Para validar a abordagem proposta, considerou-se um conjunto de instâncias disponibilizado na literatura. Os resultados obtidos mostram que a técnica proposta não foi inferior à literatura corrente em nenhuma das instâncias avaliadas; além disso, obteve resultados mais promissores em 30% das instâncias testadas quando comparado à abordagem VNS apenas com estrutura de memória, destacando assim o impacto do refinamento via Path-Relinking.