Accueil > Manifestations > Thèses et HDR > Thèses > Arnaud Letort

Arnaud Letort

Directeur de thèse

Nicolas Beldiceanu

Résumé

La programmation par contraintes est une approche régulièrement utilisée pour résoudre des problèmes combinatoires d’origines diverses. Dans cette thèse nous nous focalisons sur les problèmes d’ordonnancement cumulatif. Un problème d’ordonnancement consiste à déterminer les dates de débuts et de fins d’un ensemble de tâches, tout en respectant certaines contraintes de capacité et de précédence. Les contraintes de capacité concernent aussi bien des contraintes cumulatives classiques où l’on restreint la somme des hauteurs des tâches intersectant un instant donné, que des contraintes cumulatives colorées où l’on restreint le nombre maximum de couleurs distinctes prises par les tâches.

Un des objectifs récemment identifiés pour la programmation par contraintes est de traiter des problèmes de grandes tailles, habituellement résolus à l’aide d’algorithmes dédiés et de métaheuristiques. Par exemple, l’utilisation croissante de centres de données virtualisés laisse apparaitre des problèmes d’ordonnancement et de placement multi-dimensionnels de plusieurs milliers de tâches.

Pour atteindre cet objectif, nous utilisons l’idée de balayage synchronisé considérant simultanément une conjonction de contraintes cumulative et des précédences, ce qui nous permet d’accélérer la convergence au point fixe. De plus, de ces algorithmes de filtrage nous dérivons des procédures gloutonnes qui peuvent être appelées à chaque noeud de l’arbre de recherche pour tenter de trouver plus rapidement une solution au problème. Cette approche permet de traiter des problèmes impliquant plus d’un million de tâches et 64 resources cumulatives.

Ces algorithmes ont été implémentés dans les solveurs de contraintes Choco et SICStus, et évalués sur divers problèmes de placement et d’ordonnancement.

Mots-clés : Programmation par contraintes, ordonnancement, cumulatif, passage à l’échelle, point fixe, contraintes de ressources multi-dimensionelles, balayage synchronisé.

Composition du jury :

  • Philippe BAPTISTE, Directeur de la stratégie, Ministère de l’Enseignement supérieur et de la Recherche, Rapporteur ;
  • Patrice BOIZUMAULT, Professeur, Université de Caen Basse-Normandie, Rapporteur ;
  • Claude JARD, Professeur, Université de Nantes, Examinateur ;
  • Laurent PERRON, Ingénieur, Google, Examinateur ;
  • Éric PINSON, Professeur, Université Catholique de l’Ouest, Examinateur ;
  • Nicolas BELDICEANU, Professeur, École des Mines de Nantes, Directeur de thèse

Dernière modification : lundi 21 octobre 2013