Offre de thèse au LIP6 : Etude de la complexité paramétrée des problèmes d'ordonnancement avec gr

Directeur de la thèse : Alix Munier Kordon

Laboratoire et Equipe : LIP6, Architectures et Logiciels pour Syst\`emes Embarqu\'es sur Puce (ALSOC).

Description du sujet

On considère le problème d’ordonnancement à temps de communication P|prec, pi = 1, cij , ri, di|* défini par un ensemble de tâches de durée unitaire, des contraintes de précédence et des fenêtres de temps [ri, di] pour chacune des tâches, le tout à exécuter sur un ensemble de machines parallèles. Les contraintes de précédence modèlisent des transferts de données. 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 d’au moins ci,j 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.

Ce problème est N P-difficile, y compris quand les durées de communication cij = 1 et que le nombre de machines n’est pas limité [4]. Il fait partie de problèmes particulièrement difficiles pour lesquels aucun algorithme exact efficace n’a été proposé depuis de nombreuses années, malgré des applications très nombreuses. Sa résolution par un algorithme exact permet de plus de résoudre par dichotomie les problèmes avec pour critère la minimisation de la durée maximale Cmax ou le retard algébrique maximal Lmax. L’émergence, depuis le début des années 2000, de la complexité paramétrée [2] avec un nombre croissantde publications internationales sur ce thème a renouvelé la compréhension de la difficulté des problèmes d’optimisation combinatoire. Cette approche détermine des paramètres pertinents qui permettent de construire des algorithmes de complexité polynômiale lorsque la valeur du paramètre est fixée. Plus précisément la complexité d’un algorithme de complexité paramétrée est de la forme O(f (p) × P (n)) où n est la taille de l’instance, p son paramètre, P une fonction polynôme et f une fonction quelconque.
Un problème qu’on peut résoudre par un algorithme de complexité paramétrée est dit « Fixed-Parameter Tractable » (FPT) pour ce paramètre.

L’intérêt théorique de la complexité paramétrée pour sonder la complexité intrinsèque des problèmes combinatoires est évident. L’efficacité pratique des algorithmes qui en résultent demande à être travaillée, notamment dans le domaine de l’ordonnancement où peu d’algorithmes de complexité paramétrée existent [5] par rapport à d’autres domaines de l’optimisation combinatoire, notamment l’algorithmique des graphes. En effet, une communauté croissante de chercheurs en optimisation combinatoire revisitent les problèmes classiques pour déterminer si ces problèmes sont ou non FPT pour des paramètres à définir selon les problèmes.

Récemment, Claire Hanen et Alix Munier Kordon ont développé un algorithme FPT pour le problème sans délai de communication P |prec, ri, di|*[3]. Les deux paramètres considérés sont la durée maximale d’une tâche et le pathwidth qui correspond au nombre maximal de fenêtres de temps [ri, di] qui s’intersectent en un instant. Alix Munier Kordon et Ning Tang ont également développé un algorithme FPT pour le problème P |prec, pi = 1, cij = 1, ri, di|* avec des temps de communication unitaire [1] ; le paramètre considéré est ici aussi le pathwidth.?

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 P |prec, pi = 1, cij , ri, di|*. Les paramètres pressentis sont le pathwidth et la valeur maximale d’un temps de communication. Cependant, d’autres paramètres peuvent être étudiés. 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.

Profil du candidat et conditions de la thèse: 

Le candidat devra avoir de bonnes connaissances en Algorithmique et en programmation. Des notions de base en théorie de la complexité, et/ou en recherche opérationnelle sont vivement recommandées. La thèse doit se dérouler à partir de la rentrée 2023 au LIP6, 4 place Jussieu, 75252 Paris.

Pour candidater : envoyer par mail à Alix.Munier@lip6.fr une lettre de motivation, et vos bulletins de L3, M1 et M2.

Références
[1] Alix Munier Kordon and Ning Tang. A fixed-parameter algorithm for a unit-execution-time unit-
communication-time tasks scheduling problem with a limited number of identical processors.
RAIRO-Oper. Res., 56(5) :3777–3788, 2022.
[2] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk,
Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer Publishing Company,
Incorporated, 1st edition, 2015.
[3] Claire Hanen and Alix Munier Kordon. Fixed parameter tractability of building schedules with small
communication delays and limited resources. Journal of Scheduling, to be published, 2022.
[4] Han Hoogeveen, Jan Karel Lenstra, and Bart Veltman. Three, four, five, six, or the complexity of
scheduling with communication delays. Operations Research Letters, 16(3) :129 – 137, 1994.
[5] Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling : 15 open
problems. Computers and Operations Research, 100 :254 – 261, 2018.