Abstract | ||
---|---|---|
We consider the problem of online dynamic power management that provides hard real-time guarantees. In this problem, each of the given jobs is associated with an arrival time, a deadline, and an execution time, and the objective is to decide a schedule of the jobs as well as a sequence of state transitions on the processors so as to minimize the total energy consumption. In this paper, we examine the problem complexity and provide online strategies to achieve energy-efficiency. First, we show that the competitive factor of any online algorithm for this problem is at least 2.06. Then we present an online algorithm which gives a 4-competitive schedule. When the execution times of the jobs are unit, we show that the competitive factor improves to 3.59. At the end, the algorithm is generalized to allow a trade-off between the number of processors we use and the energy-efficiency of the resulting schedule. |
Year | Venue | Field |
---|---|---|
2013 | CoRR | Online algorithm,Dynamic power management,Computer science,Problem complexity,Execution time,Energy consumption,Competitive analysis,Distributed computing |
DocType | Volume | Citations |
Journal | abs/1304.1590 | 0 |
PageRank | References | Authors |
0.34 | 11 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jian-Jia Chen | 1 | 2007 | 129.20 |
Mong-jen Kao | 2 | 26 | 7.82 |
D. T. Lee | 3 | 2418 | 1083.30 |
Ignaz Rutter | 4 | 315 | 44.45 |
Dorothea Wagner | 5 | 2362 | 221.67 |