Direction de recherche : Claire HANEN

Complexité Paramétrée et Nouveaux Schémas Énumératifs Efficaces pour le RCPSP

La plupart des problèmes d’ordonnancement sont fortement NP-difficiles et nécessitent des heuristiques élaborées pour être résolus en pratique. Bien que fournissant des résultats au court terme, ces approches expliquent rarement ce qui rend ces problèmes fondamentalement difficiles. Avoir cet éclairage pourrait mettre à jour des similitudes entre des problèmes apparemment distincts et faciliter les transferts de stratégie. Cela serait également utile dès lors que l’on souhaite enrichir un problème - par exemple en y ajoutant des relations de précédence, ou en passant de tâches de même durée à des tâches de durées arbitraires.
Pour acquérir une telle expertise, il est possible d’aller au-delà de la théorie classique de la complexité, et de se tourner vers la complexité paramétrée. Étant donné un problème P, on choisit un paramètre k reflétant une propriété de l’instance en entrée, par exemple son nombre de machines. En fonction du problème P et du paramètre k, soit on développe des algorithmes dits "fixed-parameter tractable" (c.-à-d. qui opèrent en temps f(k) x poly(n) avec f une fonction arbitraire), soit on montre que le problème reste difficile lorsque le paramètre est petit (typiquement via une réduction depuis un problème paramétré reconnu comme difficile, à la manière d’une preuve de NP-difficulté). L’ensemble des paramètres pour lesquels le problème P est "fixed-parameter tractable" peut alors être interprété comme un ”phénotype” : en le comparant à celui d’un autre problème P', on peut déduire si les deux problèmes ont l’air équivalents, si l’un est une généralisation de l’autre, ou s’ils sont difficiles pour des raisons distinctes.
Dans cette thèse, nous étudions la complexité paramétrée du problème d’ordonnancement de projet sous contrainte de ressources (RCPSP) et de ses sous-problèmes, possiblement augmentés de délais de précédence et de fenêtres temporelles pour les tâches. Pour les délais de précédence, nous étudions le paramètre l_max - c.-à-d. le valeur maximum de délai pouvant apparaitre dans l’entrée - dans le cas de délais minimum, exact et maximum. Pour ces trois types de délais nous montrons que, même à petit l_max, ordonnancer des tâches de durée unitaire sur une unique reste difficile, et ce même pour des durées de délai toutes identiques. Cela suggère de limiter une propriété supplémentaire dans le cas de problèmes avec délais de précédence.
À ce titre, nous proposons l’ajout de fenêtres temporelles pour les tâches afin d’élargir le panel de paramètres disponibles. Cela nous permet de considérer deux paramètres ayant récemment rencontré du succès dans la littérature : d’une part la marge ? - c.-à-d. la différence maximum entre la taille de fenêtre d’une tâche et la durée de celle-ci -, d’autre part la largeur de chemin µ - c.-à-d. le nombre maximum de fenêtres pouvant se chevaucher le long d’une même unité de temps. Nous introduisons également un nouveau paramètre, que nous appelons le niveau propre q, et qui indique le nombre maximum de fenêtres pouvant inclure strictement une même autre fenêtre le long de ses deux bornes. Vis-à-vis de ces paramètres, nous proposons plusieurs algorithmes "fixed-parameter tractable", et les complétons avec des preuves de difficulté paramétrée. Nous considérons également d’autres suggestions de paramètres pour proposer une vue d’ensemble plus complète de la complexité paramétrée du RCPSP et de ses sous-problèmes.

Publications 2022-2024

• 2024
  • M. Mallem : “Parameterized Complexity and New Efficient Enumerative Schemes for RCPSP”, soutenance de thèse, soutenance 11/10/2024, direction de recherche Hanen, Claire (2024)
  • M. Mallem, C. Hanen, A. Munier‑Kordon : “A New Structural Parameter on Single Machine Scheduling with Release Dates and Deadlines”, International Symposium on combinatorial optimization 2024, vol. 14594, Lecture Notes in Computer Science, Tenerife (Canaries), Spain, pp. 205-219, (Springer Nature Switzerland) (2024)
• 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)