Real-Time Scheduling with Regenerative Energy

This paper investigates real-time scheduling in a system whose energy reservoir is replenished by an environmental power source. The execution of tasks is deemed primarily energy-driven, i.e., a task may only respect its deadline if its energy demand can be satisfied early enough. Hence, a useful scheduling policy should account for properties of the energy source, capacity of the energy storage as well as power dissipation of the single tasks. We show that conventional scheduling algorithms (like e.g. EDF) are not suitable for this scenario. Based on this motivation, we state and prove optimal scheduling algorithms that jointly handle constraints from both energy and time domain. Furthermore, an offline schedulability test for a set of periodic or even bursty tasks is presented. Finally, we validate the proposed theory by means of simulation and compare our algorithms with the classical earliest deadline first algorithm.