L'objectif de ce travail est de dégager un ensemble d'éléments qui puissent servir de base à la mise en place d'un logiciel d'ordonnancement dont les actions permettent de prendre en compte les besoins d'un certain nombre d'entreprises qui seraient surtout des PME. Notre travail comporte deux parties : - Dans la première partie, nous présenterons un bilan des méthodes d'ordonnancements disponibles. Dans les deux premiers chapitres, nous présenterons des rappels sur la théorie des graphes et des généralités sur les ordonnancements. Dans le troisième chapitre, nous présenterons le problème central d'ordonnancement, étape fondamentale dans toutes les familles d'ordonnancement. Dans le quatrième chapitre, nous étudierons les problèmes cumulatifs qui se posent dès lors que l'on s'intéresse aux moyens de réalisation. Dans le cinquième chapitre, nous nous intéresserons à certaines méthodes d'optimisation économique des projets. - La deuxième partie sera dirigée vers la construction du cadre d'un logiciel à l'usage des PME. Dans le sixième chapitre, nous présenterons nos enquêtes auprès des entreprises pour la mise en évidence des pratiques et des besoins en ordonnancements. Dans le septième chapitre, nous ferons l'intégration des contraintes après analyse. Dans le huitième chapitre, nous présenterons le logiciel.

Du fait de la miniaturisation grandissante des circuits électroniques, la conception de système sur puce actuelle, se heurte au problème des latences sur les fils d'interconnexions traversant tout le circuit. Un système sur puce est un ensemble de blocs de calculs (les composants IP) qui s'échangent des données. Alors que la communication à l'intérieur de ces blocs de calculs peut toujours se faire de manière synchrone, c'est à dire s'abstraire comme une action instantanée, la communication d'un bloc de calculs à un autre prend un temps qui n'est pas négligeable. Il s'écoule plusieurs cycles d'horloge entre l'émission d'une donnée sur un fil d'interconnexion et sa réception. La théorie du Latency Insensitive Design créée par Luca Carloni et Alberto Sangiovanni-Vincentelli permet entre autre de résoudre ce problème en implantant un protocole de communication basé sur la segmentation des fils d'interconnexions et sur le principe de rétroaction en cas d'embouteillage. Dans un premier temps, nous avons donné un fondement théorique à cette théorie en la rapprochant formellement d'une modélisation par Marked/Event graph (Sous ensemble sans conflit des Réseaux de Pétri) et avec des places de capacité ; ce qui génère naturellement le protocole de contrôle de flux. Cette modélisation nous amène à la problématique principale de cet ouvrage: comment, et sous quelles conditions, peut on minimiser la taille des ressources de mémorisation utilisées comme tampons intermédiaires au long de ces fils d'interconnexions? Car leur nombre et leur position peuvent se révéler critique à l'implantation matérielle. Nous allons ensuite étudier cette question sous une hypothèse naturelle de déterminisme, ce qui permet d'obtenir des régimes de fonctionnement périodiques et réguliers. Le but de cette thèse est de modifier le protocole mis en place dans la théorie du Latency Insensitive Design en prenant en compte cette hypothèse. L'étude des systèmes déterministes et des résultats existant nous a permis une première phase de modification appelée: égalisation. L'étape suivante consiste à ordonnancer statiquement ces systèmes. Pour cela, nous avons choisi de représenter explicitement l'ordonnancement de chacun des éléments du système comme un mot binaire périodique où les "1" représentent les instants d'activités et les "0" d'inactivités tel que M. Pouzet et al. l'ont introduit dans le "N-synchronous Kahn network". Une étude approfondie des différentes classes de mots binaires existants (mot de Sturm, de Christoffel, de Lyndon ou encore mécaniques) a précédé leur association à la théorie du Latency Insensitive Design et au processus d'égalisation pour obtenir des systèmes déterministes ordonnancés statiquement.

La simulation de systèmes complexes a pour objectif d'offrir une observation de la dynamique des systèmes étudiés dans un temps adapté à une interprétation scientifique. La simulation orientée agent permet de plus une observation multi-échelle du système considéré car elle s'appuie sur la description des entités granulaires composant celui-ci et leurs interactions. Le grand nombre d'entités nécessaires à la modélisation de systèmes large-échelle grêve cependant les performances en simulation. Ces travaux de recherche visent l'exécution de telles simulations en proposant de les appuyer sur un réseau de plates-formes de simulation. Après avoir identifié les exigences d'une telle approche, nous proposons une architecture agent pour la gestion de la cohérence de la simulation distribuée sur une infrastructure d'exécution flexible. Le système multi-agent formé par les agents répartis sur les plates-formes établit une plate-forme virtuelle exécutant la simulation sans adaptation du modèle simulé. Pour optimiser les performances, nous considérons la représentation du temps dans les simulations et les mécanismes agents d'interaction, notamment le modèle perception/influence sur l'environnement, afin d'établir un ordonnancement parallèle de la simulation. Nous complétons cette exécution parallèle en considérant l'équilibrage de charges dynamique. Ce dernier s'appuie lui aussi sur les informations incluent dans le modèle simulé et vise autant à maximiser l'exploitation de chacune des plates-formes qu'à assurer la flexibilité de la simulation vis à vis de la dynamique de l'infrastructure d'exécution. Ces concepts et algorithmes sont mis en œuvre dans la plate-forme GEAMAS-NG.

La modélisation et l'analyse de systèmes hospitaliers sont traditionnellement réalisées en utilisant méthodes et outils issus du génie industriel. Cependant, les caractéristiques de ces systèmes sont difficiles à capturer avec les outils de modélisation et de simulation classiques. Notre objectif est de spécifier et de développer une plate-forme de modélisation et de simulation dédiée aux systèmes hospitaliers, appelée medPRO (medical Process-Resource-Organisation), accompagnée d'une méthodologie d'analyse adaptée au domaine médical. Cette plate-forme est construite autour d'un cadre de modélisation et d'un guide méthodologique conçus pour un système hospitalier particulier. UML (Unified Modelling Language) a été choisi pour la modélisation de ces systèmes. Plusieurs points de vue sont proposés : Processus (vue centrée sur le patient), Ressource (comportement des ressources humaines et matérielles), et Organisation (relation entre les intervenants). Le comportement dynamique du modèle est spécifié grâce à une classe dédiée de réseaux de Petri, appelés réseaux de Petri de Santé : un algorithme de simulation à événements discrets a également été développé pour les réseaux de Petri. Une large partie de ce travail est dédiée au système de décision, qui est utilisé (i) pour appliquer des méthodes de planification et d'ordonnancement issues du génie industriel à des systèmes hospitaliers, et (ii) pour piloter le déroulement de la simulation en temps réel au travers d'une approche hybride hiérarchique/hétérarchique. Trois études de cas sont également présentées pour montrer l'efficacité de la plateforme medPRO : nous nous sommes intéressés à l'unité neuro-vasculaire, à la pharmacie et au bloc opératoire du CHU de Saint-Etienne (France). Plusieurs outils d'optimisation spécifiques ont été développés et inclus dans la plate-forme.

Dans cette thèse, nous traitons des problèmes d'intégration des décisions prises aux niveaux planification (tactique) et ordonnancement (opérationnel). Que ce soit en théorie ou en pratique, ces deux niveaux sont habituellement traités indépendamment l'un de l'autre. Ainsi, les objectifs de production à réaliser sont souvent incohérents avec la capacité réelle de l'atelier. Cette thèse propose des méthodes de résolution pour des problèmes intégrés de planification et d'ordonnancement. Nous développons un nouveau modèle mathématique qui prend en compte de manière originale les contraintes de séquencement des opérations sur les machines, garantissant ainsi la faisabilité du plan de production. Ce modèle est résolu à l'aide d'une heuristique Lagrangienne pour une séquence des opérations axée. Notre approche est originale à double titre : dans la mise à jour des multiplicateurs Lagrangiens (puisque il existe un nombre exponentiel de contraintes de capacité dans notre modèle), et par la proposition d'une nouvelle procédure de lissage pour la construction d'une solution réalisable. Nous développons ensuite deux approches, basées sur le recuit simulé et la recherche taboue, qui permettent d'améliorer la séquence des opérations sur les ressources et ainsi de chercher un plan de production optimal associé à une séquence réalisable. De nombreux résultats expérimentaux ont été effectués et valident l'efficacité de nos approches.

De nombreux problèmes d'optimisation issus du monde réel, notamment dans le domaine de la logistique, doivent faire face à beaucoup de difficultés. En effet, ils sont souvent caractérisés par des espaces de recherche vastes et complexes, de multiples fonctions objectif contradictoires, et une foule d'incertitudes qui doivent être prises en compte. Les métaheuristiques sont des candidates naturelles pour résoudre ces problèmes, ce qui les rend préférables aux méthodes d'optimisation classiques. Toutefois, le développement de métaheuristiques efficaces découle d'un processus de recherche complexe. Le cœur de ce travail réside en la conception, l'implémentation et l'analyse expérimentale de métaheuristiques pour l'optimisation multiobjectif, ainsi que leurs applications à des problèmes logistiques de tournées et d'ordonnancement. Tout d'abord, une vue unifiée de ces approches est présentée, puis intégrée dans une plateforme logicielle dédiée à leur implémentation, ParadisEO-MOEO. Ensuite, plusieurs approches de coopération, combinant des métaheuristiques pour l'optimisation multiobjectif, sont proposées. Enfin, la question de la prise en compte l'incertitude est abordée dans le contexte de l'optimisation multiobjectif.

La résolution de systèmes linéaires creux est critique dans de nombreux domaines de la simulation numérique. Beaucoup d'applications, notamment industrielles, utilisent des méthodes directes en raison de leur précision et de leur robustesse. La qualité du résultat, les fonctionnalités numériques, ainsi que le temps de calcul sont critiques pour les applications. Par ailleurs, les ressources matérielles (nombre de processeurs, mémoire) doivent être utilisées de manière optimale. Dans cette habilitation, nous décrivons des travaux poursuivant ces objectifs dans le cadre de la plate-forme logicielle MUMPS, développée à Toulouse, Lyon-Grenoble et Bordeaux depuis une quinzaine d'années. Le cœur de l'approche repose sur une parallélisation originale de la méthode multifrontale : une gestion asynchrone du parallélisme, associée à des ordonnanceurs distribués, permet de traiter des structures de données dynamiques et autorise ainsi le pivotage numérique. Nous nous intéressons à l'ordonnancement des tâches, à l'optimisation de la mémoire et à différentes fonctionnalités numériques. Les travaux en cours et les objectifs futurs visent à résoudre efficacement des problèmes de plus en plus gros, sans perte sur les aspects numériques, et tout en adaptant nos approches aux évolutions rapides des calculateurs. Dans ce contexte, les aspects génie logiciel et transfert deviennent critiques afin de maintenir sur le long terme une plate-forme logicielle comme MUMPS. Cette plate-forme est à la fois nécessaire à nos travaux de recherche et utilisée en production ; elle maximise ainsi les retours applicatifs qui valident nos travaux et permettent d'orienter nos recherches futures.

Dans cette Thèse, nous avons introduit plusieurs procédures pour résoudre le problème d'ordonnancement du projet multi-compétences (MSPSP). L'objectif est de trouver un ordonnancement qui minimise le temps de terminaison (makespan) d'un projet, composé d'un ensemble d'activités. Les relations de précédences et les contraintes de ressource seront considérées. Dans ce problème, les ressources sont des membres du personnel qui maîtrisent plusieurs compétences. Ainsi, un certain nombre de travailleurs doit être affecté pour utiliser chaque compétence requise par une activité. Par ailleurs, nous accorderons une importance particulière aux méthodes exactes pour résoudre le MSPSP, puisqu'il y a encore un certain nombre d'instances pour lesquelles l'optimalité doit encore être prouvée. Néanmoins,pour traiter des instances plus importantes, nous implémentons une approche heuristique.

L'usage des plateformes de Cloud Computing offrant une Infrastructure en tant que service (IaaS) a augmenté au sein de l'industrie. Les infrastructures IaaS fournissent des ressources virtuelles depuis un catalogue de types prédéfinis. Les avancées dans le domaine de la virtualisation rendent possible la création et la destruction de machines virtuelles au fur et à mesure, avec un faible surcout d'exploitation. En conséquence, le bénéfice offert par les plate-formes IaaS est la possibilité de dimensionner une architecture virtuelle au fur et à mesure de l'utilisation, et de payer uniquement les ressources utilisées. D'un point de vue scientifique, les plateformes IaaS soulèvent de nouvelles questions concernant l'efficacité des décisions prises en terme de passage à l'échelle, et également l'ordonnancement des applications sur les plateformes dynamiques. Les travaux de cette thèse explorent ce thème et proposent des solutions à ces deux problématiques. La première contribution décrite dans cette thèse concerne la gestion des ressources. Nous avons travaillé sur le redimensionnement automatique des applications clientes de Cloud afin de modéliser les variations d'utilisation de la plateforme. De nombreuses études ont montré des autosimilarités dans le trafic web des plateformes, ce qui implique l'existence de motifs répétitifs pouvant être périodiques ou non. Nous avons développé une stratégie automatique de dimensionnement, capable de prédire le temps d'utilisation de la plateforme en identifiant les motifs répétitifs non périodiques. Dans un second temps, nous avons proposé d'étendre les fonctionnalités d'un intergiciel de grilles, en implémentant une utilisation des ressources à la demandes.Nous avons développé une extension pour l'intergiciel DIET (Distributed Interactive Engineering Toolkit), qui utilise un marché virtuel pour gérer l'allocation des ressources. Chaque utilisateur se voit attribué un montant de monnaie virtuelle qu'il utilisera pour exécuter ses tâches. Le mécanisme d'aide assure un partage équitable des ressources de la plateforme entre les différents utilisateurs. La troisième et dernière contribution vise la gestion d'applications pour les plateformes IaaS. Nous avons étudié et développé une stratégie d'allocation des ressources pour les applications de type workflow avec des contraintes budgétaires. L'abstraction des applications de type workflow est très fréquente au sein des applications scientifiques, dans des domaines variés allant de la géologie à la bioinformatique. Dans ces travaux, nous avons considéré un modèle général d'applications de type workflow qui contient des tâches parallèles et permet des transitions non déterministes. Nous avons élaboré deux stratégies d'allocations à contraintes budgétaires pour ce type d'applications. Le problème est une optimisation à deux critères dans la mesure où nous optimisons le budget et le temps total du flux d'opérations. Ces travaux ont été validés de façon expérimentale par leurs implémentations au sein de la plateforme de Cloud libre Nimbus et de moteur de workflow MADAG présent au sein de DIET. Les tests ont été effectuées sur une simulation de cosmologie appelée RAMSES. RAMSES est une application parallèle qui, dans le cadre de ces travaux, a été portée sur des plateformes virtuelles dynamiques. L'ensemble des résultats théoriques et pratiques ont débouché sur des résultats encourageants et des améliorations.

La logistique de gestion de crise fait de plus en plus parler d'elle. En effet, que ce soit au sujet de conflits géopolitiques ou de catastrophes naturelles, ou encore lorsqu'il s'agit d'urgences de proximité, on ne peut plus passer à côté de la gestion de crise pour faire face à des faits internationaux ou nationaux. La logistique de gestion de crise œuvre pour que les secours soient optimisés et que l'aide et le ravitaillement en nourriture, eau, médicaments, soit apportés rapidement aux zones sinistrées. Les travaux de recherche présentés dans cette thèse, dans le cadre d'une coopération avec le département logistique d'EADS, visent à apporter une réponse à ces défis. Nous présentons, dans ce contexte, des solutions basées sur une approche de modélisation, optimisation et simulation orientée agents de flux logistiques. Les problèmes de gestion de flux abordés nous ont permis d'étudier et développer trois volets d'investigation : un module d'aide au positionnement des zones logistiques qui permet de minimiser les distances entre les zones et d'optimiser leurs nombre et ce pour une meilleure circulation des flux, une approche innovante pour l'ordonnancement distribué des tâches de livraison qui permet d'apporter une solution à un problème de gestion des flux fortement distribué, et finalement un agent holonique qui permet de fournir une estimation de la consommation à venir d'un site logistique, en alliant l'expertise des logisticiens aux modèles à base de logique floue. Pour démontrer l'efficacité des approches utilisées, un démonstrateur baptisé OBAC (Optimisation à Base d'Agents Communicants) a été réalisé, intégrant toutes ces approches et applications militaires