Getting the best response for your erg

K.R. Pruhs, P. Uthaisombut, G.J. Woeginger

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

21 Citaten (Scopus)


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.
Originele taal-2Engels
TitelAlgorithm theory - SWAT 2004 : 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8 - 10, 2004 ; proceedings
RedacteurenT. Hagerup, J. Katajainen
Plaats van productieBerlin
ISBN van geprinte versie978-3-540-22339-9
StatusGepubliceerd - 2004

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Duik in de onderzoeksthema's van 'Getting the best response for your erg'. Samen vormen ze een unieke vingerafdruk.

Citeer dit