La ROADEF
La R.O.A.D
Evénements
Prix
Publications
Plus
Forums
Connexion
Livre blanc

Stage de M2 au LIP6 : Implémentation et performance d'un algorithme FPT pour un problème d'ordonnanc

Forum 'Stages' - Sujet créé le 2022-11-23 par Alix Munier


Descriptif du Stage  

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 cij doit être ajouté entre l'exécution des deux tâches.

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é [5]. 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'emergence, depuis le début des années 2000, de la complexité paramétrée [2] 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 dont la complexité 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 [6].

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|* [4]. 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 but du stage est d'étendre cet algorithme pour prendre en compte des temps de communication supérieurs à un pour un nombre limité ou illimité de machines parallèles. Pour cela, un second paramètre à considérer est la valeur maximale d'un temps de communication. Il s'agira dans un premier temps de
caractériser des propriétés de dominance pertinentes qui vont permettre uneénumération plus efficace.
L'algorithme devra être programmé et testé sur des instances générées aléatoirement.

Cette implémentation pourra s'appuyer sur les travaux réalisés dans le projet LIP6 2020  Comparaison
de deux algorithmes pour l'ajustement des dates d'échéance pour un problème d'ordonnancement à m
machines  sur la réduction des intervalles par pré-processing [3], mais aussi sur les dominances établies
dans le cadre du projet Emergence EASI, une collaboration en cours avec le laboratoire Heudiasyc de
l'UTC [7]. Ces travaux portent sur les problèmes P |prec, ri, di|* sans temps de communication, il convient donc d'étudier leur adaptation à ce contexte.

Enfin, les résultats algorithmiques et expérimentaux obtenus viendront à l'appui d'une future publication
en revue et/ou en conférence internationale.


Conditions du stage

Le stage aura lieu en 2023 au LIP6 sur le campus Pierre et Marie Curie (4 place Jussieu, 75252 Paris)
et sera co-encadré par Claire Hanen et Alix Munier Kordon pour une durée de 6 mois. La gratification
prévue est approximativement de 555 Euros par mois.

Le candidat recherché doit être en Master 2 de recherche opérationnelle, de mathématiques appliquées,
d'informatique ou uneécole d'ingénieur avec un cursus en informatique. Il doit avoir de solides connaissances en programmation et en algorithmique.

Pour postuler, envoyez par mail aux deux encadrantes Claire.Hanen@lip6.fr et Alix.Munier@lip6.fr un
CV avec au minimum les notes de M1 et de 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, Alix Munier Kordon, and Theo Pedersen. Two deadline reduction algorithms for sche-
duling dependent tasks on parallel processors. In Peter J. Stuckey, editor, Integration of Constraint
Programming, Artificial Intelligence, and Operations Research - 18th International Conference,
CPAIOR 2021, Vienna, Austria, July 5-8, 2021, Proceedings, volume 12735 of Lecture Notes in
Computer Science, pages 214–230. Springer, 2021.
[4] 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.
[5] 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.
[6] Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling : 15 open
problems. Computers and Operations Research, 100 :254 – 261, 2018.
[7] Istenc Tarhan, Jacques Carlier, Claire C. Hanen, Antoine Jouglet, and Alix Munier Kordon. Para-
metrized analysis of an enumerative algorithm for a parallel machine scheduling problem. working
paper or preprint, November 2022.