License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10071.8
URN: urn:nbn:de:0030-drops-25351
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2535/
Go to the corresponding Portal

Chrobak, Marek ; Baptiste, Philippe ; Dürr, Christoph

Polynomial Time Algorithms for Minimum Energy Scheduling

pdf-format:
10071.ChrobakMarek.Paper.2535.pdf (0.2 MB)

Abstract

The aim of power management policies is to reduce the amount of energy consumed by computer systems while maintaining satisfactory level of performance. One common method for saving energy is to simply suspend the system during the idle times. No energy is consumed in the suspend mode. However, the process of waking up the system itself requires a certain fixed amount of energy, and thus suspending the system is beneficial only if the idle time is long enough to compensate for this additional energy expenditure. In the specific problem studied in the paper, we have a set of jobs with release times and deadlines that need to be executed on a single processor. Preemptions are allowed. The processor requires energy L to be woken up and, when it is on, it uses the energy at a rate of R units per unit of time. It has been an open problem whether a schedule minimizing the overall energy consumption can be computed in polynomial time. We solve this problem in positive, by providing an O(n5)-time
algorithm. In addition we provide an O(n4)-time algorithm for computing the minimum energy schedule when all jobs have unit length.

BibTeX - Entry

@InProceedings{chrobak_et_al:DagSemProc.10071.8,
  author =	{Chrobak, Marek and Baptiste, Philippe and D\"{u}rr, Christoph},
  title =	{{Polynomial Time Algorithms for Minimum Energy Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2010/2535},
  URN =		{urn:nbn:de:0030-drops-25351},
  doi =		{10.4230/DagSemProc.10071.8},
  annote =	{Keywords: Scheduling, algorithm, dynamic programming, energy}
}

Keywords: Scheduling, algorithm, dynamic programming, energy
Collection: 10071 - Scheduling
Issue Date: 2010
Date of publication: 03.05.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI