Thèse Allocation de Ressources Cloud par l'Ordonnancement Multi-Agents H/F - Doctorat.Gouv.Fr

Établissement : Université Paris-Saclay GS Informatique et sciences du numérique École doctorale : Sciences et Technologies de l'Information et de la Communication Laboratoire de recherche : IBISC - Informatique, BioInformatique, Systèmes Complexes Direction de la thèse : Jean-Christophe JANODET ORCID 0009000468061712 Début de la thèse : 2026-10-01 Date limite de candidature : 2026-05-12T23:59:59 Dans les environnements Cloud et Edge Computing, l'allocation d'une ressource partagée (processeur, bande passante) à des utilisateurs ayant des contraintes hétérogènes est un défi industriel majeur [5]. L'approche classique d'optimisation globale montre ses limites face à la réalité des contrats de service (Service Level Agreement, SLA) individualisés.
Pour relever ce défi, cette thèse s'appuie sur le cadre théorique de l'ordonnancement multi-agents, introduit initialement par Agnetis et al. [1] et largement structuré depuis [2, 3]. Nous proposons d'étudier un modèle d'ordonnancement sur machine unique [4] partagée par deux clients aux exigences conflictuelles :
- L'Agent A (Flux critiques / Temps Réel) : Il représente des services exigeant une forte réactivité et une synchronisation précise (ex : streaming vidéo, objets connectés). L'objectif est d'optimiser des métriques de performance temporelles (par exemple, minimiser la pénalité liée aux avances et aux retards par rapport à une échéance, ou minimiser le retard moyen).
- L'Agent B (Tâches de fond / Best-Effort) : Il représente des calculs asynchrones et flexibles (ex : sauvegardes massives, entraînement de modèles d'IA). Son SLA prend la forme d'un seuil de tolérance à ne pas franchir (par exemple, garantir qu'un certain quota de tâches respecte les délais, ou limiter la dégradation globale du service).

Les travaux de cette thèse s'articuleront autour de trois axes de recherche principaux :

Axe 1 : Fondements théoriques et résolution exacte d'une classe de problèmes multi-agents
Ce premier axe établit le socle mathématique de la thèse en se concentrant sur la modélisation et la résolution d'une famille de problèmes de partage de ressources sur machine unique. L'objectif est d'analyser la complexité théorique de différentes combinaisons de critères (optimisation de la synchronisation de l'Agent A sous contrainte du SLA de l'Agent B) et de développer des algorithmes exacts (programmation linéaire, séparation et évaluation). Ces travaux permettront d'obtenir des solutions exactes sur des instances de taille modérée, servant de base de référence absolue pour évaluer toutes les méthodes futures.

Axe 2 : Algorithmique avancée et passage à l'échelle pour le Cloud
Ce deuxième axe vise à surmonter les limites de temps de calcul pour répondre aux exigences de rapidité du Cloud Computing, où l'orchestrateur doit gérer des milliers de requêtes instantanément. Il s'agira de concevoir des heuristiques de décision très rapides et des métaheuristiques performantes (comme les algorithmes génétiques ou la recherche locale) capables de traiter de très grands volumes de tâches. L'enjeu est de trouver rapidement d'excellentes solutions d'ordonnancement qui respectent strictement le seuil de tolérance de l'Agent B tout en optimisant au mieux les performances de l'Agent A.

Axe 3 : Généralisation aux architectures distribuées et dynamiques
Le dernier axe a pour but de rapprocher les modèles mathématiques de la réalité complexe des centres de données modernes en relâchant les hypothèses simplificatrices initiales. D'une part, les algorithmes développés seront adaptés pour fonctionner non plus sur un serveur unique, mais sur des architectures distribuées (grappes de serveurs ou machines virtuelles en parallèle). D'autre part, la dimension dynamique du Cloud sera intégrée afin de gérer l'arrivée continue et imprévisible de nouvelles requêtes en temps réel.
Cette thèse s'inscrit en Recherche Opérationnelle et Optimisation Combinatoire, spécifiquement dans la théorie de l'ordonnancement multi-agents. Avec l'émergence des architectures mutualisées (Cloud/Edge), l'ordonnancement classique évolue pour allouer les ressources entre des entités aux exigences conflictuelles (contrats SLA). Ces contraintes inter-agents engendrent de nouveaux problèmes NP-difficiles, soulevant trois défis majeurs : (1) Complexité théorique : Établir la frontière de difficulté mathématique des modèles ; (2) Modélisation : Traduire rigoureusement les contrats SLA en Programmation Linéaire (PLNE) ; (3) Algorithmique : Développer des méthodes exactes (garantie d'optimalité) et approchées (passage à l'échelle industriel). L'enjeu central de la thèse est d'étudier et de résoudre ce problème d'optimisation sous contrainte. Les travaux se concentreront sur l'analyse de la complexité théorique et le développement d'algorithmes (exacts et heuristiques). Le but sera d'élaborer des méthodes capables de trouver la séquence d'exécution optimale qui minimise l'écart temporel des tâches de l'Agent A par rapport à leur échéance, tout en garantissant strictement que le quota de dépassements toléré par l'Agent B ne sera pas franchi.

Le candidat retenu doit
- Être titulaire d'un diplôme de master en recherche opérationnelle, en informatique, en mathématiques appliquées ou dans tout autre domaine connexe.
- Avoir de bonnes connaissances en algorithmique (optimisation combinatoire, algorithmes exacts et approchés, l'analyse des algorithmes).