Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times

Abstract

We study the problem of minimizing the weighted number of late jobs to be scheduled on a single machine when processing times are equal. In this paper, we show that this problem, as well as its preemptive variant, are strongly polynomial. When preemption is not allowed (1∣pj=p, rj∣ΣwjUj), the problem can be solved in O(n7). In the preemptive case, (1∣pj=p, pmtn, rj ∣ΣwjUj), the problem can be solved in O(n10). Both algorithms are based upon dynamic programming. Copyright © 1999 John Wiley & Sons, Ltd.