La version classique du problème d'ordonnancement de projet à contraintes de ressources (RCPSP) consiste à trouver un ordonnancement, de durée minimale, des activités d'un projet entrant en compétition sur l'usage de ressources renouvelables, cumulatives et disponibles en quantité limité. <br />La réputation d'extrême difficulté du RCPSP a mené nombre de chercheurs à proposer de nouvelles méthodes de résolution exacte toujours plus performantes pour ce problème. Malgré cela, les instances de tailles réelles, qui se recontrent fréquemment, par exemple dans la gestion de production industrielle, sont encore loins d'être résolues optimalement. Il est donc intéressant, en combinant les acquis des travaux précédents, en particulier en programmation par contraintes (PPC) et en programmation linéaire (PL), de se pencher sur des méthodes exactes innovantes ou encore de développer des procédures d'évaluation par défaut, pour permettre une meilleure estimation de la performance des heuristiques sur le RCPSP. Ce travail de thèse entre dans ce cadre.<br /><br />Dans un premier temps, nous nous attachons au calcul de bornes inférieures pour le RCPSP par relaxation lagrangienne. D'une part, nous cherchons à accélerer le calcul de la borne de Brucker et Knust (obtenue par hybridation de PPC et de génération de colonnes) en résolvant le programme linéaire sous-jacent par relaxation lagrangienne (méthodes de sous-gradient et de génération de contraintes). D'autre part, nous appliquons le même principe de relaxation lagrangienne, sur la formulation linéaire initiale de Mingozzi et al. dont est extraite la relaxation préemptive utilisée par Brucker et Knust. Une partie du problème se réduit alors, comme indiqué par Möhring et al., au calcul d'une coupe minimale dans un graphe.<br /> <br />Nous étudions ensuite, un second type de bornes inférieures, obtenu par des méthodes de coupes basées sur les relaxations continues de deux formulations linéaires entières. Ces programmes linéaires sont au préalable resserés par des techniques éprouvées de propagation de contraintes, dont la règle globale du shaving. L'originalité de notre méthode repose essentiellement dans la génération des coupes qui sont, en grande partie, directement déduites des règles de propagation de contraintes.<br /><br />Enfin, nous proposons une méthode originale de résolution exacte pour le RCPSP, basée sur la procédure de Resolution Search de Chvàtal, une alternative aux méthodes de Branch-and-Bound classiques et qui se rapproche du Dynamic Backtracking en programmation par contraintes. Dans Resolution Search, l'espace de recherche ne se présente pas comme un arbre, puisqu'il s'agit, à chaque fois qu'un noeud terminal est rencontré, de rechercher par backtrakings successifs, les fixations minimales qui font de ce noeud un noeud terminal. L'ensemble des ces fixations est alors stocké de manière intelligente de façon à les exclure de l'espace de recherche. Resolution Search a été initialement développée pour la résolution de programmes linéaires en variables binaires, mais n'a semble-t'il jamais été employée dans le cadre de problèmes spécifiques.<br />Dans le but de prouver son efficacité, nous commencons par l'appliquer basiquement à deux formulations linéaires en variables binaires pour le RCPSP et la comparons à une version tout aussi basique de Branch-and-bound.<br /> Nous en poursuivons l'étude en utilisant des règles de branchement et d'évaluation ayant déjà prouvé leur efficacité dans des implémentations classiques de méthodes arborescentes pour le RCPSP, telles que celles de Brucker et al., Carlier et Latapie, Demeulemeester et Herroelen.

.

L'évolution constante des processeurs vers des architectures proposant des capacités superscalaires, de parallélisme au niveau des instructions, de prédiction, de spéculation et la multiplication des niveaux de hiérarchie mémoire donnent de plus en plus d'importance au travail du compilateur.<br />Dans cette thèse, nous nous intéressons aux transformations du programme source destinées à l'optimisation dans la chaîne de compilation, et plus particulièrement à une transformation appelée décalage d'instructions.<br />Cette transformation sert de base au pipeline logiciel, elle a une influence sur le parallélisme au niveau des instructions et l'utilisation des registres.<br />Elle intervient également comme composante des techniques de parallélisation de boucles par ordonnancement affine.<br />Nous avons voulu mieux comprendre les perspectives offertes par le décalage d'instructions, savoir quels objectifs il permettait d'atteindre mais aussi savoir quels problèmes de décalage restaient difficiles.<br />Pour cela nous avons étudié le décalage d'instructions dans plusieurs contextes plus ou moins proches, et apporté des contributions à chacun d'entre eux.<br /><br />Dans le cadre du pipeline logiciel, nous proposons un algorithme polynomial pour déterminer le décalage le plus à même de produire un maximum de parallélisme au niveau des instructions, et une étude expérimentale de l'efficacité absolue de la technique à l'aide de l'outil logiciel que nous avons réalisé dans ce but : PASTAGA (pour Plate-forme d'Analyse Statistique et de Tests d'Algorithmes sur Graphes Aléatoires).<br />Dans le cadre de l'utilisation des registres (stage scheduling), de la parallélisation de boucle et de la localité, nous apportons des réponses aux problèmes de décalage d'instructions associés~: complexité, solutions exactes, approximations.

Après un état de l'art sur l'ordonnancement en général et l'ordonnancement temps réel en particulier permetttant de préciser les notions utilisées par la suite et après avoir motivé l'intérêt d'une nouvelle contrainte temps réel de latence, nous proposons un modèle qui formalise les systèmes temps réel avec contraintes de précédences, de périodicités et de latences. Dans ce modèle, les précédences sont définies par un graphe orienté acyclique infiniment répété. Pour le cas monoprocesseur, on étudie trois problèmes d'ordonnancement : celui des systèmes avec contraintes de précédences et de périodicités, celui des systèmes avec contraintes de précédences et de latences et enfin celui des systèmes avec contraintes de précédences, de périodicités et de latences. Pour chaque problème on étudie la cohérence entre les différentes contraintes, on donne des conditions d'ordonnançabilité et on propose un algorithme prouvé optimal dans le sens où s'il y a un ordonnancement, l'algorithme le trouvera. On passe ensuite au cas multiprocesseur où l'architecture est définie par un graphe non-orienté. On étudie trois problèmes d'implantation (distribution et ordonnancement) dans les mêmes cas qu'en monoprocesseur en tenant compte des temps de communications. On prouve que ces trois problèmes sont NP-difficiles et on propose, donc, des heuristiques. Les performances de chaque heuristique sont comparées à celles d'algorithme exacte de type "branch and bound", en utilisant des simulations numériques.

L'évolution des besoins des logiciels entraîne la croissance de la complexité des environnements répartis. La recherche effectuée dans le domaine de la conception de ces environnements vise à réduire cette complexité. Un des principaux problèmes de la conception des infrastructures réparties concerne la composition des propriétés non fonctionnelles (également appelées services techniques). Les services interagissent entre eux. Nous avons identifié deux types d'interaction : les interactions de type structurel et les interactions de type comportemental.<br />Il existe actuellement de nombreuses approches (académiques et industrielles) qui permettent de concevoir ces infrastructures.<br />Dans un premier temps, nous exposons les concepts de la composition et nous étudions les mécanismes de composition mis en oeuvre dans ces approches de conception.<br />A partir de cette étude, nous proposons une nouvelle approche de composition appelée composition comportementale qui permet de supprimer un certain nombre de limites identifiées dans les autres approches. L'approche de composition comportementale utilise le modèle de composants Fractal et introduit un modèle d'automates qui permet de décrire les comportements des composants.<br />Les interactions de type structurel s'expriment à partir du modèle de composants et se matérialisent par des liaisons entre les interfaces des composants. Les interactions de type comportemental s'expriment à partir du modèle d'automate et se matérialisent par des contraintes d'ordonnancement. Les mécanismes de composition de notre approche mettent en oeuvre ces différents types d'interaction.<br />Nous avons réalisé un canevas logiciel qui implante le modèle de composant et le modèle de comportement. Le canevas a été conçu afin que les approches de conception puisse l'utiliser. L'implantation du canevas génère un environnement d'exécution basé sur le langage synchrone réactif Esterel.<br />Pour conclure, nous positionnons notre approche avec les autres approches de conception à partir de critères d'évaluation que nous avons définis. Quelques perspectives concernant l'approche sont données.

Dans ce mémoire, nous étudions les méthodes itératives de recherche dans le cadre de la résolution du problème d'ordonnancement de type jobshop<br /><br />Plus que les performances en elles-mêmes, nous nous intéressons tout particulièrement à la compréhension du fonctionnement des méthodes de résolution ainsi qu'à l'analyse de l'influence de la coopération de plusieurs méthodes de recherche sur la qualité des solutions engendrées.<br /> <br />Dans un premier temps, nous évaluons l'apport de critères secondaires intégrés dans la fonction coût. Nous utilisons des algorithmes itératifs de recherche pour étudier l'impact de l'intégration de ces critères sur le paysage adaptatif ainsi que sur la qualité des ordonnancements engendrés.<br /><br />Nous proposons ensuite quelques améliorations du schéma d'application des opérateurs dans les algorithmes génétiques. <br /><br />Finalement, nous étudions quelques modèles d'hybridation des méta-heuristiques basés sur la recherche tabou et les algorithmes évolutifs.

Les nouveaux supports d'exécution que sont les grilles de processeurs<br />apparaissent aujourd'hui comme une alternative économiquement viable aux grands systèmes de calcul centralisés. De grands projets nationaux comme GRID5000 sont basés sur ce concept de machines réparties. Ce changement du paysage du calcul parallèle haute performance a créé une nouvelle demande d'algorithmes spécifiques pour tirer le meilleur parti des ressources déployées. Pour concevoir ces algorithmes et démontrer leur efficacité, il faut s'appuyer sur des modèles qui tentent de décrire fidèlement le comportement réel des machines tout en restant suffisamment simples à manipuler. Dans cette thèse, nous avons étudié deux modèles parmi les plus importants pour ces nouveaux supports et nous avons fourni des algorithmes polynomiaux optimaux, des algorithmes d'approximations garantis, ou des preuves de NP-complètudes le cas échéant.

Cette thèse aborde le problème de la résolution des problèmes combinatoires à l'aide d'algorithmes génétiques. Ce type d'algorithme présente en effet nombres d'avantages. Cependant, ils sont généralement relativement lents. Cette thèse est donc centrée sur les algorithmes hybrides, c'est-à-dire des algorithmes construits à l'aide de plusieurs méthodes différentes. Dans notre cas, nous étudions les algorithmes qui réunissent algorithmes génétiques et heuristiques. Il existe deux méthodes pour générer de tels algorithmes qui sont la représentation directe et la représentation indirecte. Ces deux méthodes sont étudiés au travers de trois problèmes distincts : l'ordonnancement statique de programmes parallèles, le placement de composants électroniques et la planification de réseaux cellulaires. Pour chacun des trois problèmes, les algorithmes hybrides ont montrés leur efficacité. Pour le problème de la planification de réseaux cellulaires, une nouvelle modélisation a été faite. Cette modélisation permet d'effectuer en même temps le placement des émetteurs et l'allocation de fréquences.

Dans cette thèse, les mécanismes d'implantation efficace d'algorithmes d'ordonnancement dans des langages de programmation parallèle de haut niveau sont étudiés. Ces mécanismes sont basés sur les principes de dégénération séquentielle et distribuée. La dégénération séquentielle consiste à optimiser les coûts de création de tâches lorsqu'il n'est pas nécessaire de générer plus de parallélisme. La dégénération distribuée consiste à générer automatiquement une exécution distribuée aussi proche que possible de celle du programme équivalent écrit avec une bibliothèque de communication de type MPI. Dans l'objectif de proposer un couplage efficace de ces deux mécanismes, plusieurs protocoles de cohérence mémoire permettant d'implanter des couches de mémoire partagée distribuée sont comparés. Cette étude permet de valider l'efficacité du protocole "flot de données" que nous proposons lorsque le nombre de tâches déplacées lors de l'exécution du programme est faible. Un mécanisme de pile distribuée permettant l'implantation de ce protocole est proposé. Il est basé sur une gestion efficace du flot de données couplé avec un mécanisme d'allocation performant. Ces mécanismes sont finalement implantés dans le langage Athapascan et validés pour des applications de simulation et d'optimisation combintoire.

Ce travail propose une approche originale pour l'ordonnancement de tâches sous contraintes de temps et de ressources. Les méthodes et techniques développées s'inscrivent dans la problématique de l'"Analyse Sous Contraintes" (A.S.C.) des problèmes d'ordonnancement. Cette A.S.C. vise à caractériser les ordonnancements admissibles de manière à proposer au décideur un choix d'actions cohérentes vis-à-vis des contraintes, tout en lui offrant une certaine flexibilité face à des aléas éventuels. L'A.S.C. est décrite comme un processus d'inférence mettant en interaction une base de règles et une base de faits temporels et séquentiels représentant les caractéristiques des ordonnancements admissibles. Un logiciel (MASCOT) écrit en Prolog-II a été réalisé selon ce principe. Une nouvelle approche pour l'A.S.C. et plus particulièrement pour le raisonnement temporel sous contraintes de ressources a été développée. L'originalité de cette approche réside essentiellement dans la prise en compte du couplage temps/ressource à l'aide du concept d'intervalle temps-ressource qui conduit à utiliser un raisonnement énergétique. L'intervalle temps-ressource permet de représenter à la fois les tâches ou intervalles consommateurs et les intervalles de temps alloués sur lesquels des ressources sont disponibles, appelés intervalles fournisseurs. Le problème de l'ordonnancement de tâches amène à étudier l'interaction entre intervalles consommateurs et fournisseurs sur la base de considérations énergétiques. Le logiciel MASCOT met en jeu un processus de déduction symbolique. Ce type de déduction a été amélioré par la prise en compte de l'énergie obligatoirement consommée ou consommation obligatoire d'intervalles consommateurs sur un intervalle fournisseur. De nouvelles règles de déduction ont été écrites et intégrées dans MASCOT. D'autre part, un processus de déduction basé sur un raisonnement purement énergétique a été élaboré et implémenté (logiciel REPORT) en Prolog-II. Il utilise un autre type de déduction, la déduction numérique, qui permet d'affiner les bornes temporelles d'un intervalle fournisseur en considérant la consommation obligatoire des autres intervalles consommateurs. En d'autres termes, ces résultats consistent à actualiser des dates limites et correspondent à des conditions nécessaires d'admissibilité ; ils permettent ainsi de détecter des infaisabilités éventuelles. L'outil de modélisation utilisé est le graphe potentiels-bornes qui permet de représenter des contraintes numériques (sur la durée des tâches par exemple) et des contraintes symboliques entre intervalles. Il sert de support à un processus d'inférence par propagation numérique des contraintes.