Abordagens exatas e heurísticas para o problema de escalonamento de tarefas em uma máquina com tempos de setup dependentes da sequência e datas de liberação

Os problemas de escalonamento de tarefas possuem diversas variantes, que buscam representar diferentes situações em que um recurso é compartilhado por um conjunto de tarefas. Este projeto aborda o problema de escalonamento em uma única máquina, considerando datas de liberação e tempos de setup dependentes da sequência e não antecipatórios. O objetivo é minimizar o tempo de término da última tarefa do sequenciamento (makespan).

Para a resolução do problema, foram desenvolvidos métodos exatos e heurísticos. Na abordagem exata, foi proposto um algoritmo Branch-and-Price, baseado em uma formulação de geração de colunas. Como abordagem heurística, foi desenvolvida uma heurística híbrida que combina os métodos Iterated Local Search (ILS) e Beam Search, buscando explorar eficientemente o espaço de soluções e obter soluções de alta qualidade em tempos computacionais reduzidos.

Autores: Rafael Morais, Teobaldo Bulhões, Anand Subramanian