Description
Date depot: 6 avril 2023
Titre: Etude de la complexité paramétrée des problèmes d'ordonnancement avec grands temps de communication
Directrice de thèse:
Alix MUNIER (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é: On considère le problème d'ordonnancement à temps de communication défini par un ensemble de tâches de durée unitaire, des contraintes de précédence et des fenêtres de temps pour chacune des tâches, le tout à exécuter sur un ensemble de machines parallèles.
Lorsque deux tâches sont liées par une contrainte de précédence, si elles sont effectuées par la même machine, elles peuvent se succéder immédiatement;
mais si elles sont exécutées sur des machines différentes, un temps de communication fixé doit être ajouté entre l'exécution des deux tâches.
Le problème est alors de déterminer un ordonnancement réalisable, si cela est possible. Comme les temps de communications peuvent être supérieurs à la durée des tâches, on dit que ce problème est à grand temps de communication.
Le sujet de cette thèse porte sur l'étude de l'existence d'algorithmes paramétrés pour des problèmes à grands temps de communication definis précédemment. On observe que dans le cas de grands temps de communication, la structure des ordonnancements réalisables est complexe.
Il s'agit donc de caractériser des propriétés de dominance pertinentes qui vont permettre, lorsque c'est possible, une énumération efficace en vu de définir un algorithme FPT pour les paramètres considérés. Dans la négative, il s'agira de classer le problème dans les hiérarchies de la complexité paramétrée. On tâchera de caractériser la frontière entre problème FPT et problèmes plus complexes.