TY - JOUR
T1 - Scheduling on two identical machines with a speed-up resource
AU - Xu, Haifeng
AU - Chen, Lin
AU - Ye, Deshi
AU - Zhang, Guochuan
N1 - Funding Information:
We would much like to thank the reviewers for their insightful comments which greatly help improve the pre- sentation of the paper. This paper was supported in part by NSFC (10971192) and (11071215).
PY - 2011/9/15
Y1 - 2011/9/15
N2 - We address a variant of scheduling problem on two identical machines, where we are given an additional speed-up resource. If a job uses the resource, its processing time may decrease. However, at any time the resource can only be used by at most one job. The objective is to minimize the makespan. For the offline version, we present an FPTAS. For the online version where jobs arrive over list, we propose an online algorithm with competitive ratio of 1.781, and show a lower bound of 1.686 for any online algorithm.
AB - We address a variant of scheduling problem on two identical machines, where we are given an additional speed-up resource. If a job uses the resource, its processing time may decrease. However, at any time the resource can only be used by at most one job. The objective is to minimize the makespan. For the offline version, we present an FPTAS. For the online version where jobs arrive over list, we propose an online algorithm with competitive ratio of 1.781, and show a lower bound of 1.686 for any online algorithm.
KW - FPTAS
KW - Online algorithms
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=79958070443&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2011.05.022
DO - 10.1016/j.ipl.2011.05.022
M3 - Article
AN - SCOPUS:79958070443
SN - 0020-0190
VL - 111
SP - 831
EP - 835
JO - Information Processing Letters
JF - Information Processing Letters
IS - 17
ER -