From preemptive to non-preemptive speed-scaling scheduling

被引:13
作者
Bampis, Evripidis [1 ]
Kononov, Alexander [2 ]
Letsios, Dimitrios [1 ,3 ]
Lucarelli, Giorgio [1 ,3 ]
Nemparis, Loannis [1 ,4 ]
机构
[1] Univ Paris 06, LIP6, F-75252 Paris 05, France
[2] Sobolev Inst Math, Novosibirsk, Russia
[3] Univ Evry, IBISC, Evry, France
[4] NKUA, Dept Informat & Telecommun, Athens, Greece
关键词
Approximation algorithms; Speed-scaling; Non-preemptive scheduling;
D O I
10.1016/j.dam.2014.10.007
中图分类号
O29 [应用数学];
学科分类号
070104 [应用数学];
摘要
We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed s then the energy consumption is s(alpha) units of energy per time unit, where alpha > 1 is a small constant. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption to be minimized. While most previous works have studied the preemptive case of the problem, where a job may be interrupted and resumed later, we focus on the non-preemptive case where once a job starts its execution, it has to continue until its completion without any interruption. As the preemptive case is known to be polynomially solvable for both the single-processor and the multiprocessor case, we explore the idea of transforming an optimal preemptive schedule to a non-preemptive one. We prove that the preemptive optimal solution does not preserve enough of the structure of the non-preemptive optimal solution, and more precisely that the ratio between the energy consumption of an optimal non-preemptive schedule and the energy consumption of an optimal preemptive schedule can be very large even for the single-processor case. Then, we focus on some interesting families of instances: (i) equal-work jobs on a single-processor, and (ii) agreeable instances in the multiprocessor case. In both cases, we propose constant factor approximation algorithms. In the latter case, our algorithm improves the best known algorithm of the literature. Finally, we propose a (non-constant factor) approximation algorithm for general instances in the multiprocessor case. (C) 2014 Elsevier B.V. All rights reserved.
引用
收藏
页码:11 / 20
页数:10
相关论文
共 20 条
[1]
Albers S, 2011, SPAA 11: PROCEEDINGS OF THE TWENTY-THIRD ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, P279
[2]
Energy-Efficient Algorithms [J].
Albers, Susanne .
COMMUNICATIONS OF THE ACM, 2010, 53 (05) :86-96
[3]
Albers S, 2007, SPAA'07: PROCEEDINGS OF THE NINETEENTH ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, P289
[4]
Angel E., 2013, ABS13091732 CORR
[5]
Angel E, 2012, LECT NOTES COMPUT SC, V7484, P128, DOI 10.1007/978-3-642-32820-6_15
[6]
Antoniadis Antonios, 2012, Algorithm Theory-SWAT 2012. Proceedings 13th Scandinavian Symposium and Workshops, P249, DOI 10.1007/978-3-642-31155-0_22
[7]
Bampis Evripidis, 2012, Computing and Combinatorics. Proceedings of the 18th Annual International Conference COCOON 2012, P25, DOI 10.1007/978-3-642-32241-9_3
[8]
Bampis E., 2013, LIPICS SCHLOSS DAGST
[9]
Bampis E, 2012, LECT NOTES COMPUT SC, V7676, P106
[10]
Energy Optimal Scheduling on Multiprocessors with Migration [J].
Bingham, Brad D. ;
Greenstreet, Mark R. .
PROCEEDINGS OF THE 2008 INTERNATIONAL SYMPOSIUM ON PARALLEL AND DISTRIBUTED PROCESSING WITH APPLICATIONS, 2008, :153-161