Energy reduction for scheduling a set of multiple feasible interval jobs

Time-critical jobs in many real-time applications have more than one feasible interval. Such jobs can be executed in any of their feasible intervals. Given a schedulable set of multiple feasible interval (MFI) jobs, energy can be saved by carefully selecting the executing interval for each job. In this paper, we explore the energy minimization problem for real-time systems in which jobs have more than one feasible interval. The static and dynamic energy management schemes are both investigated to minimize the energy consumption while preserving the system’s feasibility. Focusing on EDF scheduling algorithm, we first study reducing the dynamic power consumption of a single CPU. We show that the static optimal speed assignment problem is NP-Hard and propose a simulated annealing (SA) based approach to solve it. Then, we develop several on-line greedy algorithms to exploit run-time slack by reselecting a job’s executing interval on-the-fly. In addition, a leakage-aware version is discussed to improve the overall energy efficiency. Simulation results show that all proposed schemes achieve significant improvements of energy efficiency while the system remains schedulable.