| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1141580 | Discrete Optimization | 2009 | 7 Pages |
Abstract
We consider the problem of preemptively scheduling nn independent jobs on mm parallel machines so as to minimize the makespan. Each job JjJj has a release time rjrj and it can only be processed on a subset of machines MjMj. The machines are linearly ordered. Each job JjJj has a machine index ajaj such that Mj={Maj,Maj+1,…,Mm}Mj={Maj,Maj+1,…,Mm}. We first show that there is no 1-competitive online algorithm for this problem. We then give an offline algorithm with a running time of O(nklogP+mnk2+m3k)O(nklogP+mnk2+m3k), where kk is the number of distinct release times and PP is the total processing time of all jobs.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Yumei Huo, Joseph Y.-T. Leung, Xin Wang,