A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs |
| |
Authors: | E L Lawler |
| |
Institution: | (1) Computer Science Division, University of California, 94720 Berkeley, CA, USA |
| |
Abstract: | The scheduling problem 1|pmtn, r
j
|w
j
U
j
calls forn 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
2
W
2) andO(k
2
W), wherek is the number of distinct release dates andW is the sum of the integer job weights. Thus, for the problem 1|pmtn, r
j
|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
3
k
2). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|