Minimizing the Number of Late Jobs with Release Time Constraint

We consider the problem of preemptively scheduling a set of \(N\) independent jobs with release times on \(m \geq 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 \geq 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 \geq 2\).