Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

O sequenciamento de tarefas que utilizam um ou mais recursos é uma atividade corriqueira em ambientes industriais que deve ser realizada eficientemente. Por isso, há na literatura uma vasta gama de problemas que buscam modelar tais atividades. Dentre eles, destaca-se o problema de escalonamento de tarefas em uma unica máquina, sujeito a datas de liberação e tempos de setup dependentes da sequencia, com objetivo de minimizar o tempo da última tarefa executada (makespan). Este trabalho propõe uma meta-heurística para tal problema que utiliza uma estrutura de dados que permite a avaliação de movimentos em tempo constante amortizado durante a busca local. Experimentos computacionais realizados com um grupo de 1800 instâncias demonstram a competitividade do algoritmo proposto frente aos três melhores algoritmos encontrados na literatura. Em particular, o método desenvolvido foi capaz de melhorar a melhor solução conhecida em 1123 das 1800 instâncias testadas.