An Improvement-Path Framework and an Exact Algorithm for Single-Machine Scheduling with Release Times
Este artigo propõe um novo framework de caminho de melhoria e um algoritmo de reparo iterativo exato que, ao modelar o tempo de ociosidade da máquina como tempo de espera negativo para simplificar a estrutura do problema e caracterizar a descontinuidade da fila como o único obstáculo à melhoria, garante a descoberta de um escalonamento globalmente ótimo para o problema de escalonamento de máquina única com tempos de liberação, que é NP-difícil, em tempo finito.