Paper Info
Title
Competitive analysis of online real-time scheduling algorithms under hard energy constraint
Abstract
In this paper, we undertake the competitive analysis of the online real-time scheduling problems under a given hard energy constraint. Specifically, we derive worst-case performance bounds that apply to any online algorithm, when compared to an optimal algorithm that has the knowledge of the input sequence in advance. First, by focusing on uniform value-density settings, we prove that no online algorithm can achieve a competitive factor greater than $1-\frac{e_{\max}}{E}$ , where e max驴 is the upper bound on the size of any job and E is the available energy budget. Then we propose a variant of EDF algorithm, EC-EDF, that is able to achieve this upper bound. We show that a priori information about the largest job size in the actual input sequence makes possible the design of a semi-online algorithm EC-EDF 驴 which achieves a constant competitive factor of 0.5. This turns out to be the best achievable competitive factor in these settings. In non-uniform value density settings, we derive an upper bound on the competitive factor achievable by any online algorithm, as well as the competitive factors of EC-EDF and EC-EDF 驴 algorithms. We also investigate the implications of having additional constraints on the online scheduling algorithm, including non-idling and non-preemptive execution constraints. Moreover, we analyze the case where the processor can adjust its speed at run-time through Dynamic Voltage Scaling (DVS) capability.
Year
DOI
Venue
2010
10.1007/s11241-010-9100-y
Realtime systems
Keywords
Field
DocType
Real-time systems,Energy management,Competitive analysis
Dynamic voltage scaling,Energy management,Online algorithm,Mathematical optimization,Upper and lower bounds,Scheduling (computing),Computer science,A priori and a posteriori,Real-time computing,Available energy,Distributed computing,Competitive analysis
Journal
Volume
Issue
ISSN
46
1
0922-6443
Citations 
PageRank 
References 
12
0.77
27
Authors
3
Name
Order
Citations
PageRank
Vinay Devadas11796.94
Fei Li2439.37
Hakan Aydin3121861.97