Energy-Efficient Algorithms for Flow Time Minimization

被引:102
作者
Albers, Susanne [1 ]
Fujiwara, Hiroshi [2 ]
机构
[1] Univ Freiburg, Dept Comp Sci, Georges Kohler Allee 79, D-79110 Freiburg, Germany
[2] Kwansei Gakuin Univ, Sch Sci & Technol, Dept Informat, Sanda 6691337, Japan
关键词
Variable-speed processor; flow time; online algorithms; competitive analysis; offline algorithms; dynamic programming;
D O I
10.1145/1290672.1290686
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this article we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable-speed processor so as to minimize the total cost consisting of the energy consumption and the total flow time of all jobs. We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the article is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time.
引用
收藏
页数:17
相关论文
共 16 条
[1]   Optimal power-down strategies [J].
Augustine, J ;
Irani, S ;
Swamy, C .
45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2004, :530-539
[2]   Dynamic speed scaling to manage energy and temperature [J].
Bansal, N ;
Kimbrel, T ;
Pruhs, K .
45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2004, :520-529
[3]  
Bansal N, 2005, LECT NOTES COMPUT SC, V3404, P460
[4]  
BANSAL N., 2007, P 18 ACM SIAM S DISC
[5]  
Bunde D., 2006, P 18 ANN ACM S PAR A, P190, DOI DOI 10.1145/1148109.1148140
[6]  
Cornu~ejols G., 1990, DISCRETE LOCATION TH, P119
[7]   On-line analysis of the TCP acknowledgment delay problem [J].
Dooly, DR ;
Goldman, SA ;
Scott, SD .
JOURNAL OF THE ACM, 2001, 48 (02) :243-273
[8]  
Fabrikant Alex, 2003, PODC 2003, P347, DOI [10.1145/872035.872088, DOI 10.1145/872035.872088]
[9]  
Irani S, 2003, SIAM PROC S, P37
[10]  
Irani S., 2005, SIGACT NEWS, V36, P63, DOI DOI 10.1145/1067309.1067324