Getting the Best Response for Your Erg

Kirk Pruhs, Patchrawat Uthaisombut, Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

16 Citations (Scopus)

Abstract

We consider the bi-criteria problem of minimizing the average flow time (average response time) of a collection of dynamically released equi-work processes subject to the constraint that a fixed amount of energy is available. We assume that the processor has the ability to dynamically scale the speed at which it runs, as do current microprocessors from AMD, Intel, and Transmeta. We first reveal the combinatorial structure of the optimal schedule. We then use these insights to devise a relatively simple polynomial time algorithm to simultaneously compute, for each possible energy, the schedule with optimal average flow time subject to this energy constraint.
Original languageEnglish
Title of host publicationAlgorithm Theory - SWAT 2004
Subtitle of host publication9th Scandinavian Workshop on Algorithm Theory, Humlebæk, Denmark, July 8-10, 2004. Proceedings
EditorsTorben Hagerup, Jyrki Katajaien
Place of PublicationHeidelberg
PublisherSpringer
Pages14-25
Number of pages11
ISBN (Electronic)978-3-540-27810-8
ISBN (Print)978-3-540-22339-9
DOIs
Publication statusPublished - 2004
Event9th Scandinavian Workshop on Algorithm Theory, SWAT 2004 - Humlebaek, Denmark
Duration: 8 Jul 200410 Jul 2004
Conference number: 9

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3111
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th Scandinavian Workshop on Algorithm Theory, SWAT 2004
Abbreviated titleSWAT 2004
CountryDenmark
CityHumlebaek
Period8/07/0410/07/04

Keywords

  • METIS-219785

Fingerprint

Dive into the research topics of 'Getting the Best Response for Your Erg'. Together they form a unique fingerprint.

Cite this