Paper Info
Title
Competitive online algorithms for multiple-machine power management and weighted flow time
Abstract
We consider online job scheduling together with power management on multiple machines. In this model, jobs with arbitrary sizes and weights arrive online, and each machine consumes different amount of energy when it is processing a job, idling or sleeping. A scheduler has to maintain a good balance of the states of the machines to avoid energy wastage, while giving an efficient schedule of the jobs. We consider a recently well-studied objective of minimizing the total weighted flow time of the jobs plus the total energy usage. For the special case where all jobs have the same weight, competitive algorithms have been obtained (Lam et al. 2009, Chan et al. 2011). This paper gives a non-trivial potential analysis of a weighted generalization of the power management algorithm in (Chan et al. 2011), coupled with a classic scheduling algorithm HDF. This leads to the first competitive result for minimizing weighted flow time plus energy. The result can be extended to the dynamic speed scaling model where the scheduler can vary the speed of individual machines to process the jobs and the energy usage depends on the speed of the machines.
Year
Venue
Keywords
2013
CATS
competitive algorithm,energy wastage,energy usage,classic scheduling algorithm,total weighted flow time,total energy usage,multiple-machine power management,competitive result,weighted generalization,dynamic speed,competitive online algorithm,weighted flow time
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
11
6
Name
Order
Citations
PageRank
Ho-Leung Chan147125.23
Sze-Hang Chan2433.80
Tak-Wah Lam31860164.96
Lap-Kei Lee440621.59
Rongbin Li5422.64
Chi-Man Liu6967.06