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

Abstract

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.

• The article: PDF (196,497 bytes)
• Source material: ZIP (54,824 bytes)
• Self citation in BIBTeX (371 bytes)

© 2011 Sze-Hang Chan, Tak-Wah Lam, Lap-Kei Lee, Hing-Fung Ting and Peng Zhang
Licensed under a Creative Commons Attribution License

2011, Article 2

2010 Article 13

Special Issue

Published articles