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

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(n⁷). In the preemptive case, (1|pj = p, pmtn, rj |wjUj), the problem can be solved in O(n¹⁰). Both algorithms are based upon dynamic programming.