TY - JOUR
T1 - A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions
AU - Huo, Yumei
AU - Leung, Joseph Y.T.
AU - Wang, Xin
N1 - Funding Information:
The first author’s work was supported in part by the PSC-CUNY research fund and second author’s work was supported in part by the NSF grant DMI-0556010.
PY - 2009/8
Y1 - 2009/8
N2 - We consider the problem of preemptively scheduling n independent jobs on m parallel machines so as to minimize the makespan. Each job Jj has a release time rj and it can only be processed on a subset of machines Mj. The machines are linearly ordered. Each job Jj has a machine index aj such that 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 (n k log P + m n k2 + m3 k), where k is the number of distinct release times and P is the total processing time of all jobs.
AB - We consider the problem of preemptively scheduling n independent jobs on m parallel machines so as to minimize the makespan. Each job Jj has a release time rj and it can only be processed on a subset of machines Mj. The machines are linearly ordered. Each job Jj has a machine index aj such that 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 (n k log P + m n k2 + m3 k), where k is the number of distinct release times and P is the total processing time of all jobs.
KW - Inclusive processing set
KW - Makespan minimization
KW - Polynomial-time algorithms
KW - Preemptive scheduling
KW - Release time
UR - http://www.scopus.com/inward/record.url?scp=67349097086&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67349097086&partnerID=8YFLogxK
U2 - 10.1016/j.disopt.2009.02.002
DO - 10.1016/j.disopt.2009.02.002
M3 - Article
AN - SCOPUS:67349097086
SN - 1572-5286
VL - 6
SP - 292
EP - 298
JO - Discrete Optimization
JF - Discrete Optimization
IS - 3
ER -