Skip to Main content Skip to Navigation

A Linear Algorithm for Real-Time Scheduling with Optimal Energy Use

Bruno Gaujal 1 Nicolas Navet 2 Cormac Walsh 1
2 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present an algorithm for scheduling a set of non-recurrent tasks (or jobs) with real-time constraints so as to minimize the total energy consumption on a dynamically variable voltage processor. Our algorithm runs in linear time and is thus an improvement over the classical algorithm of Yao et al. It was made possible by considering the problem as a shortest path problem. We also propose an algorithm for the case where the processor possesses only a limited number of clock frequencies. We extend this algorithm to provide the minimum number of speed changes, which is important when the speed switching overhead cannot be neglected. All our algorithms are linear in the number of tasks if the arrivals and deadlines are sorted and need O(N logN) time otherwise and these complexities are shown optimal. We extend the results to fluid tasks and non-convex cost functions. An interesting by-product of this study is that it furnishes a linear time feasibility test for a set of non-recurrent tasks scheduled under EDF. This is an improvement over the classical one.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:33:22 PM
Last modification on : Friday, June 25, 2021 - 3:40:05 PM


  • HAL Id : inria-00071696, version 1


Bruno Gaujal, Nicolas Navet, Cormac Walsh. A Linear Algorithm for Real-Time Scheduling with Optimal Energy Use. [Research Report] RR-4886, LIP RR-2003-38, INRIA,LIP. 2003. ⟨inria-00071696⟩



Record views


Files downloads