Minimizing the number of late jobs on a single machine under due date uncertainty

We study the problem of minimizing the number of late jobs on a single machine where job processing times are known precisely and due dates are uncertain. The uncertainty is captured through a set of scenarios. In this environment, an appropriate criterion to select a schedule is to find one with the best worst‐case performance, which minimizes the maximum number of late jobs over all scenarios. For a variable number of scenarios and two distinct due dates over all scenarios, the problem is proved NP‐hard in the strong sense and non‐approximable in pseudo‐polynomial time with approximation ratio less than 2. It is polynomially solvable if the number s of scenarios and the number v of distinct due dates over all scenarios are given constants. An O(nlog n) time s‐approximation algorithm is suggested for the general case, where n is the number of jobs, and a polynomial 3‐approximation algorithm is suggested for the case of unit‐time jobs and a constant number of scenarios. Furthermore, an O(n ^s+v-2/(v-1) ^v-2) time dynamic programming algorithm is presented for the case of unit‐time jobs. The problem with unit‐time jobs and the number of late jobs not exceeding a given constant value is solvable in polynomial time by an enumeration algorithm. The obtained results are related to a min‐max assignment problem, an exact assignment problem and a multi‐agent scheduling problem.