Paper Info
Title
Improved multi-processor scheduling for flow time and energy
Abstract
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.
Year
DOI
Venue
2012
10.1007/s10951-009-0145-5
Journal of Scheduling
Keywords
Field
DocType
Online scheduling algorithms,Multi-processor scheduling,Competitive analysis,Dynamic speed scaling,Energy minimization
Online algorithm,Mathematical optimization,Fair-share scheduling,Scheduling (computing),Computer science,Automaton,Algorithm,Flow time,Real-time computing,Rate-monotonic scheduling,Energy minimization,Competitive analysis
Journal
Volume
Issue
ISSN
12
6
1094-6136
Citations 
PageRank 
References 
7
0.54
29
Authors
4
Name
Order
Citations
PageRank
Tak-Wah Lam11860164.96
Lap-Kei Lee240621.59
Isaac K. K. To31326.41
Prudence W. H. Wong437438.69