Minimizing the Number of Late Jobs with Release Time Constraint

Abstract

We consider the problem of preemptively scheduling a set of $N$ independent jobs with release times on $m\ge 1$ identical machines so as to minimize the number of late jobs. For a single machine, Lawler has given an $O(N^5)$ time algorithm for finding a schedule with the minimum number of late jobs. However, for fixed $m\ge 2$, the question of whether the problem can be shown to be solvable in polynomial time or shown to be NP-hard remained open over the last decade. In this paper, we answer this question by showing that it is NP-hard for every fixed $m\ge 2$.