English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study classical deadline-based preemptive scheduling of tasks in acomputing environment equipped with both dynamic speed scaling and sleep statecapabilities: Each task is specified by a release time, a deadline and aprocessing volume, and has to be scheduled on a single, speed-scalableprocessor that is supplied with a sleep state. In the sleep state, theprocessor consumes no energy, but a constant wake-up cost is required totransition back to the active state. In contrast to speed scaling alone, theaddition of a sleep state makes it sometimes beneficial to accelerate theprocessing of tasks in order to transition the processor to the sleep state forlonger amounts of time and incur further energy savings. The goal is to outputa feasible schedule that minimizes the energy consumption. Since theintroduction of the problem by Irani et al. [16], its exact computationalcomplexity 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-approximationalgorithm and NP-hardness due to [2] and [2,17], respectively. We close theaforementioned gap between the upper and lower bound on the computationalcomplexity of speed scaling with sleep state by presenting a fullypolynomial-time approximation scheme for the problem. The scheme is based on atransformation to a non-preemptive variant of the problem, and a discretizationthat exploits a carefully defined lexicographical ordering among schedules.

A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State