Le travail présenté dans cette thèse, issu d'une problématique industrielle réelle, traite de la coordination entre la production et la distribution, dans un environnement multisite, multiproduit et multipériode. Après une présentation de la problématique industrielle, la première partie du mémoire s'intéresse essentiellement à l'organe de production et étudie des problèmes d'ordonnancement de machines parallèles. Dans cette partie, nous introduisons tout d'abord les problèmes d'ordonnancement, puis nous présentons un état de l'art concernant l'ordonnancement de machines parallèles. Enfin, nous proposons des méthodes de résolution pour des problèmes d'ordonnancement de machines parallèles non liées avec temps de changement dépendant de la séquence entre les produits. La deuxième partie du mémoire s'intéresse à une prise en compte plus globale de l'ensemble de la division industrielle et en particulier aux aspects multisites et aux problèmes liés à la coordination. Après une revue des travaux récents dans ce domaine, nous proposons une décomposition spatiale permettant de diviser le problème global en plusieurs problèmes plus petits et d'utiliser ainsi des méthodes plus performantes pour résoudre chacun d'entre eux. Enfin, le dernier chapitre détaille l'étude d'un problème réel et donne les performances et les limites du modèle proposé pour sa résolution.

Les ordinateurs parallèles offrent une alternative intéressante pour les applications de calcul scientifique, grandes consommatrices de ressources de calcul et de mémoire. Cependant, la programmation efficace de ces machines est souvent difficile et les implantations obtenues sont généralement peu portables. Nous proposons dans cette thèse un modèle de programmation parallèle permettant une programmation simple, portable et efficace des applications parallèles. Ce modèle est basé sur une décomposition explicite de l'application en tâches de calculs qui communiquent entre elles par l'intermédiaire d'objets en mémoire partagée. La sémantique des accès aux données partagées est quasi séquentielle et les précédences entre les tâches sont implicitement définies pour respecter cette sémantique. Nous présentons dans une première partie la mise en oeuvre de ce modèle de programmation dans l'interface applicative C++ Athapascan-1. Une analyse à l'exécution des dépendances de données entre tâches permet d'extraire le flot de données et donc les précédences entre les tâches à exécuter. Des algorithmes d'ordonnancement adaptables à l'application et à la machine cible sont également utilisés. Nous montrons comment, sur architecture distribuée, la connaissance du flot de données entre les tâches peut être utilisée par le système pour réduire les communications et gérer efficacement la mémoire partagée distribuée. Ce modèle de programmation et sa mise en oeuvre dans l'interface applicative Athapascan-1 sont ensuite validés expérimentalement sur différentes architectures et différentes applications d'algèbre linéaire, notamment la factorisation creuse de Cholesky avec partitionnement bidimensionnel. La facilité de programmation de ces applications grâce à cette interface et les résultats obtenus (amélioration des performances par rapport au code de factorisation dense de Cholesky de la bibliothèque ScaLapak sur une machine à 60 processeurs par exemple) confirment l'intérêt du modèle de programmation proposé.

Cette thèse est centrée sur la modélisation de l'exécution d'une application parallèle par un graphe de flot de données. Ce graphe, qui relie les tâches aux données partagées, est construit de manière dynamique. Cette construction, indépendante de l'ordonnancement des tâches effectué, permet de définir la sémantique des accès aux données et de controler la consommation mémoire de toute exécution. Nous étudions dans une première partie les algorithmes permettant la construction et la gestion d'un tel graphe de flot de données dans un environnement distribué. Un point crucial de ces algorithmes est la détection de terminaison des accès des tâches sur les données partagées. Nous proposons un algorithme réactif réalisant cette détection. L'implantation de cet algorithme est au centre de l'implantation distribuée de l'interface de programmation parallèle Athapascan-1. Cette interface permet la description du parallélisme d'une application par création de tâches asynchrones. La sémantique (de type lexicographique) de cette interface est également définie à partir du graphe de flot de données. Nous montrons dans une deuxième partie que la connaissance du flot de données d'une application permet de controler de manière théorique la durée et, surtout, la consommation mémoire de toute exécution. Ce controle est effectué à partir d'un ordonnancement séquentiel implicite des tâches. Nous proposons, implantons dans Athapascan-1 et évaluons deux algorithmes d'ordonnancement distribués permettant de limiter le volume de mémoire requis par toute exécution. Ces expérimentations permettent de valider les résultats théoriques obtenus.

La notion de qualité de service (QoS) est un concept important pour transporter sur les réseaux de l'information avec un maximum de fiabilité. Les métriques de la QoS sont le débit, le délai, la gigue et le taux de pertes. Par ailleurs, la multiplicité des applications conduit à une hétérogénéité des données : les flots élastiques requièrent un débit soutenu et les flots non élastiques exigeants en délai. Les algorithmes d'ordonnancement à différenciation proportionnelle permettent de partager équitablement les ressources entre les applications, selon leurs besoins. Toutefois, la proportionnalité ne s'est jusque-là effectuée que selon un seul critère de qualité (débit, délai ou taux de perte). Nous proposons un algorithme d'ordonnancement à différenciation proportionnelle, fondée sur la fonction de puissance mettant en rapport deux critères : le délai et le débit. L'ordonnanceur PSP (Power as a Scheduling Parameter) offre un partage équitable des ressources entre les applications à besoins différents de manière à ce qu'aucune classe ne subisse de phénomène de famine. L'implémentation et les tests de l'ordonnanceur ont été réalisés au moyen de l'outil de simulation ns-2.

Les travaux présentés dans cette thèse concernent l'ordonnancement<br />pour les plates-formes hétérogènes à grande échelle. Nous nous<br />intéressons principalement aux opérations de communications<br />collectives comme la diffusion de données, la distribution de données<br />ou la réduction. Nous étudions ces problèmes dans le cadre de leur<br />régime permanent, en optimisant le débit d'une série d'opérations de<br />communications, en vue d'obtenir un ordonnancement asymptotiquement<br />optimal du point de vue du temps d'exécution total. Après avoir<br />présenté un cadre général d'étude qui nous permet de connaître la<br />complexité du problème pour chaque primitive, nous développons, pour<br />le modèle de communication un-port bidirectionnel, une méthode de<br />résolution pratique fondée sur la résolution d'un programme linéaire<br />en rationnels. Cette étude du régime permanent est illustrée par des<br />expérimentations sur Grid5000 et se prolonge vers l'ordonnancement<br />d'applications multiples sur des grilles de calcul.

Nos travaux concernent la mise en œuvre de méthodologies pour la résolution de problèmes d'ordonnancement en industries agroalimentaires. Trois nouvelles approches basées sur les algorithmes génétiques, sont proposées pour la résolution de problèmes d'ordonnancement multi-objectifs : les algorithmes génétiques séquentiels (SGA), les algorithmes génétiques parallèles (PGA) et les algorithmes génétiques parallèles séquentiels (PSGA). Deux approches coopératives multi-objectifs en mode relais, SH_GA/TS et SH_GA/SA, hybridant toutes les deux des métaheuristiques de haut niveau, sont par la suite proposées. Un algorithme évolutionnaire et un algorithme de recherche locale sont, dans ce cas exécutés séquentiellement.

Les grilles de calcul et le "cloud computing" permettent de distribuer un ensemble de ressources informatiques, telles que du stockage ou du temps de calcul, à un ensemble d'utilisateurs en fonction de leurs demandes en donnant l'illusion de ressources infinies. Cependant, lorsque l'ensemble de ces ressources est insuffisant pour satisfaire les exigences des utilisateurs, des conflits d'intérêts surgissent. Ainsi, un libre accès à des ressources limitées peut entraîner une utilisation inefficace qui pénalise l'ensemble des participants. Dans de tels environnements, il devient nécessaire d'établir des procédures d'arbitrage afin de résoudre ces conflits en garantissant une distribution équitable aux différents utilisateurs. Nous présentons une nouvelle classe de problèmes : celle des ordonnancements multi-utilisateurs. Cette thèse aborde la notion d'équité au travers de problèmes d'allocation de ressources sous incertitudes et d'ordonnancement de tâches périodiques.

Nous étudions la modélisation et la validation hors-ligne des applications temps-réel en environnement monoprocesseur, qui prend explicitement en compte l'échange des messages, le partage des ressources et les instructions conditionnelles entre les tâches. Notre objectif est de mettre en évidence l'impact de ces paramètres sur l'analyse des applications. Classiquement, ces applications sont modélisées de façon linéaire, en encapsulant les blocs conditionnels, et les séquences sont utilisées pour leur validation. Nous proposons une approche de modélisation et de validation arborescente, qui permet de considérer de façon explicite les blocs conditionnels, et qui utilise les arbres d'ordonnancement pour la validation. Nous comparons ensuite ces deux approches, et prouvons que les premières sont parfois trop pessimistes, c'est à dire qu'elles peuvent conduire à déclarer certaines applications comme non ordonnançables, alors qu'en réalité elles le sont. Nous commençons par construire un générateur d'arbres d'ordonnancement valides. La complexité du générateur étant exponentielle en fonction du nombre de tâches, cette approche est di cile à mettre en ÷uvre dans la pratique. Nous proposons donc une approche de modélisation bas ée sur les réseaux de Petri. Ce réseau sera utilisé pour générer les arbres valides, par construction du graphe de marquages, et la complexité pourra être réduite grâce à des heuristiques.

Les systèmes temps réel à contraintes temporelles strictes sont caractérisés par des ensembles de tâches pour lesquelles sont connus l'échéance, le modèle d'arrivée (fréquence) et la durée d'exécution pire cas (WCET). Nous nous intéressons à l'ordonnancement de ces systèmes sur plate-forme multiprocesseur. Garantir le respect des échéances pour un algorithme d'ordonnancement est l'une des problématiques majeures de cette thématique. Nous allons plus loin en nous intéressant à la sûreté temporelle, que nous caractérisons par les propriétés (i) de robustesse et (ii) de viabilité. La robustesse consiste à proposer un intervalle sur les augmentations (i-a) de WCET et (i-b) de fréquence tel que les échéances soient respectées. La viabilité consiste cette fois à garantir le respect des échéances lors du relâchement des contraintes (ii-a) de WCET (réduction), (ii-b) de fréquence (réduction) et (ii-c) d'échéance (augmentation). La robustesse revient alors à tolérer l'imprévu, tandis que la viabilité est la garantie que l'algorithme d'ordonnancement n'est pas sujet à des anomalies suite à un relâchement de contraintes. Nous considérons l'ordonnancement en priorités fixes, où chaque occurrence d'une tâche est ordonnancée avec la même priorité. Dans un premier temps, nous étudions la propriété de robustesse dans les approches d'ordonnancement hors-ligne et sans migration (partitionnement). Nous traitons le cas des tâches avec ou sans partage de ressources. Dans un second temps, nous étudions la propriété de viabilité d'une approche d'ordonnancement en ligne avec migrations restreintes et sans partage de ressources.

Un réseau ad hoc peut se voir comme une généralisation ultime d'un réseau sans fil. Les protocoles qui assurent la communication dans un réseau ad hoc doivent également prendre en compte la mobilité et la variation de la connectivité des noeuds. En fait, la recherche sur les algorithmes de routage dans les réseaux ad hoc s'est principalement concentrée sur des réseaux totalement connectés dans lesquels la mobilité des noeuds n'est pas utilisée. Dans cette thèse, nous nous sommes intéressés à des techniques qui mettent la mobilité au service du routage dans un réseau ad hoc de grande taille. Certains inconvénients du routage dans ces réseaux sont l'information imprécise sur le routage des noeuds à longue distance, la variation de la connectivité et le surcoût généré par les protocoles de routage. Cette thèse offre une solution basée sur le contrôle de la mobilité des noeuds pour amléiorer les performances des protocoles de routage d'un réseau ad hoc de grande taille. Nous pensons que le mouvement des noeuds présente une opportunité: si les noeuds se déplacent d'une manière appropriée, alors les algorithmes de routage peuvent en tirer profit. Ainsi, notre solution met en oeuvre un mécanisme de rendez-vous qui réduit, les effets de la mobilité, le surcoût dû aux mises à jour et assure une communication en temps borné dans le réseau. Une autre conséquence de ce mécanisme est la réduction de la consommation de l'énergie et de la bande passante car la zone de transmission des noeuds peut être réduite. Nous présentons deux algorithmes, dont un tolérant aux pannes et développé un simulateur pour faire des tests et des mesures de performances. De plus, nous avons montré la faisabilité de la solution par une implantation sur des robots.