Ordonnancement robuste avec information partielle structurée // robust scheduling with partial and structured information

Topic description

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 cœur 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.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Scheduling problems play a central role in computer science and operations research, with applications ranging from parallel computing to the management of distributed systems. Classical models generally assume complete knowledge of input parameters (such as processing times), an assumption that is rarely met in practice.

Conversely, extreme models such as non-clairvoyant scheduling disregard any prior information. Between these two extremes, recent work has focused on integrating predictions from machine learning models into algorithm design. However, these approaches often rely on simplified error models (black-box oracles, global error), which poorly capture their actual structure.

We propose to explore a framework based on predictions structured as classes, allowing errors to be represented via confusion matrices. This framework opens up interesting avenues for linking error structure and algorithmic performance, since the structure of such matrices allows us to directly model the behavior of the classification model (e.g., under/over-estimators, class pair confusion, etc.).

The overall objective is to study scheduling problems in the presence of partial information derived from imperfect predictions, and to design robust algorithms that explicitly exploit the structure of the errors.

A central focus of the thesis is to consider predictions in the form of classifications and to model their errors using a confusion matrix. The goal is to investigate how such information can be leveraged in the design of scheduling algorithms, by analyzing to what extent this matrix can be known, estimated, or learned, and whether its structure can be influenced to better distinguish certain critical tasks. More generally, the aim is to understand how the structure of errors, beyond their simple magnitude, impacts algorithmic performance and can contribute to the design of robust methods.

This approach forms the core of the thesis. Nevertheless, other forms of uncertainty modeling may be considered if they prove relevant, in order to compare different frameworks (intervals, scenarios, hybrid models) and better situate the contribution of the model under study.

Based on this, the thesis aims to design scheduling algorithms that leverage available structured information and to analyze their performance according to various criteria (worst-case, average, min-max regret, or other more specific criteria). Particular attention will be paid to the relationship between the structure of the confusion matrix and the guarantees obtained, as well as to identifying situations where partial but structured information yields significant gains.

Finally, an important objective is to better understand the interaction between learning and decision-making. This will involve, in particular, evaluating the actual role of model accuracy, identifying potential error structures that are more favorable than others, and studying the extent to which learning can be directed toward objectives relevant to scheduling.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/10/

Funding category

Funding further details

Financement d'un établissement public Français