The scheduling problem 1ℝpmtn,rjℝΣwjUj calls for n jobs with arbitrary release dates and due dates to be preemptively scheduled for processing by a single machine, with the objective of minimizing the sum of the weights of the late jobs. A dynamic programming algorithm for this problem is described. Time and space bounds for the algorithm are, respectively, O(nk2W2) and O(k2W), where k is the number of distinct release dates and W is the sum of the integer job weights. Thus, for the problem 1ℝpmtn,rjℝΣUj, in which the objective is simply to minimize the number of late jobs, the pseudopolynomial time bound becomes polynomial, i.e. O(n3k2).
