Speed scaling functions for flow time scheduling based on active job count

Tak Wah Lam, Lap Kei Lee, Isaac K.K. To, Prudence W.H. Wong

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

62 Citations (Scopus)

Abstract

We study online scheduling to minimize flow time plus energy usage in the dynamic speed scaling model. We devise new speed scaling functions that depend on the number of active jobs, replacing the existing speed scaling functions in the literature that depend on the remaining work of active jobs. The new speed functions are more stable and also more efficient. They can support better job selection strategies to improve the competitive ratios of existing algorithms [8,5], and, more importantly, to remove the requirement of extra speed. These functions further distinguish themselves from others as they can readily be used in the non-clairvoyant model (where the size of a job is only known when the job finishes). As a first step, we study the scheduling of batched jobs (i.e., jobs with the same release time) in the non-clairvoyant model and present the first competitive algorithm for minimizing flow time plus energy (as well as for weighted flow time plus energy); the performance is close to optimal.

Original languageEnglish
Title of host publicationAlgorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
Pages647-659
Number of pages13
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event16th Annual European Symposium on Algorithms, ESA 2008 - Karlsruhe, Germany
Duration: 15 Sept 200817 Sept 2008

Publication series

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

Conference

Conference16th Annual European Symposium on Algorithms, ESA 2008
Country/TerritoryGermany
CityKarlsruhe
Period15/09/0817/09/08

Fingerprint

Dive into the research topics of 'Speed scaling functions for flow time scheduling based on active job count'. Together they form a unique fingerprint.

Cite this