ABSTRACT In this paper, we study a scheduling problem, in which every job is associated with a release time, deadline, required computation time, and required energy. We focus on an important special case where the jobs execute on a uniprocessor system that is supplied by a renewable energy source and use a rechargeable storage unit with limited capacity. Earliest deadline first (EDF) is a class one online algorithm in the classical real-time scheduling theory where energy constraints are not considered. We propose a semi-online EDF-based scheduling algorithm theoretically optimal (i.e., processing and energy costs neglected). This algorithm relies on the notions of energy demand and slack energy, which are different from the well known notions of processor demand and slack time. We provide an exact feasibility test. There are no restrictions on this new scheduler: each job can be one instance of a periodic, aperiodic, or sporadic task with deadline. INDEX TERMS Real-time systems, energy harvesting, uniprocessor, optimal scheduling, earliest deadline first, slack energy.
In the case of the uniprocessor, it Earliest Deadline First (EDF) scheduling has been shown as an optimal on-line algorithm for real-time systems in energy harvesting computing system with unpredictable energy supply REF .
Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems
IEEE Transactions on Emerging Topics in Computing
IEEE Transactions on Emerging Topics in Computing
Computer Science