Informations générales : Ce sujet sera hébergé au sein de l’équipe Systèmes Logistiques et de Production (SLP) et fera l’objet d’une collaboration avec l’équipe Modélisation et Gestion Intégrée des Systèmes d’Activités (MOGISA) du Laboratoire d’Architecture et d’Analyse des Systèmes (LAAS) à Toulouse. Les encadrants seront :
– à Nantes : Odile Bellenguez-Morineau (Chargée de recherche à l’Ecole
des Mines de Nantes) et Damien Prot (Maître Assistant Associé à
l’Ecole des Mines de Nantes), joignables aux adresses suivantes :
odile.morineau_at_mines-nantes.fr et damien.prot_at_mines-nantes.fr
– à Toulouse : Christian Artigues (Directeur de Recherche au CNRS) et
Julien Moncel (Maître de Conférences à l’Université Toulouse 1 Capitole),
joignables aux adresses suivantes :
christian.artigues_at_laas.fr et julien.moncel_at_laas.fr.
Ce stage pourra se poursuivre par une thèse, dont le financement est en
cours de demande.
Contexte : Les techniques de décomposition de graphes (comme par exemple la décomposition modulaire, la split decomposition, la décomposition arborescente, etc.) relèvent toutes d’un même principe, connu sous le nom de diviser pour régner. L’idée est de décomposer une (grande) structure en (petites) sous-structures, sur lesquelles il sera plus facile de résoudre un problème donné. L’intérêt de ces techniques de décomposition réside dans le fait que, pour certains problèmes qui sont difficiles en général, il est possible de les résoudre efficacement lorsque les graphes concernés admettent une “bonne" décomposition.
C’est notamment le cas en ordonnancement, où l’on doit fréquemment
tenir compte de contraintes de précédence, modélisées le plus souvent par un graphe acyclique orienté. Dans ce cadre, certains problèmes difficiles en général deviennent faciles dès lors que ce graphe de précédence a une “bonne” structure (typiquement un arbre, ou un graphe série-parallèle). Le problème de minimisation du critère
Ci (avec Ci = date de fin de la tâche i) sur
une machine (noté en général 1|prec|Ci) est ainsi NP-complet lorsque les tâches sont soumises à des contraintes de précédence quelconque, mais est polynomial dès lors que le le graphe des précédences est une arborescence ou un graphe série-parallèle [2].
Sujet du stage : Dans ce stage de M2R on s’intéresse à l’application d’un type particulier de décomposition, appelé décomposition arborescente. Ce type de décomposition date des années 1980 [3], et a fait l’objet d’un nombre important de travaux, notamment dans la communauté graphes et logique (voir par exemple le livre à paraître de B. Courcelle et J. Engelfriet [1]).
L’idée générale est de regrouper les sommets du graphe en “paquets”, de sorte à ce que la structure d’incidence entre ces “paquets” de sommets soit celle d’un arbre. L’objectif du stage est de comprendre le principe de d´ecomposition arborescente ainsi que les résultats de base sur le sujet, puis d’étudier l’application de cette technique de décomposition à des problèmes d’ordonnancement.
On pourra par exemple dans un premier temps s’intéresser à fournir
des preuves alternatives à des résultats connus (par exemple concernant 1|prec|Ci lorsque le graphe est un arbre ou un graphe série-parallèle), mais utilisant le principe de décomposition arborescente.
Références
[1] B. Courcelle et J. Engelfriet, Graph Structure and Monadic Second-
Order Logic, a Language Theoretic Approach, `a paraˆıtre chez Cambridge
University Press, disponible en ligne `a http://www.labri.fr/perso/
courcell/Book/TheBook.pdf
[2] E. L. Lawler, Sequencing jobs to minimize total weighted completion
time subject to precedence constraints, Annals of Discrete Mathematics
2 (1978), 75–90.
[3] N. Robertson, P. Seymour, Graph minors III : Planar tree-width, Journal
of Combinatorial Theory, Series B 36(1) (1984), 49–64.
2
