Energy-efficient algorithms for flow time minimization

Susanne Albers, Hiroshi Fujiwara

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

36 Scopus citations

Abstract

We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this paper we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable speed processor so as to minimize the total cost consisting of the power consumption and the total flow time of all the jobs. We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the paper is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time.

Original languageEnglish
Title of host publicationSTACS 2006
Subtitle of host publication23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Pages621-633
Number of pages13
DOIs
StatePublished - 2006
Externally publishedYes
EventSTACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings - Marseille, France
Duration: 23 Feb 200625 Feb 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3884 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceSTACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Country/TerritoryFrance
CityMarseille
Period23/02/0625/02/06

Fingerprint

Dive into the research topics of 'Energy-efficient algorithms for flow time minimization'. Together they form a unique fingerprint.

Cite this