Supervision : Claire HANEN

Parameterized complexity and efficient enumerative schemes for the RCPSP

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é.
Peu de résultats ont été publiés à ce jour dans le domaine de l'ordonnancement; la majorité des résultats obtenus concernent des problèmes d'optimisation combinatoires sur les graphes. La thèse aura en premier lieu pour objectif de développer si cela est possible de nouveaux algorithmes paramétrés, et dans le cas contraire, de démontrer qu'il n'en n'existe pas pour ce paramètre à moins que P=NP. Il s'agira alors de faire émerger une cartographie de la complexité paramétrée pour les problèmes d'ordonnancement issus du RCPSP.
Au delà d'algorithmes énumératifs visant à montrer l'existence d'algorithmes FPT, le second objectif de la thèse visera à concevoir des algorithmes efficaces en pratique fondés sur ces nouveaux paradigmes.

2022 Publications

• 2022
  • M. Mallem, C. Hanen, A. Munier‑Kordon : “Scheduling coupled tasks with time windows: a parameterized complexity analysis”, (2022)
  • M. Mallem, C. Hanen, A. Munier Kordon : “Parameterized complexity of a parallel machine scheduling problem”, International Symposium on Parameterized and Exact Computation (IPEC), Postdam, Germany (2022)
  • C. Hanen, M. Mallem, A. Munier‑Kordon : “Parameterized Complexity of Single-machine Scheduling with Precedence, Release Dates and Deadlines”, Models and Algorithms for Planning and Scheduling, Biella, Italy (2022)
  • M. Mallem : “Parameterized complexity of a single machine scheduling problem”, 23^e congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Villeurbanne - Lyon, France (2022)