Speed Scaling for Maximum Lateness

被引:3
作者
Bampis, Evripidis [1 ]
Letsios, Dimitrios [1 ]
Milis, Ioannis [2 ]
Zois, Georgios [1 ,2 ]
机构
[1] Univ Paris 06, Sorbonne Univ, UMR 7606, LIP6, F-75005 Paris, France
[2] Athens Univ Econ & Business, Dept Informat, Athens, Greece
关键词
Energy efficiency; Speed scaling; Scheduling; Maximum lateness; ENERGY;
D O I
10.1007/s00224-015-9622-8
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider the power-aware problem of scheduling non-preemptively a set of jobs on a single speed-scalable processor so as to minimize the maximum lateness, under a given budget of energy. In the offline setting, our main contribution is a combinatorial polynomial time algorithm for the case in which the jobs have common release dates. In the presence of arbitrary release dates, we show that the problem becomes strongly NP-hard. Moreover, we show that there is no O(1)-competitive deterministic algorithm for the online setting in which the jobs arrive over time. Then, we turn our attention to an aggregated variant of the problem, where the objective is to find a schedule minimizing a linear combination of maximum lateness and energy. As we show, our results for the budget variant can be adapted to derive a similar polynomial time algorithm and an NP-hardness proof for the aggregated variant in the offline setting, with common and arbitrary release dates respectively. More interestingly, for the online case, we propose a 2-competitive algorithm.
引用
收藏
页码:304 / 321
页数:18
相关论文
共 16 条
[1]  
Albers S., 2011, STACS LIPICS, V9, P1
[2]   Energy-Efficient Algorithms for Flow Time Minimization [J].
Albers, Susanne ;
Fujiwara, Hiroshi .
ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (04)
[3]   Energy-Efficient Algorithms [J].
Albers, Susanne .
COMMUNICATIONS OF THE ACM, 2010, 53 (05) :86-96
[4]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[5]   SPEED SCALING FOR WEIGHTED FLOW TIME [J].
Bansal, Nikhil ;
Pruhs, Kirk ;
Stein, Cliff .
SIAM JOURNAL ON COMPUTING, 2009, 39 (04) :1294-1308
[6]  
Boyd S, 2004, CONVEX OPTIMIZATION
[7]  
Brucker P., 1977, Ann. Discrete Math., V1, P343, DOI [DOI 10.1016/S0167-5060(08)70743-X, 10.1016/S0167-5060(08)70743-X]
[8]   Power-aware scheduling for makespan and flow [J].
Bunde, David P. .
JOURNAL OF SCHEDULING, 2009, 12 (05) :489-500
[9]   Speed is as powerful as clairvoyance [J].
Kalyanasundaram, B ;
Pruhs, K .
JOURNAL OF THE ACM, 2000, 47 (04) :617-643
[10]  
Lawler W.H., 1976, SEQUENCING SCHEDULIN, V4, P445