Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142641 | Operations Research Letters | 2013 | 6 Pages |
Abstract
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)O(1)-speed 11-approximation algorithm and our numerical experiments show that the speed-scaling ratio required is close to 11.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Rodrigo A. Carrasco, Garud Iyengar, Cliff Stein,