Competitive Analysis of Energy-Constrained Real-Time Scheduling

摘要

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 - 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. We also extend our analysis to other settings, including those with non-uniform value densities and dynamic voltage scaling capability.