, W is non-decreasing in w

, W (t) being an integral from 0 to t, W is continuous, W (0) = 0, and W has right-derivatives everywhere: W + (t) = sup u?0

F. Yao, A. Demers, and S. Shenker, A scheduling model for reduced CPU energy, IEEE Annual Foundations of Computer Science, pp.374-382, 1995.

N. Bansal, T. Kimbrel, and K. Pruhs, Speed scaling to manage energy and temperature, J. of the ACM, vol.54, issue.1, 2007.

B. Gaujal, A. Girault, and S. Plassart, Dynamic speed scaling minimizing expected energy consumption for real-time tasks, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01615835

J. Chen, N. Stoimenov, and L. Thiele, Feasibility analysis of on-line DVS algorithms for scheduling arbitrary event streams, Real-Time Systems Symposium, RTSS'09, (Washington (DC), USA), pp.261-270, 2009.

L. Thiele, S. Chakraborty, and M. Naedele, Real-time calculus for scheduling hard real-time systems, International Symposium on Circuits and Systems, ISCAS'00, pp.101-104, 2000.

R. Jejurikar and R. Gupta, Procrastination scheduling in fixed priority real-time systems, Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES'04, pp.57-66, 2004.

J. Augustine, S. Irani, and C. Swamy, Optimal power-down strategies, Symposium on Foundations of Computer Science, FOCS'04, pp.530-539, 2004.

C. Liu and J. Layland, Scheduling algorithms for multiprogramming in hard real-time environnement, J. of the ACM, vol.20, pp.46-61, 1973.

R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2018.

M. L. Puterman, Markov Decision Process : Discrete Stochastic Dynamic Programming. Wiley, wiley series in probability and statistics, 2005.

M. Petrovitsch, Sur une manière d'étendre le théorème de la moyence aux équations différentielles du premier ordre, Math. Ann, vol.54, issue.3, pp.417-436, 1901.

F. Baccelli and J. Mairesse, Ergodic Theorems for Stochastic Operators and Discrete Event Networks, Publications of the, pp.171-208, 1998.
URL : https://hal.archives-ouvertes.fr/inria-00074049

A. Marshall and I. Olkin, Inequalitites: Theory of Majorization and Its Applications, vol.143, 1979.

D. Bertsekas and J. Tsitsiklis, Neuro-dynamic programming, 1996.

A. Müller and D. Stoyan, Comparison Methods for Stochastic Models and Risks. No. ISBN: 978-0-471-49446-1 in Wiley Series in Probability and Statistics, 2002.

H. Yun and J. Kim, On energy-optimal voltage scheduling for fixed priority hard real-time systems, ACM Trans. Embed. Comput. Syst, vol.2, issue.3, pp.393-430, 2003.

M. Li and F. F. Yao, An efficient algorithm for computing optimal discrete voltage schedules, SIAM J. Comput, vol.35, pp.658-671, 2005.

B. Gaujal, N. Navet, and C. Walsh, Shortest path algorithms for real-time scheduling of fifo tasks with minimal energy use, ACM Trans. on Emb. Comput. Syst, vol.4, issue.4, 2005.
URL : https://hal.archives-ouvertes.fr/inria-00099957

J. Lorch and A. Smith, Improving dynamic voltage scaling algorithms with PACE, ACM SIGMETRICS 2001 Conference, pp.50-61, 2001.

F. Gruian, On energy reduction in hard real-time systems containing tasks with stochastic execution times, IEEE Workshop on Power Management for Real-Time and Embedded Systems, pp.11-16, 2001.

P. Pillai and K. G. Shin, Real-time dynamic voltage scaling for low-power embedded operating systems, SIGOPS Oper. Syst. Rev, vol.35, pp.89-102, 2001.

, Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria