Description
Date depot: 3 janvier 2023
Titre: Aspects algorithmiques pour l’ancrage de décisions en optimisation sous incertitude
Directeur de thèse:
Bruno ESCOFFIER (LIP6)
Directrice de thèse:
Pascale BENDOTTI (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Algorithmique, combinatoire
Resumé: Il s'agit d'une thèse CIFRE en partenariat avec EDF.
Cette thèse est centrée sur l’optimisation de la gestion des ressources sous différentes hypothèses d’incertitude sur les données. Elle s’inscrit dans le cadre général de la robustesse, avec un focus particulier sur la recherche de solutions dites ancrées, en ce sens que leur date d'exécution est garantie malgré l'incertitude sur les données.
L’objectif premier de la thèse est d’étendre et d’adapter la notion et les méthodologies d’ancrage robuste à des problèmes d’ordonnancement plus généraux et plus complexes, afin de se rapprocher des applications opérationnelles.
Une première direction de recherche de la thèse consiste à considérer le cas de tâches dont la durée dépend de la date d’exécution. S’il ne s’agit pas de gestion de ressources dans toute sa généralité, avoir des tâches dont la durée dépend du temps permet de prendre en compte des contraintes dites de calendrier ou plus généralement une disponibilité variable dans le temps des ressources - en particulier des périodes d’indisponibilité. L’objectif est de voir dans quelle mesure les durées dépendant du temps peuvent être prises en compte dans le calcul de solutions ancrées. En particulier, on s’interrogera sur l’extension de l’approche développée dans le cas non dépendant du temps, et l’on étudiera des cas particuliers sous l’angle de la complexité et de la conception d’algorithmes approchés.
Une deuxième direction concerne l’étude du lissage de ressources (resource leveling), l’idée principale étant d’exprimer certains aspects liés aux ressources non pas comme des contraintes mais comme des éléments de la fonction objectif. Il s’agit alors d’optimiser la gestion des ressources. Le travail de thèse s’intéressera à l’étude du lissage de ressources pour des problèmes d’ordonnancement, point encore peu exploré dans la littérature malgré son intérêt applicatif, et à l’éventuel extension de l’ancrage-robuste à ces problèmes.
Une troisième direction concerne la prise en compte globale et explicite des ressources via l’étude du problème Resource-Constrained Project Scheduling Problem (RCPSP). Il s’agira d’intégrer les considérations précédentes - tâches de durée dépendant du temps et/ou lissage de ressources - dans le calcul de solution ancrées pour le RCPSP. La grande complexité du problème orientera probablement le travail de thèse vers des approches heuristiques pour la résolution effective du problème.
D’autres problèmes de planification peuvent bénéficier de l’ancrage de décisions, par exemple à EDF la planification de la production d’unités de production court-terme ou de l’arrêt des tranches nucléaires moyen-terme en management d’énergie. D’un point de vue plus générique, il apparaît que certaines incertitudes sont de nature à impacter la structure des problèmes, par exemple dans un réseau où un aléa peut conduire à la disparition d’arcs et/ou de noeuds ou à un changement de capacités. Pour faire face à ces aléas, le calcul de solutions robustes – et en particulier de solutions ancrées - est pertinent, dans les problèmes de connectivité dans les réseaux notamment, comme le problème de dépannage Enedis en cas de crise.
On cherchera dans ce travail de thèse à étendre la notion d’ancrage à des problèmes de conception de réseaux et/ou de connectivité dans les graphes. On étudiera la résolution algorithmique de ces problèmes: complexité, étude de cas polynomiaux pour les problèmes NP-difficiles, conception et analyse d’algorithmes approchés.
Parallèlement à ces études de nature essentiellement théorique, un objectif de la thèse sera d’implanter, tester et analyser les méthodes d’ancrage-robuste conçues précédemment. Ceci nécessitera notamment la création de benchmarks pertinents pour les applications considérées avec aussi bien des instances adaptées de la littérature, que des instances réalistes.
Doctorant.e: Brunod Indrigo Luca