Chicago Journal of Theoretical Computer Science

CJTCS Special Issue: CATS 2010

Selected papers from

2010 Computing: The Australasian Theory Symposium

held in Brisbane, Australia, January 18-21 2010.

Guest Editors: Taso Viglas, University of Sydney, Australia

Alex Potanin, Victoria University, Wellington, NZ

Article 2011-1

Published by the Department of Computer Science, The University of Chicago.

Non-clairvoyant Scheduling for Weighted Flow Time and Energy on Speed Bounded Processors

Sze-Hang Chan
Department of Computer Science
University of Hong Kong
Hong Kong,
Tak-Wah Lam
Department of Computer Science
University of Hong Kong
Hong Kong,
Lap-Kei Lee
Max-Planck-Institut für Informatik
66123 Saarbrücken
Hing-Fung Ting
Department of Computer Science
University of Hong Kong
Hong Kong
Peng Zhang
School of Computer Science and Technology
Shandong University
May 5, 2011

We consider the online scheduling problem of minimizing total weighted flow time plus energy in the dynamic speed scaling model, where a processor can scale its speed dynamically between 0 and some maximum speed T. In the past few years this problem has been studied extensively under the clairvoyant setting, which requires the size of a job to be known at release time [AlF07,BPS07,BCL+08,LLT+esa08,LLT+spaa08,BCP09,GNS09,LLT+09]. For the non-clairvoyant setting, despite its practical importance, the progress is relatively limited. Only recently an online algorithm [LAPS] is known to be O(1)-competitive for minimizing (unweighted) flow time plus energy in the infinite speed model (i.e., T = ∞) [CEL+09,CEP09]. This paper makes two contributions to the non-clairvoyant scheduling. First, we resolve the open problem that the unweighted result of [LAPS] can be extended to the more realistic model with bounded maximum speed. Second, we show that another non-clairvoyant algorithm [WRR] is O(1)-competitive when weighted flow time is concerned. Note that [WRR] is not as efficient as [LAPS] for scheduling unweighted jobs as [WRR] has a much bigger constant hidden in its competitive ratio.

DOI: 10.4086/cjtcs.2011.001

[] 2011, Article 2 [] 2010 Article 13
[back] Special Issue [back] Published articles
[CJCTS home]