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 2 )-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 ).