An Improvement-Path Framework and an Exact Algorithm for Single-Machine Scheduling with Release Times
본 논문은 기계의 유휴 시간을 문제를 단순화하기 위한 음의 대기 시간으로 모델링하고 큐의 불연속성을 개선의 유일한 장애물로 규정함으로써, 출시 시간이 있는 NP-난해 단일 기계 스케줄링 문제에 대해 유한한 시간 내에 전역 최적 스케줄을 찾는 것을 보장하는 새로운 개선 경로 프레임워크와 정확한 반복 수선 알고리즘을 제안한다.