Um algoritmo heurístico para resolver o problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes da sequência

Resumo

Este trabalho trata o Problema de Sequenciamento em Máquinas Paralelas NãoRelacionadas com Tempos de Preparação Dependentes da Sequência, objetivando minimizar o makespan. É proposto um algoritmo heurístico na qual a solução inicial é gerada por meio de um método construtivo guloso, e depois refinada pelo procedimento Iterated Local Search (ILS). O ILS usa como busca local o procedimento Adaptive Local Search (ALS), desenvolvido neste trabalho. O ALS consiste de duas buscas locais e uma perturbação, sendo que cada uma delas é escolhida de acordo com uma certa probabilidade, a qual depende do sucesso em iterações pregressas. Os experimentos computacionais mostraram que o algoritmo proposto supera dois algoritmos da literatura, tanto em termos de qualidade quanto em variabilidade da solução final. Além disso, o algoritmo estabeleceu novos limites superiores em mais de 95% das instâncias.