Energy Minimization in Real-Time Systems: from Worst-Case Guarantees to Statistical Learning

This chapter investigates the following question: How can a server with a variable processing speed schedule jobs with hard deadlines while minimizing its energy consumption? We have addressed several variants of this problem. The common context is that we consider a single processing unit with variable processing speed capabilities (thanks to DVFS), and we consider real-time jobs, each one characterized by its release time, its size, and its relative deadline. We present first the simple case of a deterministic environment, where all the job characteristics are known. Two variants are studied here, of increasing uncertainty: (1) when a finite sequence of jobs must be scheduled off-line, and (2) when a possibly infinite sequence of jobs must be scheduled on-line. Then, we move to the more complex case of a stochastic environment: here, some job characteristics become known only when a job arrives (i.e., its relative deadline) or finishes (\i.e., its size), and only statistical information are known (i.e., the size distribution). Three variants are studied here, again of increasing uncertainty: (1) when there is a single job with known statistics, (2) when there are multiple jobs with known statistics, and (3) when there are multiple jobs with completely unknown statistics. The overall picture is that we progressively study variants of the problem where the available information becomes more and more complex. Throughout this presentation, we present the technical results and we provide the scheduling algorithms; mathematical proofs are only given for new results, since proofs for published results can be 156 found in the corresponding papers. The techniques we rely on include dynamic programming, Markov Decision Processes, and reinforcement learning.