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

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

H. Aydin, R. G. Melhem, D. Mossé, and P. Mejía-alvarez, Determining optimal processor speeds for periodic real-time tasks with different power characteristics, Euromicro Conference on Real-Time Systems, ECRTS'01, pp.225-232, 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.

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

E. Bini and C. Scordino, Optimal two-level speed assignment for real-time systems, IJES, vol.4, issue.2, pp.101-111, 2009.

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.

J. Mao, C. G. Cassandras, and Q. Zhao, Optimal dynamic voltage scaling in energy-limited nonpreemptive systems with real-time constraints, IEEE Trans. Mob. Comput, vol.6, issue.6, pp.678-688, 2007.

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

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

B. Gaujal, N. Navet, and C. Walsh, Shortest Path Algorithms for Real-Time Scheduling of FIFO tasks with Minimal Energy Use, ACM Transactions on Embedded Computing Systems (TECS), vol.4, issue.4, 2005.
URL : https://hal.archives-ouvertes.fr/inria-00099957

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

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.

Q. Wu, P. Juang, M. Martonosi, and D. Clark, Voltage and frequency control with adaptive reaction time in multiple-clock-domain processors, International Conference on High-Performance Computer Architecture, HPCA'05, pp.178-189, 2005.

T. Burd and R. Brodersen, Design issues for dynamic voltage scaling, International Symposium on Low Power Electronics and Design, ISLPED'00, 2000.

M. Bandari, R. Simon, and H. Aydin, Energy management of embedded wireless systems through voltage and modulation scaling under probabilistic workloads, International Green Computing Conference, IGCC'14, pp.1-10, 2014.

K. Li, Energy and time constrained task scheduling on multiprocessor computers with discrete speed levels, J. of Parallel and Distributed Computing, vol.95, pp.15-28, 2016.

J. Wang, P. Roop, and A. Girault, Energy and timing aware synchronous programming, International Conference on Embedded Software, EMSOFT'16, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01412100

A. Bastoni, B. Brandenburg, and J. Anderson, Cache-related preemption and migration delays: Empirical approximation and impact on schedulability, Workshop on Operating Systems Platforms for Embedded Real-Time Applications, OSPERT'10, pp.33-44, 2010.

B. Brandenburg, Scheduling and Locking in Multiprocessor Real-Time Operating Systems, 2011.

B. Brandenburg and M. Gul, Global scheduling not required: Simple, near-optimal multiprocessor real-time scheduling with semi-partitioned reservations, Real-Time Systems Symposium, RTSS'16, pp.99-110, 2016.

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

P. Hilton and J. Pedersen, Catalan numbers, their generalization, and their uses, The Mathematical Intelligencer, vol.13, pp.64-75, 1991.

W. Horn, Some simple scheduling algorithms, Naval Research Logistics, vol.21, issue.1, pp.177-185, 1974.

J. K. Ousterhout, Why aren't operating systems getting faster as fast as hardware?, Proceedings of the Usenix Summer 1990 Technical Conference, pp.247-256, 1990.

B. Gaujal, A. Girault, and S. Plassart, A discrete time markov decision process for energy minimization under deadline constraints, Tech. Rep. XXXXX, Inria, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02391948

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.

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