MINIMIZING THE NUMBER OF TARDY JOBS IN SINGLE-MACHINE SEQUENCING

A 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 r epresented by a given ordered set (P, less-than-or-equal-to). In a fea sible schedule a job is called a tardy job if its completion time is s trictly bigger than its due time. The problem is to find a feasible sc hedule that minimizes the number of tardy jobs. Clearly each job canno t be completed before \D(x)\ = \{y in P: y less-than-or-equal-to x}\ u nits of time. So we fix a nonnegative integer k and we allow a tardine ss 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 pap er we present an effective procedure for constructing an optimal schedule in some special cases. Moreover, we show that the problem of minimizi ng the number of tardy jobs for interval orders is related to an inter esting combinatorial problem of ordered sets.