Name
Abstract | ||
|---|---|---|
We investigate a very basic problem in dynamic speed scaling where a sequence of jobs, each specified by an arrival time, a deadline and a processing volume, has to be processed so as to minimize energy consumption. We study multi-processor environments with m parallel variable-speed processors assuming that job migration is allowed, i.e. whenever a job is preempted it may be moved to a different processor. We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time, given any convex non-decreasing power function. In contrast to a previously known strategy, our algorithm does not resort to linear programming. For the online problem, we extend two algorithms Optimal Available and Average Rate proposed by Yao et al. 15] for the single processor setting. Here we concentrate on power functions P ( s ) = s α , where s is the processor speed and α 1 is a constant. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.jcss.2015.03.001 | Journal of Computer and System Sciences |
Keywords | Field | DocType |
Energy efficiency,Offline algorithm,Online algorithm,Flow computation,Competitive analysis | Power function,Online algorithm,Discrete mathematics,Mathematical optimization,Computer science,Algorithm,Schedule,Linear programming,Time complexity,Energy consumption,Clock rate,Competitive analysis | Journal |
Volume | Issue | ISSN |
81 | 7 | 0022-0000 |
Citations | PageRank | References |
14 | 0.69 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Susanne Albers | 1 | 1538 | 107.42 |
| Antonios Antoniadis | 2 | 127 | 13.81 |
| Gero Greiner | 3 | 82 | 4.48 |