Stage de M2 au LIP6 : Implémentation et comparaison expérimentale d'un algorithme paramétré pour un

Descriptif du stage

On considère le problème d’ordonnancement classique P|prec,pi,SCT|Cmax défini par un ensemble de tâches T = {1, . . . , n} de durée pi, i ∈ T quelconque et des contraintes de précédence définies par un graphe sans circuit G = (T , A). Chaque arc (i, j) ∈ A est associé à un transfert de données de durée entière cij : si les tâches i et j sont exécutées sur des processeurs différents, une durée cij est nécessaire entre la fin de i et le démarrage de j pour transférer les données nécessaires à l’excécution de j. On dispose de plus de m machines identiques pour exécuter les tâches. D’autre part, on suppose que les temps de communication sont plus petits que la durée des tâches, soit mini∈T pi ≥ max(i,j)∈A cij. Le problème consiste alors à construire un ordonnancement réalisable de durée minimale. Rayward- Smith [3] a montré que ce problème d’optimisation est NP-difficile y compris pour des tâches et des durées de communication égaux à 1.

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.

Ning Tang et Alix Munier Kordon ont développé un algorithme de complexité paramétrée pour le problème P |prec, pi = 1, cij = 1|Cmax[4] pour lequel les temps de communication et les durées sont unitaires. Des intervalles de réalisation [ri,di] sont associées aux tâches, et le paramétre considéré est la largeur chemin (pathwidth) du graphe d’intervalle associé. Par la suite, Claire Hanen et Alix Munier Kordon ont étendu cette approche et développé un algorithme de complexité paramétrée pour le problème P |prec, pi, SCT |Cmax avec pour paramètre la largeur chemin et la durée maximale d’une tâche [2]. Le but de ces algorithmes étaient d’établir que ces problèmes étaient FPT pour la largeur chemin.

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 [2]. 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. L’algorithme obtenu sera alors comparé expérimentalement sur des instances générées aléatoirement avec d’autres approches exactes, comme par exemple la programmation linéaire en nombres entiers.

Conditions du stage

Le stage aura lieu en 2022 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] Claire Hanen and Alix Munier Kordon. Fixed parameter tractability of building schedules with small communication delays and limited resources. Technical report.

[3] Victor J. Rayward-Smith. Uet scheduling with unit interprocessor communication delays. Discrete Applied Mathematics, 18(1) :55 – 71, 1987.

[4] Ning Tang and Alix Munier Kordon. A fixed-parameter algorithm for scheduling unit dependent tasks with unit communication delays. In Euro-Par 2021, volume 12820 of Lecture Notes in Computer Science, pages 105–119. Springer, 2021.