Minimizing the number of tardy jobs in single machine sequencing

AbstractA set P of n jobs has to be processed without preemption, one job at a time, on a single machine. The weight and processing time of each job is one. Furthermore, the jobs are subject to precedence constraints represented by a given ordered set (P,⩽). In a feasibleschedule a job is called a tardy job if its completion time is strictly bigger than its due time. The problem is to find a feasible schedule that minimizes the number of tardy jobs. Clearly each job cannot be completed before ∣D(x)∣=∣{y in P: y⩽x}∣ units of time. So we fix a nonnegative integer k and we allow a tardiness of k units of time for each job. This problem seems to be hard even when the structure of the order on P is quite simple. In this paper we present an effective procedure for constructing an optimalschedule in some special cases. Moreover, we show that the problem of minimizing the number of tardy jobs for interval orders is related to an interesting combinatorial problem of ordered sets