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

Le stage se déroulera au sein de l’équipe OPTIMIST (OPTImization Methods for Integrated SysTems) du LORIA (Laboratoire lorrain de recherche en informatique et ses applications). Le LORIA est une unité mixte de recherche (UMR 7503) située sur le campus scientifique de Vandœuvre-lès-Nancy.

Créée en 2016, l’équipe OPTIMIST conçoit des algorithmes et des outils d’aide à la décision pour des systèmes complexes et intégrés. Ses travaux combinent recherche opérationnelle, optimisation combinatoire et algorithmique. Ils s’appliquent à des domaines variés :

l’informatique, avec le cloud computing et la virtualisation des fonctions réseau ;

les villes intelligentes, avec la mobilité et les réseaux électriques intelligents ;

l’industrie, avec l’ordonnancement de production, le transport et la logistique.

Le sujet de ce stage, à l’interface de l’ordonnancement et de l’énergie, s’inscrit pleinement dans ces thématiques.

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é r_j, une durée p_j et éventuellement une échéance d_j. 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) comprise entre L et 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 la somme des dates de fin augmentée du coût carbone des 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, 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.

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 machine 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 Algorithms, 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," Algorithmica, vol. 30, no. 1, pp. 101–139, 2001.

• Ê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 et/ou en optimisation combinatoire appréciées.
• Programmation en Python et bon niveau en anglais scientifique.