Accueil > Manifestations > Thèses et HDR > Thèses > Alban Derrien

Alban Derrien

Directeur de thèse

Nicolas Beldiceanu
Thierry Petit

Résumé

La programmation par contraintes est une approche régulièrement utilisée pour traiter des problèmes d’ordonnancement variés. Les problèmes d’ordonnancement cumulatifs représentent une classe de problèmes dans laquelle des tâches non morcelable peuvent être effectuées en parallèle. Ces problèmes apparaissent dans de nombreux contextes réels, tels que par exemple l’allocation de machines virtuelles ou l’ordonnancement de processus dans le "cloud", la gestion de personnel ou encore d’un port.
De nombreux mécanismes ont été adaptés et proposés en programmation par contraintes pour résoudre les problèmes d’ordonnancement.
Les différentes adaptations ont abouti à des raisonnements qui semblent a priori significativement distincts.
Dans cette thèse nous avons effectué une analyse détaillée des différents raisonnements, proposant à la fois une notation unifiée purement théorique
mais aussi des règles de dominance, permettant une amélioration significative du temps d’exécution d’algorithmes issus de l’état de l’art, pouvant aller jusqu’à un facteur sept. Nous proposons aussi un nouveau cadre de travail pour l’ordonnancement cumulatif robuste, permettant de trouver des solutions supportant qu’à tout moment une ou plusieurs tâches soit retardées, sans remise en cause de l’ordonnancement généré et en gardant une date de fin de projet satisfaisante. Dans ce cadre, nous proposons une adaptation d’un algorithme de l’état de l’art, Dynamic Sweep.

Composition du jury :

  • Claude-Guy QUIMPER, Professeur, Université de Laval, Quebec, Rapporteur
  • Pierre LOPEZ, Directeur de Recherche CNRS, Toulouse, Rapporteur
  • Xavier LORCA, Maitre-Assistant HdR, École des Mines de Nantes, Examinateur
  • Nicolas BELDICEANU, Professeur, École des Mines de Nantes, Directeur de thèse
  • Thierry PETIT, Affiliate associate professor, Worcester Polytechnic Institute, USA, Co-encadrant

Dernière modification : mercredi 18 novembre 2015