Optimal Scheduling for Real-Time Jobs in Energy Harvesting Computing Systems

摘要

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.