TY - JOUR
T1 - Improved multi-processor scheduling for flow time and energy
AU - Lam, Tak Wah
AU - Lee, Lap Kei
AU - To, Isaac K.K.
AU - Wong, Prudence W.H.
N1 - Funding Information:
I.K.K. To and P.W.H. Wong are partially supported by EPSRC Grant EP/E028276/1.
Funding Information:
T.W. Lam is partially supported by HKU Grant 7176104.
PY - 2012/2
Y1 - 2012/2
N2 - Energy usage has been an important concern in recent research on online scheduling. In this paper, we study the tradeoff between flow time and energy (Albers and Fujiwara in ACM Trans. Algorithms 3(4), 2007; Bansal et al. in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 805-813, 2007b, Bansal et al. in Proceedings of International Colloquium on Automata, Languages and Programming, pp. 409-420, 2008; Lam et al. in Proceedings of European Symposium on Algorithms, pp. 647-659, 2008b) in the multi-processor setting. Our main result is an enhanced analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m ≥ 2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. The result still holds even if the comparison is made against the optimal migratory offline algorithm. This improves previous analysis that CRR is O(log P)-competitive where P is the ratio of the maximum job size to the minimum job size.
AB - Energy usage has been an important concern in recent research on online scheduling. In this paper, we study the tradeoff between flow time and energy (Albers and Fujiwara in ACM Trans. Algorithms 3(4), 2007; Bansal et al. in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 805-813, 2007b, Bansal et al. in Proceedings of International Colloquium on Automata, Languages and Programming, pp. 409-420, 2008; Lam et al. in Proceedings of European Symposium on Algorithms, pp. 647-659, 2008b) in the multi-processor setting. Our main result is an enhanced analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m ≥ 2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. The result still holds even if the comparison is made against the optimal migratory offline algorithm. This improves previous analysis that CRR is O(log P)-competitive where P is the ratio of the maximum job size to the minimum job size.
KW - Competitive analysis
KW - Dynamic speed scaling
KW - Energy minimization
KW - Multi-processor scheduling
KW - Online scheduling algorithms
UR - http://www.scopus.com/inward/record.url?scp=84861229683&partnerID=8YFLogxK
U2 - 10.1007/s10951-009-0145-5
DO - 10.1007/s10951-009-0145-5
M3 - Article
AN - SCOPUS:84861229683
SN - 1094-6136
VL - 15
SP - 105
EP - 116
JO - Journal of Scheduling
JF - Journal of Scheduling
IS - 1
ER -