Thèse Ordonnancement Robuste avec Information Partielle Structurée H/F - Doctorat.Gouv.Fr

Établissement : Université Marie et Louis Pasteur École doctorale : SPIM - Sciences Physiques pour l'Ingénieur et Microtechniques Laboratoire de recherche : Franche Comté Electronique Mécanique Thermique et Optique - Sciences et Technologies Direction de la thèse : Laurent PHILIPPE ORCID 0000000338254594 Début de la thèse : 2026-10-01 Date limite de candidature : 2026-05-24T23:59:59 Les problèmes d'ordonnancement occupent une place centrale en algorithmique et en recherche opérationnelle, avec des applications allant du calcul parallèle à la gestion de systèmes distribués. Les modèles classiques supposent généralement une connaissance complète des paramètres d'entrée (par exemple les temps de traitement), hypothèse rarement satisfaite en pratique.

À l'inverse, des modèles extrêmes comme l'ordonnancement non-clairvoyant négligent toute information préalable. Entre ces deux extrêmes, des travaux récents s'intéressent à l'intégration de prédictions issues de modèles d'apprentissage automatique dans la conception d'algorithmes. Toutefois, ces approches reposent souvent sur des modèles simplifiés des erreurs (oracle de type boîte noire, erreur globale), qui capturent mal leur structure réelle.

Nous proposons d'explorer un cadre basé sur des prédictions structurées sous forme de classes, permettant de représenter les erreurs via des matrices de confusion. Ce cadre ouvre des perspectives intéressantes pour relier structure des erreurs et performance algorithmique, puisque la structure de telles matrices permet de modéliser directement le comportement du modèle de classification (e.g., sous/sur-estimateurs, confusion de paires de classes, etc.)

L'objectif général est d'étudier des problèmes d'ordonnancement en présence d'informations partielles issues de prédictions imparfaites, et de concevoir des algorithmes robustes exploitant explicitement la structure des erreurs.

Un axe central de la thèse consiste à considérer des prédictions sous forme de classification et à modéliser leurs erreurs via une matrice de confusion. L'objectif est d'étudier comment une telle information peut être exploitée dans la conception d'algorithmes d'ordonnancement, en analysant dans quelle mesure cette matrice peut être connue, estimée ou apprise, et si sa structure peut être influencée afin de mieux distinguer certaines tâches critiques. Plus généralement, il s'agit de comprendre comment la structure des erreurs, au-delà de leur simple amplitude, impacte les performances algorithmiques et peut contribuer à la conception de méthodes robustes.

Ce positionnement constitue le coeur de la thèse. Néanmoins, d'autres formes de modélisation de l'incertitude pourront être considérées si elles s'avèrent pertinentes, afin de comparer différents cadres (intervalles, scénarios, modèles hybrides) et mieux situer l'apport du modèle étudié.

Sur cette base, la thèse vise à concevoir des algorithmes d'ordonnancement exploitant l'information structurée disponible, et à en analyser les performances selon différents critères (pire cas, moyenne, min-max regret, ou d'autres critères plus spécifiques). Une attention particulière sera portée au lien entre la structure de la matrice de confusion et les garanties obtenues, ainsi qu'à l'identification de situations où une information partielle mais structurée permet des gains significatifs.

Enfin, un objectif important est de mieux comprendre l'interaction entre apprentissage et décision. Il s'agira notamment d'évaluer le rôle réel de la précision des modèles, d'identifier d'éventuelles structures d'erreurs plus favorables que d'autres, et d'étudier dans quelle mesure l'apprentissage peut être orienté vers des objectifs pertinents pour l'ordonnancement. Ordonnancement avec prédiction Relier structure d'erreur et performance algorithmique Optimisation robuste (étude des problèmes min-max, min-max regret )

Les personnes candidates devront avoir :
- une solide formation en algorithmique, optimisation ou recherche opérationnelle ;
- un intérêt pour les aspects théoriques (preuves, analyse d'algorithmes) ;
- idéalement, une ouverture vers les problématiques liées à l'apprentissage automatique.

Une grande rigueur, d'autonomie, de la curiosité scientifique, ainsi qu'une capacité à travailler en équipe sont également attendues.