Minimizando o makespan no escalonamento de tarefas em máquina única com tempos de setup dependentes da sequência e restrições de inventário

Este trabalho introduz e estuda o problema de escalonamento de tarefas que combina datas de liberação, tempos de setup dependentes da sequência e restrições de inventário em uma única máquina. Foram propostas quatro formulações matemáticas e desenvolvidos algoritmos exatos Branch-and-Cut (B&C) e Branch-Cut-and-Price (BCP), além de uma heurística que combina Beam Search, Ruin-and-Recreate e Iterated Local Search, denominada BeRRILS. Os resultados computacionais mostraram que a formulação baseada em arcos apresentou o melhor desempenho entre os modelos, enquanto o BCP resolveu mais instâncias até a otimalidade e o B&C obteve menores gaps médios. A heurística proposta mostrou-se competitiva e robusta na obtenção de soluções viáveis, destacando-se o impacto positivo da utilização da perturbação baseada em Ruin-and-Recreate.

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