### Skapa referens, olika format (klipp och klistra)

**Harvard**

Antoniadis, A., Huang, C. och Ott, S. (2015) *A fully polynomial-time approximation scheme for speed scaling with sleep state*.

** BibTeX **

@conference{

Antoniadis2015,

author={Antoniadis, Antonios and Huang, Chien-Chung and Ott, Sebastian},

title={A fully polynomial-time approximation scheme for speed scaling with sleep state},

booktitle={Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms},

pages={1102},

abstract={We study classical deadline-based preemptive scheduling of jobs in a computing environment equipped with both dynamic speed scaling and sleep state capabilities: Each job is specified by a release time, a deadline and a processing volume, and has to be scheduled on a single, speed-scalable processor that is supplied with a sleep state. In the sleep state, the processor consumes no energy, but a constant wake-up cost is required to transition back to the active state. In contrast to speed scaling alone, the addition of a sleep state makes it sometimes beneficial to accelerate the processing of jobs in order to transition the processor to the sleep state for longer amounts of time and incur further energy savings. The goal is to output a feasible schedule that minimizes the energy consumption. Since the introduction of the problem by Irani et al. [17], its exact computational complexity has been repeatedly posed as an open question (see e.g. [2, 9, 16]). The currently best known upper and lower bounds are a 4/3-approximation algorithm and NP-hardness due to [2] and [2, 18], respectively. We close the aforementioned gap between the upper and lower bound on the computational complexity of speed scaling with sleep state by presenting a fully polynomial-time approximation scheme for the problem. The scheme is based on a transformation to a non-preemptive variant of the problem, and a discretization that exploits a carefully defined lexicographical ordering among schedules.},

year={2015},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 227047

A1 Antoniadis, Antonios

A1 Huang, Chien-Chung

A1 Ott, Sebastian

T1 A fully polynomial-time approximation scheme for speed scaling with sleep state

YR 2015

T2 Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

AB We study classical deadline-based preemptive scheduling of jobs in a computing environment equipped with both dynamic speed scaling and sleep state capabilities: Each job is specified by a release time, a deadline and a processing volume, and has to be scheduled on a single, speed-scalable processor that is supplied with a sleep state. In the sleep state, the processor consumes no energy, but a constant wake-up cost is required to transition back to the active state. In contrast to speed scaling alone, the addition of a sleep state makes it sometimes beneficial to accelerate the processing of jobs in order to transition the processor to the sleep state for longer amounts of time and incur further energy savings. The goal is to output a feasible schedule that minimizes the energy consumption. Since the introduction of the problem by Irani et al. [17], its exact computational complexity has been repeatedly posed as an open question (see e.g. [2, 9, 16]). The currently best known upper and lower bounds are a 4/3-approximation algorithm and NP-hardness due to [2] and [2, 18], respectively. We close the aforementioned gap between the upper and lower bound on the computational complexity of speed scaling with sleep state by presenting a fully polynomial-time approximation scheme for the problem. The scheme is based on a transformation to a non-preemptive variant of the problem, and a discretization that exploits a carefully defined lexicographical ordering among schedules.

LA eng

DO 10.1137/1.9781611973730.74

LK http://dx.doi.org/10.1137/1.9781611973730.74

OL 30