TY - GEN
T1 - Speed scaling functions for flow time scheduling based on active job count
AU - Lam, Tak Wah
AU - Lee, Lap Kei
AU - To, Isaac K.K.
AU - Wong, Prudence W.H.
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=57749203967&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-87744-8_54
DO - 10.1007/978-3-540-87744-8_54
M3 - Conference contribution
AN - SCOPUS:57749203967
SN - 3540877436
SN - 9783540877431
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 647
EP - 659
BT - Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
T2 - 16th Annual European Symposium on Algorithms, ESA 2008
Y2 - 15 September 2008 through 17 September 2008
ER -