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

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.Nous proposons un algorithme pour ordonnancer un ensemble de tâches non-récurrents (ou "jobs")soumises à des contraintes temps réels de façon à minimiser la consommation en énergie sur un processeur dont la tension d'alimentation peut-être modifiée en ligne ("dynamic voltage scaling"). cet algorithme est linéaire en le nombre de tâches, ce qui constitue un amélioration par rapport à l'algorithme classique de Yao et Al; Cette amélioration a été possible en considérant ce problème d'ordonnancement comme un problème de plus court chemin. Nous présentons aussi un algorithme pour le cas où le processeur possède un nombre fini de vitesses; nous l'étendons ensuite pour minimiser le nombre de changement de vitesses ce qui est important lorsque le coût d'un changement de vitesses ne peut être négligé. Tous les algorithmies sont linéaires en le nombre de tâches si les instants d'arrivées et d'échéances sont triés et en O(N log N) sinon. Ces complexités sont prouvées optimales. Nous étendons ensuite les résultats au cas des tâches fluides at aux fonctions de coût non-convexes. Une contribution intéressante de cette étude est qu'elle fournit un algorithme linéaire pour tester la faisabilité d'un ensemble de tâches ordonnancées sous EDF, ce qui est une amélioration sur le test classique présenté dans [13