A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times

Abstract

We consider a class of n-job one-machine scheduling problems with ready time r(i), processing time p(i), and due time d(i) for each job i. Preemption is not allowed, and precedence constraints among jobs are not assumed. For this problem we show that there is a 0(n²)-time algorithm to find a schedule that minimizes the number of tardy jobs, under the assumption that r(i) < r(j) implies d(i) ≤ d(j).