Les gestionnaires de ressources reposant sur une gestion dynamique des tâches permettent une utilisation efficace des ressources des grappes de serveurs. Ils mettent en oeuvre pour cela des mécanismes manipulant à la volée l'état des tâches et leur placement sur les différents noeuds de la grappe. En pratique, ces stratégies d'ordonnancement ad-hoc s'adaptent difficilement aux grappes. En effet, celles-ci ne permettent pas nécessairement une manipulation fiable des tâches et peuvent imposer des contraintes d'ordonnancement spécifiques. Dans cette thèse, nous nous sommes fixés comme objectif de faciliter le développement de gestionnaires de ressources basés sur une gestion dynamique des tâches. Pour cela, nous avons retenu une architecture à base de machines virtuelles qui exécutent les tâches des utilisateurs dans leur propre environnement logiciel tout en proposant les primitives nécessaires à la manipulation de celles-ci de manière non-intrusive. Nous avons également proposé une approche autonome optimisant en continu l'ordonnancement des tâches. Les stratégies d'ordonnancement sont implémentées au moyen de la programmation par contraintes qui permet de définir de manière flexible des problèmes d'ordonnancement et de les résoudre. Nous avons validé notre approche par le développement et l'évaluation du prototype Entropy, support pour l'implémentation de différentes stratégies d'ordonnancement. Celles-ci ont pu répondre efficacement à des problèmes concrets et actuels.

En août 2005, British Airways mit quatre jours à rétablir ses vols après une grève d'une journée d'un de ses sous-traitants. En interconnectant et intégrant leurs systèmes d'aide à la décision, les entreprises deviennent de plus en plus soumises aux changements. Parallèlement, avec le développement de technologies comme les puces RFID et la localisation par GPS les entreprises sont capables de suivre en temps réel le déroulement des opérations sur le terrain. Dans cette thèse nous nous intéressons au cas des problèmes de satisfaction de contraintes dans un cadre dynamique. En effet, depuis de nombreuses années la programmation par contraintes a fait la preuve de son efficacité pour résoudre des problèmes d'optimisation (tournées de véhicules, ordonnancements, etc) dans le cadre statique. Cependant le contexte dynamique soulève encore de nombreuses difficultés. Nous proposons donc un ensemble d'outils permettant la gestion et la prise en compte des événements, survenant de manière inattendue, dans le cadre de la programmation par contraintes. Chaque outil repose sur une approche particulière des problèmes dynamiques (tuples interdits, recherche locale, explications) et offre ainsi un éclairage différent et complémentaire.

Résoudre un problème d'ordonnancement consiste à organiser un ensemble de tâches, c'est-à-dire déterminer leurs dates de début et de fin et leur attribuer des ressources en respectant certaines contraintes. Dans cette thèse, nous proposons de nouvelles approches exactes basées sur la programmation par contraintes pour deux classes de problèmes d'ordonnancement NP-difficiles validées expérimentalement par l'implémentation d'un ensemble de nouvelles fonctionnalités dans le solveur de contraintes choco. Dans un problème d'atelier, n lots sont constitués chacun de m tâches à exécuter sur m machines distinctes. Chaque machine ne peut exécuter qu'une tâche à la fois. La nature des contraintes liant les tâches d'un même lot peut varier (séquencement global ou par lot, pas de séquencement). Le critère d'optimalité étudié est la minimisation du délai total. Nous proposons d'abord une étude et une classification des différents modèles et algorithmes de résolution. Ensuite, nous introduisons une nouvelle approche flexible pour ces problèmes classiques. Une machine à traitement par fournées peut traiter plusieurs tâches en une seule opération, une fournée. Les dates de début et de fin des tâches d'une même fournée sont identiques. Le problème étudié consiste à minimiser le retard algébrique maximal de n tâches de différentes tailles sur une machine de capacité b. Conjointement, la somme des tailles des tâches d'une fournée ne doit pas excéder la capacité b. Nous proposons, dans ce contexte, un modèle basé sur une décomposition du problème. Nous définissons ensuite une nouvelle contrainte pour l'optimisation basée sur une relaxation du problème qui améliore sa résolution.

La programmation par contraintes est une approche intéressante pour traiter des problèmes d'ordonnancement. En ordonnancement cumulatif, les activités sont définies par leur date de début, leur durée et la quantité de ressource nécessaire à leur exécution. La ressource totale disponible (la capacité) en chaque instant est fixe. La contrainte globale Cumulative modélise ce problème en programmation par contraintes. Dans de nombreux cas pratiques, la date limite de fin d'un projet est fixée et ne peut être retardée. Dans ce cas, il n'est pas toujours possible de trouver un ordonnancement des activités qui n'engendre aucun dépassement de la capacité en ressource. On peut alors tolérer de relâcher la contrainte de capacité, dans une limite raisonnable, pour obtenir une solution. Nous proposons une nouvelle contrainte globale : la contrainte SoftCumulative qui étend la contrainte Cumulative pour prendre en compte ces dépassements de capacité. Nous illustrons son pouvoir de modélisation sur plusieurs problèmes pratiques, et présentons différents algorithmes de filtrage. Nous adaptons notamment les algorithmes de balayage et d'Edge-Finding à la contrainte SoftCumulative. Nous montrons également que certains problèmes pratiques nécessitent d'imposer des violations de capacité pour satisfaire des règles métiers, modélisées par des contraintes additionnelles. Nous présentons une procédure de filtrage originale pour traiter ces dépassements imposés. Nous complétons notre étude par une approche par décomposition. Enfin, nous testons et validons nos différentes techniques de résolution par une série d'expériences.

La programmation par contraintes, carrefour de diverses disciplines, a montré son intérêt dans de nombreux domaines d'application. De nombreux problèmes réels sont dynamiques : le système de contraintes les définissant n'est donc pas figé. Pour résoudre un problème dynamique, il faut assurer une certaine incrémentalité et être capable de traiter les systèmes de contraintes contradictoires. En effet, il est souvent indispensable de fournir une solution quitte à ne pas respecter certaines contraintes. On parle alors de relaxation de contraintes.<br /><br />Durant cette thèse, nous nous sommes intéressés à la définition d'un système de relaxation de contraintes permettant de maintenir une propriété donnée dans un environnement dynamique. Nous avons mené ces travaux depuis une présentation abstraite d'un tel système jusqu'à son implémentation.<br /><br />Nous présentons un schéma algorithmique général abstrait de la recherche d'une solution à un problème sur-contraint basée sur l'exploration en meilleur d'abord d'un espace de configurations. Nous en donnons trois instances pour traiter les contraintes linéaires sur les rationnels, les Constraint Satisfaction Problems et les CSP numériques. Les deux dernières sont définies à l'aide d'un système de maintien de déduction dont la ma\^\itrise raisonnée nous a permis de donner une implémentation de ces instances ayant une bonne complexité : le système DECorum.<br /><br />Nous montrons, par le biais d'un certain nombre d'expérimentations, que l'utilisation de DECorum permet de retrouver les résultats classiques sur la transition de phase, de résoudre raisonnablement des problèmes de grande taille et d'utiliser la structure du problème résolu pour améliorer la recherche.<br /><br />Enfin, nous proposons la contrainte one-of permettant de modéliser et de résoudre une disjonction de contraintes en tirant profit du mécanisme d'exploration de DECorum. Nous validons l'intérêt de la contrainte one-of sur des problèmes d'ordonnancement : les Open-Shop.

Dans le cadre de cette thèse, nous nous intéressons à l'acquisition automatique de réseau de contraintes, aussi appelée apprentissage automatique de réseau de contraintes, qui consiste à développer des solutions capables d'aider un utilisateur à modéliser un problème combinatoire sous la forme d'un réseau de contraintes. Notre travail se focalise plus précisément sur la plate-forme d'acquisition automatique de réseau de contraintes CONACQ. Dans son implémentation standard, CONACQ est passive vis-à-vis de l'utilisateur, c'est-à-dire basée sur la capacité de ce dernier à fournir des instances significatives de son problème. Dans la première partie de cette thèse, nous proposons une version interactive de CONACQ, capable de poser à l'utilisateur des questions dont le but est d'augmenter plus rapidement et de manière conséquente la connaissance acquise par la plate-forme. Afin de limiter le nombre d'interactions, nous proposons différentes stratégies de questionnement que nous validons ensuite empiriquement. Dans la seconde partie, nous nous intéressons à une utilisation pratique de l'acquisition automatique de réseau de contraintes qui vise à automatiser le processus de définitions de comportements sensorimoteurs en robotique. Dans cette optique, nous proposons une architecture logicielle, complémentaire aux architectures de contrôle existantes, qui utilise le paradigme de la programmation par contraintes pour modéliser, planifier et superviser l'exécution de comportements sensorimoteurs. Elle utilise la plate-forme CONACQ étudiée dans la première partie de cette thèse pour modéliser automatiquement les actions élémentaires d'un robot sous la forme de réseaux de contraintes. Notre architecture utilise par ailleurs un planificateur de tâches inspiré de CSP-Plan pour combiner les réseaux de contraintes acquis et ainsi définir automatiquement des comportements sensorimoteurs. Différents résultats expérimentaux sont par ailleurs présentés afin de valider notre approche.

La programmation par contraintes est un sujet de recherche qui tire profit de nombreuses autres disciplines : mathématiques discrètes, analyse numérique, intelligence artificielle, recherche opérationnelle et calcul formel. Elle a prouvé son intérêt et son efficacité dans de nombreux domaines : optimisation combinatoire, ordonnancement, finance, simulation et synthèse de composants, diagnostic de panne, biologie moléculaire, ou encore problèmes géométriques. Néanmoins, un certain nombre de limitations et de difficultés ont été identifiées dans le domaine : conception d'algorithmes génériques et stables, traitement des problèmes dynamiques, accessibilité des concepts et des outils, ...<br /><br />Dans ce document, nous plaidons pour l'utilisation de la notion d'explication au sein de la programmation par contraintes. Notre but est double : non seulement présenter un tableau général des explications (définition, génération et utilisations) mais aussi montrer comment leur utilisation permet de contribuer à lever certains des problèmes ouverts en programmation par contraintes. Nous présentons aussi une démarche générale de résolution de problème dans un environnement expliqué. Enfin, nous montrons comment ce nouveau sujet semble promis à un bel avenir.

Cette thèse s'inscrit dans le cadre de la programmation par contraintes quantifiées, un formalisme étendantla programmation par contraintes classique en ajoutant aux variables des quantificateurs existentiels ouuniversels, ce qui apporte en théorie une expressivité suffisante pour modéliser des problèmes avec adversaireou incertitude sur certains paramètres sous forme de problèmes appelés QCSP (Quantified Constraintsatisfaction Problem).Nous commençons par apporter une réponse aux difficultés de modélisation de problèmes réels dont estfrappée la programmation par contraintes quantifiées en introduisant une extension aux QCSP permettantd'expliciter les actions possibles de l'agent principal et de son adversaire. Puis, nous décrivons différentproblèmes grâce à ce formalisme, et discutons de la place de cette extension parmi les formalismes voisins créésen réponse à cette même difficulté de modélisation. Enfin, nous nous intéressons à la notion d'optimisationdans le cas des contraintes quantifiées, et apportons un formalisme d'optimisation de contraintes quantifiéespermettant d'exprimer des problèmes multi-niveaux non linéaires.

La vérification de programmes avec des calculs sur les nombres à virgule flottante est une étape très importante dans le développement de logiciels critiques. Les calculs sur les nombres flottants sont généralement imprécis, et peuvent dans certains cas diverger par rapport au résultat attendu sur les nombres réels. L'objectif de cette thèse est de concevoir un solveur de contraintes sur les nombres à virgule flottante dédié à la vérification de programmes. Nous présentons dans ce manuscrit une nouvelle méthode de résolution de contraintes sur les flottants. Cette méthode se base principalement sur la sur-approximation des contraintes sur les flottants par des contraintes sur les réels. Cette sur-approximation doit être conservative des solutions sur les flottants. Les contraintes obtenues sont ensuite résolues par un solveur de contraintes sur les réels. Nous avons proposé un algorithme de filtrage des domaines sur les flottants basé sur le concept de la sur-approximation qui utilise des techniques de programmation linéaire. Nous avons aussi proposé une méthode de recherche de solutions basée sur des heuristiques. Cette méthode offre aussi la possibilité de comparer le comportement des programmes par rapport à une spécification sur les réels. Ces méthodes ont été implémentées et expérimentées sur un ensemble de programmes avec du calcul sur les nombres flottants.

Th. doct.--Informatique--Grenoble 1, 1995. / Bibliogr. p. 285-295. Résumé en anglais et en français. 1996 d'après la déclaration de dépôt légal.