Summary: The scheduling problem \(1| pmtn,r_ j| \sum w_ jU_ j\) 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(nk^ 2W^ 2)\) and \(O(k^ 2W)\), 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,r_ j| \sum U_ j\), in which the objective is simply to minimize the number of late jobs, the pseudopolynomial time bound becomes polynomial, i.e. \(O(n^ 3k^ 2)\).