Suppose that n jobs, each with a specified processing requirement and due date, are to be preemptively scheduled for processing by a number of parallel machines, with the objective of maximizing the number of jobs that are completed by their due dates. It is known that this scheduling problem is NP-hard, even for identical machines, if the number of machines is variable, that is, specified as part of the problem instance. However, if the machine environment consists of a fixed set of uniform machines, the problem can be solved in polynomial time. An O(n3) algorithm is presented for the special case of two uniform machines. The running time of this algorithm becomes O(Wn2), where W is the sum of the job weights, for the more general problem in which it is desired to minimize the weighted number of late jobs. A fully polynomial approximation scheme is also presented for the weighted case.
