TY - CHAP
T1 - Energy Efficient Online Deadline Scheduling
AU - Chan, Ho-Leung
AU - Chan, Wun-Tat
AU - Lam, Tak-Wah
AU - Lee, Lap-Kei
AU - Mak, Kin-Sum
AU - Wong, Prudence W. H.
PY - 2007
Y1 - 2007
N2 - This paper extends the study of online algorithms for energy-efficient deadline scheduling to the overloaded setting. Specifically, we consider a processor that can vary its speed between 0 and a maximum speed T to minimize its energy usage (of which the rate is roughly a cubic function of the speed). As the speed is upper bounded, the system may be overloaded with jobs and no scheduling algorithms can meet the deadlines of all jobs. An optimal schedule is expected to maximize the throughput, and furthermore, its energy usage should be the smallest among all schedules that achieve the maximum throughput. In designing a scheduling algorithm, one has to face the dilemma of selecting more jobs and being conservative in energy usage. Even if we ignore energy usage, the best possible online algorithm is 4-competitive on throughput [12]. On the other hand, existing work on energy-efficient scheduling focuses on minimizing the energy to complete all jobs on a processor with unbounded speed, giving several O(1)-competitive algorithms with respect to the energy usage [2, 20]. This paper presents the first online algorithm for the more realistic setting where processor speed is bounded and the system may be overloaded; the algorithm is O(1)-competitive on both throughput and energy usage. If the maximum speed of the online scheduler is relaxed slightly to (1 + ε)T for some ε > 0, we can improve the competitive ratio on throughput to arbitrarily close to one, while maintaining O(1)-competitive on energy usage.
AB - This paper extends the study of online algorithms for energy-efficient deadline scheduling to the overloaded setting. Specifically, we consider a processor that can vary its speed between 0 and a maximum speed T to minimize its energy usage (of which the rate is roughly a cubic function of the speed). As the speed is upper bounded, the system may be overloaded with jobs and no scheduling algorithms can meet the deadlines of all jobs. An optimal schedule is expected to maximize the throughput, and furthermore, its energy usage should be the smallest among all schedules that achieve the maximum throughput. In designing a scheduling algorithm, one has to face the dilemma of selecting more jobs and being conservative in energy usage. Even if we ignore energy usage, the best possible online algorithm is 4-competitive on throughput [12]. On the other hand, existing work on energy-efficient scheduling focuses on minimizing the energy to complete all jobs on a processor with unbounded speed, giving several O(1)-competitive algorithms with respect to the energy usage [2, 20]. This paper presents the first online algorithm for the more realistic setting where processor speed is bounded and the system may be overloaded; the algorithm is O(1)-competitive on both throughput and energy usage. If the maximum speed of the online scheduler is relaxed slightly to (1 + ε)T for some ε > 0, we can improve the competitive ratio on throughput to arbitrarily close to one, while maintaining O(1)-competitive on energy usage.
M3 - Conference paper
T3 - Symposium on Discrete Algorithms (SODA)
SP - 795
EP - 804
BT - The Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms - SODA 2007
PB - Unknown Publisher
T2 - The Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)
Y2 - 7 January 2007 through 9 January 2007
ER -
