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

DOI10.1137/1.9781611973730.74MaRDI QIDQ5363002zbMATH OpenOpenAlexFDO

Authors Antonios Foivos Antoniadis, Chien-Chung Huang, Sebastian Ott

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.0892

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Abstract: We study classical deadline-based preemptive scheduling of tasks in a computing environment equipped with both dynamic speed scaling and sleep state capabilities: Each task 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 tasks 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. [16], its exact computational complexity has been repeatedly posed as an open question (see e.g. [2,8,15]). The currently best known upper and lower bounds are a 4/3-approximation algorithm and NP-hardness due to [2] and [2,17], 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.

Recommendations

• A fully polynomial-time approximation scheme for speed scaling with a sleep state
• Race to idle: new algorithms for speed scaling with a sleep state
• Race to idle: new algorithms for speed scaling with a sleep state
• New online algorithm for dynamic speed scaling with sleep state
• Speed-scaling with no preemptions

Cited in

(10)

• A fully polynomial-time approximation scheme for speed scaling with a sleep state
• Sleep with Guilt and Work Faster to Minimize Flow Plus Energy
• A survey of offline algorithms for energy minimization under deadline constraints
• Race to idle or not: balancing the memory sleep time with DVS for energy minimization
• Online dynamic power management with hard real-time guarantees
• Race to idle: new algorithms for speed scaling with a sleep state
• On the NP-hardness of speed scaling with sleep state
• New online algorithm for dynamic speed scaling with sleep state
• Speed scaling problems with memory/cache consideration
• Race to idle: new algorithms for speed scaling with a sleep state

This page was built for publication: A fully polynomial-time approximation scheme for speed scaling with sleep state

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363002)