✦ LIBER ✦

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

✍ Scribed by Philippe Baptiste

Publisher: Springer US
Year: 1999
Tongue: English
Weight: 102 KB
Volume: 2
Category: Article
ISSN: 1094-6136
DOI: 10.1002/(sici)1099-1425(199911/12)2:6<245::aid-jos28>3.0.co;2-5

No coin nor oath required. For personal study only.

✦ Synopsis

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"p H "p, r H " w H ; H ), the problem can be solved in O(n). In the preemptive case, (1"p H "p, pmtn, r H " w H ; H ), the problem can be solved in O(n). Both algorithms are based upon dynamic programming.