An O(n 2 ) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness

摘要

In this paper, we study the problem of scheduling n equal-length preemptive jobs on a single machine to minimize total tardiness, subject to release dates. The complexity status of this problem has remained open to date. We provide an O(n 2) time algorithm to solve the problem.