Stage M2 - Ordonnancement online sous contraintes carbone : valeur de l’information sur le profil énergétique futur

Problématique

Réduire l’empreinte carbone du calcul passe de plus en plus par l’ordonnancement : exécuter les tâches lorsque l’électricité est peu carbonée (décalage temporel) ou là où elle l’est (décalage géographique) [1, 2]. Ces stratégies concernent les centres de données, mais aussi l’edge computing, où les profils énergétiques varient fortement selon le site et l’heure. En pratique, l’intensité carbone du réseau, la production renouvelable et le prix de l’électricité évoluent en temps réel et ne sont connus qu’imparfaitement à l’avance. Les tâches arrivent elles aussi au fil de l’eau,
et les décisions d’exécution doivent être prises de manière irrévocable, sans vision complète du futur : c’est le cadre de l’ordonnancement online.
Ces problèmes ont été largement étudiés dans leur version offline [3, 4], tandis que leur version online a fait l’objet de travaux plus récents [5, 6]. Dans ce cadre, la question de la valeur de l’information au sens de l’analyse compétitive reste peu explorée : il s’agit de comprendre dans quelle mesure une connaissance partielle du profil énergétique futur peut améliorer les garanties de performance des algorithmes. Le stage s’inscrit dans la continuité de travaux sur la valeur des informations partielles en ordonnancement semi-online [7, 8], dont les outils (bornes inférieures par argument d’adversaire, analyse de compétitivité) sont bien adaptés à ce nouveau cadre.

Problématique scientifique

La question centrale du stage est de déterminer quelles informations partielles sur le profil énergétique futur améliorent réellement la compétitivité d’un algorithme d’ordonnancement online, et comment concevoir des algorithmes qui les exploitent.
Le modèle de départ considère une machine (ou un serveur edge) qui traite des tâches arrivant au fil du temps, chacune avec une date de disponibilité rj , une durée pj et éventuellement une échéance dj . L’horizon est découpé en intervalles verts (énergie décarbonée, coût nul) et bruns (coût unitaire), ou plus généralement en créneaux d’intensité carbone c(t) ∈ [L, U ], révélés online en même temps que les tâches. L’objectif est de minimiser le coût carbone total, sous contrainte d’échéances ou en combinaison avec un critère classique, par exemple∑︁ j Cj + λ∑︁ t c(t), la seconde somme portant sur les créneaux utilisés.
Plusieurs informations supplémentaires (EPI) sur le profil énergétique seront étudiées : les bornes L et U de l’intensité carbone, la durée totale verte disponible sur l’horizon, la longueur de l’intervalle en cours ou la date du prochain changement, une fenêtre de prévision de longueur w, et enfin une prévision complète du profil entachée d’erreur. Pour chacune, il s’agira d’établir si elle fait baisser la borne inférieure de compétitivité (information potentiellement valuable) ou non (valueless), puis de proposer un algorithme semi-online qui en confirme la valeur, idéalement en
atteignant la nouvelle borne.
Les principaux verrous concernent la construction d’arguments d’adversaire lorsque deux sources d’incertitude coexistent (les tâches et le profil énergétique), ainsi que la conception d’algorithmes qui restent robustes lorsque les prévisions énergétiques sont imparfaites, dans l’esprit des algorithmes avec prédictions [9, 10].

Méthodologie et contributions attendues

Le stage débutera par une étude bibliographique couvrant l’ordonnancement online et semi-online, l’analyse de compétitivité, les problèmes de recherche online de type one-way trading et k-search [11], l’ordonnancement carbon-aware et les algorithmes avec prédictions. Le modèle de base sera ensuite fixé (machine unique, préemption ou non, critère retenu) et la liste des informations étudiées formalisée.
Le cœur du travail sera théorique. Il consistera d’abord à établir des bornes inférieures pour la version purement online et à analyser des algorithmes simples (exécution immédiate, attente de l’intervalle vert, règles à seuil), puis à reprendre cette analyse pour chaque information supplémentaire afin de conclure sur sa valeur. Si l’avancement le permet, le cas des prévisions imparfaites sera traité en étudiant l’arbitrage entre consistance et robustesse.
Les algorithmes proposés seront ensuite implémentés et comparés sur des instances pire cas et sur des traces réelles d’intensité carbone, afin d’évaluer l’écart entre garanties théoriques et performances observées.
Les contributions attendues sont une classification des informations sur le profil énergétique en valueless, potentiellement valuable et garanties valuable, proposer un algorithme semi-online prouvé avec son ratio de compétitivité, ainsi qu’une étude expérimentale. Selon les résultats, le travail pourra donner lieu à une soumission en conférence et ouvrir sur une thèse.

Mots clés : Ordonnancement online, Analyse de compétitivité, Valeur de l’information, Algo-
rithmes avec prédictions, Informatique bas-carbone

Lieu
Laboratoire d’accueil
Équipe Optimist – Laboratoire LORIA
Université de Lorraine
Campus Scientifique, 615 Rue du Jardin-Botanique, 54506 Vandœuvre-lès-Nancy
Encadrement : Dr. Hajar Nouinou, Pr. Ammar Oulamara

Profil du candidat :
• Être inscrit·e en Master 2 informatique, recherche opérationnelle ou mathématiques appliquées.
• Compétences en algorithmique théorique et les preuves (complexité, analyse d’algorithmes).
• Connaissances en ordonnancement ou en optimisation combinatoire appréciées.
• Programmation en Python et bon niveau en anglais scientifique.
Durée : 5 à 6 mois à partir de février 2027, avec gratification légale.
Candidature : Envoyer un CV détaillé, une lettre de motivation et les notes de M1 et M2 à :
hajar.nouinou@loria.fr avec comme objet de mail [candidature stage ONLINE Scheduling].

Références

[1] A. Radovanović et al., “Carbon-aware computing for datacenters,” IEEE Trans. Power Syst., vol. 38, no. 2, pp. 1270–
1280, 2023.
[2] T. Sukprasert, A. Souza, N. Bashir, D. Irwin, and P. Shenoy, “On the limitations of carbon-aware temporal and
spatial workload shifting in the cloud,” in Proc. EuroSys, 2024, pp. 924–941.
[3] P. Wiesner, I. Behnke, D. Scheinert, K. Gontarska, and L. Thamsen, “Let’s wait awhile : How temporal workload
shifting can reduce carbon emissions in the cloud,” in Proc. 22nd Int. Middleware Conf., 2021, pp. 260–272.
[4] Í. Goiri et al., “Greenslot : Scheduling energy consumption in green datacenters,” in Proc. SC’11, 2011, pp. 1–11.
[5] A. Lechowicz, N. Christianson, J. Zuo, N. Bashir, M. Hajiesmaili, A. Wierman, and P. Shenoy, “The online pause
and resume problem : Optimal algorithms and an application to carbon-aware load shifting,” Proc. ACM Meas.
Anal. Comput. Syst., vol. 7, no. 3, Art. 53, 2023.
[6] J. Cendrier, R. Wijayawardana, A. Benoit, Y. Robert, F. Vivien, and A. A. Chien, “Green scheduling on the edge,”
INRIA, Res. Rep. RR-9580, 2025.
[7] H. Nouinou, T. Arbaoui, and A. Yalaoui, “Minimising total weighted completion time for semi-online single ma-
chine scheduling with known arrivals and bounded processing times,” Int. J. Prod. Res., vol. 62, no. 6, pp. 2272–
2285, 2024.
[8] H. Nouinou, T. Arbaoui, and A. Yalaoui, “Minimizing the total completion time for a class of semi-online single
machine scheduling problems,” Theor. Comput. Sci., p. 115422, 2025.
[9] M. Mitzenmacher and S. Vassilvitskii, “Algorithms with predictions,” in Beyond the Worst-Case Analysis of Algo-
rithms, Cambridge Univ. Press, 2022, pp. 646–662.
[10] R. Kumar, M. Purohit, and Z. Svitkina, “Improving online algorithms via ML predictions,” in Proc. NeurIPS, 2018,
pp. 9684–9693.
[11] R. El-Yaniv, A. Fiat, R. M. Karp, and G. Turpin, “Optimal search and one-way trading online algorithms,” Algorith-
mica, vol. 30, no. 1, pp. 101–139, 2001.