TY - JOUR
T1 - Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints
AU - Carrasco, Rodrigo A.
AU - Iyengar, Garud
AU - Stein, Cliff
PY - 2013
Y1 - 2013
N2 - In this work we combine resource augmentation and alpha-point scheduling techniques, which have resulted in very good performance scheduling algorithms, to compute approximate solutions for a general family of scheduling problems: each job has a convex non-decreasing cost function and the goal is to compute a schedule that minimizes the total cost subject to precedence constraints. We show that our algorithm is a O(1)-speed 1-approximation algorithm and our numerical experiments show that the speed-scaling ratio required is close to 1.
AB - In this work we combine resource augmentation and alpha-point scheduling techniques, which have resulted in very good performance scheduling algorithms, to compute approximate solutions for a general family of scheduling problems: each job has a convex non-decreasing cost function and the goal is to compute a schedule that minimizes the total cost subject to precedence constraints. We show that our algorithm is a O(1)-speed 1-approximation algorithm and our numerical experiments show that the speed-scaling ratio required is close to 1.
KW - Alpha-points
KW - Approximation algorithms
KW - Job-dependent convex cost
KW - Scheduling
KW - Speed scaling
KW - Weighted tardiness
UR - http://www.scopus.com/inward/record.url?scp=84879069388&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2013.05.008
DO - 10.1016/j.orl.2013.05.008
M3 - Article
AN - SCOPUS:84879069388
SN - 0167-6377
VL - 41
SP - 436
EP - 441
JO - Operations Research Letters
JF - Operations Research Letters
IS - 5
ER -