Stage de Master M2 au LIP6 : Etude et implémentation d'un algorithme de complexité paramétrée pour

1 Descriptif du stage

On considère le problème d’ordonnancement classique P |Mj (type), prec, ri, di|? défini par un ensemble de tâches de durée quelconque et des contraintes de précédence. On dispose de κ classes de machines  C?1,...,C?κ, chaque classe C?p possède mp machines identiques. Chaque tâche i doit être effectuée sur l’une des machines d’une classe prédéterminée C?τ. Chaque tâche i possède un date d’échéance di et une date de disponibilité ri. Le problème consiste à déterminer si il existe un ordonnancement réalisable, et à le construire le cas échéant.

Ce problème est NP-difficile, y compris dans le cas où les tâches sont de durée 1 [2]. Sa résolution par un algorithme exact permet de résoudre par dichotomie les problèmes P |Mj (type), prec, ri, di|Cmax et P |Mj (type), prec, ri|Lmax. Les critères de ces deux problèmes d’optimisation sont respectivement la durée maximale (Cmax) et retard algébrique maximal (Lmax).

L’émergence, depuis le début des années 2000, de la complexité paramétrée [1] avec un nombre croissant de 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 qui est résolvable par un algorithme de complexité paramétrée est dit « Fixed-Parameter Tractable »(FPT) pour ce paramètre.

Claire Hanen et Alix Munier Kordon ont développé un algorithme de complexité paramétrée pour les problèmes d’ordonnancement considérés ci-dessus [3]. Les paramètres considérés sont la largeur chemin (pathwidth) du graphe d’intervalle associé aux intervalles [ri, di] des tâches et la durée maximale d’une tâche. Le but de cet algorithme était d’établir que ces problèmes étaient FPT pour ces deux paramètres pris simultanément. Son implémentantion est l’occasion de réduire si possible sa complexité. Une piste d’accélération est d’y intégrer des propriétés élémentaires de dominance.

Le but du stage est de réaliser dans un premier temps l’implémentation de l’algorithme paramétré tel qu’il est décrit dans l’article [3]. Il s’agira ensuite d’y intégrer des méthodes de reduction de la largeur chemin et d’implémenter des méthodes de dominance permettant de réduire le nombre de solutions énumérées. On s’intéressera aux cas particuliers du problème (machines parallèles, machines spécialisées) permettant d’analyser le comportement de l’algorithme dans ces cas, et le cas échéant de proposer des améliorations spécifiques.

2 Conditions du stage

Le stage aura lieu en 2021 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 de l’ordre 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] 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.

[2] Michael R. Garey and David S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman and Company, 1979.

[3] Claire Hanen and Alix Munier Kordon. Fixed parameter tractability of building schedules of dependent typed tasks subject to release times and deadlines. Technical report.