Site Web de GILLES SIMONIN
Recherche
Les travaux effectués durant ma thèse portent sur l'étude de la complexité et de l'approximation des problèmes d'ordonnancement en présence de tâches-couplées sur un mono-processeur. Ces problèmes sont motivés par la modélisation d'un problème de robotique portant sur une torpille sous-marine d'exploration. Cette torpille a pour objectif d'exécuter deux types de tâches : celles d'acquisition et celles de traitement. Les tâches d'acquisition sont semblables à des tâches-couplées, et les tâches de traitement sont des tâches classiques. La torpille utilise différents capteurs pour réaliser les acquisitions, certains capteurs ne peuvent pas être utilisés en même temps pour cause d'interférences. Nous introduisons donc un graphe de compatibilité permettant de représenter les tâches d'acquisition pouvant avoir leurs exécutions qui se chevauchent. La torpille possède un monoprocesseur embarqué permettant d'exécuter toutes la tâches.
La première partie de mes travaux s'intéressait à la modélisation du problème, aux différentes tâches utilisées et aux contraintes qui leur sont appliquées. L'impact de la contrainte de compatibilité a été mis en avant, m'amenant à utiliser la théorie des graphes pour analyser les problèmes. Dans une seconde partie, j'ai donné la classification des problèmes possibles en faisant varier les paramètres des tâches-couplées. Plusieurs preuves de complexité ont été données pour certains problèmes se trouvant à la limite entre la polynomialité et la NP-complétude selon les valeurs des paramètres. Pour chaque problème NP-complet, des algorithmes d'approximation en temps polynomial ont été proposés, ainsi que l'analyse des bornes obtenues selon les paramètres ou les topologies du graphe de compatibilité. L'ensemble des résultats est décomposé en trois chapitres dans ma thèse prenant chacun en compte l'introduction d'une contrainte (d'incompatibilité et/ou de précédence). Tout au long de cette partie j'ai cherchais à montrer l'impact de l'introduction de la contrainte d'incompatibilité sur la complexité des problèmes d'ordonnancement avec tâches-couplées, à travers les preuves de NP-complétude et les techniques employées pour résoudre ou approximer un problème.
J'ai abordé le problème de la torpille d'un point de vue plus pratique en cherchant à réaliser une étude stochastique. Le modèle était le suivant : Les tâches d'acquisition et de traitement sont envoyées à la torpille à la volée suivant une loi de distribution. Les paquets de tâches reçus doivent être traité dans un laps de temps donné avant d'être re-exécuté de manière périodique. Lorsque un paquet de tâches n'est pas exécuté dans les temps, la torpille retire le paquet et continue à ordonnancer les autres. Le travail a été de modéliser le problème puis de proposer différentes règles de priorité à suivre pour obtenir différents ordonnancements. Des simulations ont été réalisées, et un papier a été publié à la ROADEF 2009.
J'ai également abordé l'étude en régime permanent portant sur le problème de la torpille. Le premier travail a été de modéliser le problème de la torpille, prenant en compte la structure particulière des tâches d'acquisition et la préemtivité des tâches de traitement. Ces travaux sont en collaboration avec Jean-François Pineau qui fait un postdoc au lirmm.
Enfin, certains résultats en théorie des graphes, sur le recouvrement de sommets par des chaînes disjointes de longueur inférieure à 2, ont abouti sur une collaboration avec Jean Daligault et Stéphan Thomassé sur les problèmes de star packing et les K-crowns. Un papier est en cours d'élaboration.
