Description
Date depot: 6 avril 2021
Titre: Complexité paramétrée et nouveaux schémas énumératifs efficaces pour le RCPSP
Directrice de thèse:
Claire HANEN (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Aide à la décision et recherche opérationnelle
Resumé: Cette thèse est consacrée à la complexité paramétrée du problème d'ordonnancement RCPSP (Resource constrained scheduling problem) et de ses sous-problèmes.
L'étude de la complexité paramétrée de problèmes combinatoires permet de comprendre comment certains paramètres spécifiques à chaque problème influencent sa complexité et peut déboucher sur des algorithmes exacts efficaces lorsque les paramètres sont bornés.
La thèse aura en premier lieu pour objectif d'étudier la pertinence de différents paramètres. On développera pour chacun si cela est possible de nouveaux algorithmes paramétrés (Fixed Parameter Tractable), ou dans le cas contraire, on démontrera qu'il n'en n'existe pas pour ce paramètre à moins que P=NP. Il s'agit donc de faire émerger une cartographie de la complexité paramétrée pour les problèmes d'ordonnancement issus du RCPSP, encore peu étudiée jusqu'à présent.
Au delà d'algorithmes énumératifs visant à montrer l'existence d'algorithmes FPT, le second objectif de la thèse sera de concevoir des algorithmes efficaces en pratique fondés sur ces nouveaux paradigmes, ce qui constitue une direction prometteuse pour l'ordonnancement en général. Il s'agira en particulier d'étudier l'intégration de techniques déjà éprouvées pour concevoir de bonnes méthodes exactes (dominances, décomposition, relaxations, bornes) et de les tester sur des jeux d'essais de référence.
Résumé dans une autre langue: This PhD resarch project focuses on the parameterized complexity of the RCPSP (Resource constrained scheduling problem) and its sub-problems.
The study of the parameterized complexity of combinatorial problems allows us to understand how specific parameters influence their complexity. It can lead to efficient exact algorithms if the parameters are bounded. The first objective of the resarch project will be to study the relevance of different parameters, either by developing new Fixed parameter tractable algorithms (FPT) or by proving that none exist for this parameter unless P=NP. Our goal is to develop a cartography of parameterized complexity for RCPSP and its sub-problems.
Beyond enumerative algorithms aiming at showing the existence of FPT algorithms, the second objective of the PhD resarch project will be to design efficient algorithms based on these new paradigms, which is a promising direction for scheduling in general. In particular, the integration of already proven techniques to design good exact methods (dominance, decomposition, relaxations, bounds) will be studied and tested on reference benchmarks.
Doctorant.e: Mallem Maher