Cette thèse présente les résultats du projet de recherche Coopeer sur le thème de la conception collaborative. Ce travail a permis de mettre en place une architecture d'égal à égal pour la conception assistée par ordinateur (CAO) associée à une méthode optimiste de résolution automatique des conflits pour assurer la cohérence des données répliquées. Cette méthode s'appuie sur une estampille à double identification et sur une gestion de la simultanéité basée sur des priorités. La gestion du groupe de travail et la tolérance aux pannes y sont également adressées. La méthode est applicable à la CAO, mais aussi à tout type d'application collaborative complexe.

Nous considèrerons ici les modèles linéaires de multiflots, en mettant l'accent sur leurs multiples applications, notamment dans les domaines de l'ordonnancement et de la gestion de production. Il est bien connu que ces problèmes, présentés sous forme de programmes linéaires, sont difficiles à résoudre, contrairement à leurs homologues en flot simple. Les méthodes de résolution classiques proposent, déjà dans le cas continu, des solutions approchées. On distingue: les méthodes de décomposition par les prix, par les ressources, ainsi que les techniques de partitionnement. Si l'on rajoute la contrainte d'intégralité sur les flots, ces problèmes deviennent extrêmement difficiles. Nous nous sommes intéressés à un cas particulier des problèmes de multiflots, à savoir: le biflot entier de coût minimum. Nous avons développé une approche de résolution heuristique basée sur un principe de décomposition mixte, opérant itérativement, à la fois par une allocation de ressources et par un ajustement des coûts. L'implémentation de cette approche met en évidence des résultats prometteurs, obtenus sur des problèmes de biflot purs, générés aléatoirement. Nous avons donc envisagé une deuxième application sur des problèmes de biflot plus structurés. Ces problèmes de biflot ont été proposés pour la modélisation du problème de voyageur de commerce. Cette application débouche d'une part, sur l'utilisation d'un algorithme de recherche d'un circuit hamiltonien dans un graphe, et d'autre part, sur le développement de techniques heuristiques pour la construction de tournées intéressantes

Cette thèse se situe dans le cadre de la synthèse logique. Elle a pour objet la synthèse logique optimisée de circuits sur réseaux programmables à base de «tables de vérité» de type «Xilinx». Ces réseaux programmables ont été à l'origine du premier succès commercial des réseaux reprogrammables à faible granularité. Une première solution pratiquée industriellement a consisté à associer une bibliothèque équivalente de primitives logiques simples de type «cellule standard» à un réseau Xilinx. Une telle approche conduit à une très pauvre utilisation de la technologie cible car elle ne tire pas profit de la richesse de la cellule de base. Cette thèse s'intéresse, en conséquence, à des approches plus ciblées. Il s'agit de décomposer de façon optimisée les parties combinatoires en sous-fonctions «saturant» les possibilités des cellules élémentaires. Pour ceci, le traitement des fonctions booléennes sera effectué dès l'étape de factorisation en fonction du but final. Après un rappel de la factorisation «lexicographique», qui a comme fondement l'existence d'un ordonnancement des entrées, une méthode de décomposition en sous fonctions de k variables est proposée. Elle sert de base à des méthodes de décomposition technologique pour les séries Xilinx 3000 et Xilinx 4000. Deux alternatives à cette factorisation lexicographique sont proposées, une factorisation utilisant une représentation par diagramme de décision binaire (ROBDD) et une factorisation algébrique classique adaptée aux caractéristiques de la cible Xilinx. La dernière étape de synthèse concerne de façon plus fine le regroupement des sous-fonctions dans la cellule physique Xilinx et se préoccupe de l'optimisation des points de mémorisation, des buffers et des ressources d'horloge. Une évaluation sur un ensemble d'exemples internationaux et industriels démontre l'efficacité des méthodes proposées. Ce travail a fait l'objet d'un transfert technologique vers le logiciel industriel ASYL+

.

Nous considérons ici le problème où deux programmes différents situés sur deux grappes d'ordinateurs distantes, reliées par un réseau à haut débit, forment un couplage de code et échangent<br />régulièrement des données. Un tel échange s'effectue par une redistribution de données. Nous étudions comment effectuer une telle redistribution le plus efficacement possible en minimisant temps de communication et congestion du réseau.<br /><br />Nous utilisons pour ce faire, une modélisation du problème à l'aide de graphes bipartis. Le modèle choisi permet une prise en compte du délai d'initialisation des communications, des différentes bandes passantes et impose une limite d'une communication simultanée par interface réseau (modèle 1-port) et de k communications simultanées sur la dorsale.<br /><br />Nous effectuons une validation expérimentale du modèle puis l'utilisons pour développer deux algorithmes d'ordonnancement<br />des communications. Nous montrons que chacun d'entre eux<br />est un algorithme d'approximation garantissant un temps d'exécution dans le pire des cas 8/3 fois plus élevé que le temps optimal.<br />Nous concluons l'étude de ces algorithmes par une série d'expériences démontrant de bonnes performances en pratique.<br /><br /><br />Enfin, nous étendons le problème initial au cas de grappes hétérogènes :<br />ce cas imposant de sortir du modèle 1-port, nous montrons comment modifier nos algorithmes pour en tirer parti.<br />Nous étudions également le cas de redistributions exécutées en régime permanent sur un réseau d'une topologie plus complexe autorisant les communications locales.

Ce travail présente une méthode et des outils pour l'ordonnancement en temps réel d'atelier lorsque des contraintes complexes issues du terrain sont à prendre en compte. L'approche retenue vise à caractériser non pas une solution au problème d'ordonnancement, mais un ensemble de solutions sous la forme de groupes d'opérations permutables. Dans ce contexte, on considère un ensemble d'ordres de fabrication, chacun comportant une date de livraison et une date de début au plus tôt et étant composé d'un ensemble d'opérations d'exécution. Chaque opération d'exécution nécessite simultanément pour sa réalisation un ensemble de ressources cumulatives ou disjonctives, chacune d'elles devant être sélectionnée dans un ensemble prédéfini appelé pool. Les contraintes de précédence entre les opérations d'exécution d'un même ordre de fabrication sont définies par des gammes non linéaires. On propose de caractériser l'activité de préparation nécessaire sur un sous-ensemble des ressources requises pour réaliser une opération d'exécution, par un enchaînement de trois opérations élémentaires de préparation : le démontage, le changement de type et le montage. Chaque activité de préparation dépend de la séquence des opérations d'exécution et chaque opération de préparation peut nécessiter également des ressources complémentaires. Un graphe potentiels-tâches particulier est utilisé pour représenter une séquence de groupes. Basé sur une exploration de ce graphe, un algorithme polynomial d'insertion d'une opération dans un ordonnancement visant à minimiser la conséquence de cette insertion sur les dates de livraison, est défini. Cet algorithme est utilisé dans les méthodes proposées pour générer une séquence de groupes initiale et pour l'amélioration de type tabou de cette séquence. Ces méthodes sont validées sur des problèmes classiques d'ordonnancement de projet et sur des problèmes d'ordonnancement d' atelier avec préparation générés aléatoirement. Un système interactif d'aide à la décision est proposé pour l'ordonnancement en temps réel d'un atelier avec préparation, basé sur l'exploitation de la séquence de groupes. La nouvelle version du logiciel d'ordonnancement en temps réel ORDO basée sur ce travail est déjà installée sur plusieurs sites industriels.

Ce travail a pour objet la présentation d'une approche pour l'aide au dimensionnement, l'aide à l'élaboration de politiques de conduite et le pilotage en temps réel de cellules flexibles de fabrication. L'approche que nous proposons est articulée autour de la modélisation et de l'analyse d'une cellule flexible sous un ensemble de contraintes cycliques. Le modèle choisi est un réseau de Petri p-temporel t-temporisé plus général qu'un graphe d'événements. Il permet d'une part de découplet les contraintes de gammes des contraintes de ressources, et d'autre part de modéliser aussi bien les durées d'opération associées aux transitions qui sont les paramètres de notre problème, que les durées d'attente des pièces dans les stocks intermédiaires représentés par les places qui sont elles les inconnues du problème. Après avoir défini un régime stationnaire périodique forcé, des bornes minimales et maximales qui correspondent à des conditions nécessaires de réalisation d'une production plus ou moins flexible sont calculées à l'aide des techniques de la programmation mathématique. Ces bornes sont utilisées au niveau d'un algorithme de joueur de réseau de Petri p-temporel t-temporisé possédant un mécanisme de retour arrière ("backtrack") afin de calculer une stratégie particulière de réalisation de la production, l'objectif essentiel étant de réaliser un bon compromis entre efficacité et flexibilité. Finalement, en nous basant sur le résultat de l'ordonnancement prévisionel calculé, le modèle de réseau de Petri est utilisé pour un pilotage temps réel et réactif de la cellule au travers de l'utilisation d'un joueur temps réel ne possédant plus de mécanisme de retour arrière et permettant de décrire en temps réel l'enchaînement des traitements à effectuer sur les pièces, de communiquer avec l'environnement extérieur et d'être soumis à des contraintes temporelles explicites. Un exempl e d'application illustre l'approche exposée.

Depuis quelques années, la complexité croissante de besoins informatiques dans tous les domaines de recherche scientifique et technique exige une puissance de calcul sans cesse plus importante. Dans ce contexte, le calcul parallèle apparaît comme un outil vital qui permet d'exploiter la capacité de calcul de plusieurs microprocesseurs travaillant ensemble. Le domaine auquel le calcul parallèle sera appliqué dans cette thèse est celui de l'imagerie, plus spécifiquement la synthèse d'images à partir d'images réelles. Pour permettre la création de nouvelles vues virtuelles à partir de scènes réelles, une des étapes les plus coûteuses en temps de calcul est la phase d'appariement des images. Il s'agit de la formation de paires de pixels qui représentent le même point sur les surfaces de deux images source. Le problème principal que nous cherchons à résoudre dans cette thèse est la proposition d'une version parallèle pour l'algorithme d'appariement quasi-dense (aussi appelé algorithme de propagation) d'images qui est basé sur une stratégie adaptative globale. Cette version doit être capable de préserver la qualité du résultat final obtenu par la version séquentielle de l'algorithme de propagation tout en réduisant le temps d'exécution dans un contexte de programmation orienté vers les grappes de processeurs.

Cette thèse présente un ensemble d'objectifs dont le fil conducteur est le programme Décrypthon (projet tripartite entre l'AFM, le CNRS et IBM) où les applications et les besoins ont évolué au fur et à mesure de l'avancée de nos travaux. Dans un premier temps nous montrerons le rôle d'architecte que nous avons endossé pour la conception de la grille Décrypthon. Les ressources de cette grille sont supportées par les cinq universités partenaires (Bordeaux I, Lille I, ENS-Lyon, Pierre et Marie Curie Paris VI et Orsay), ainsi que le réseau RENATER (Réseau National de Télécommunications pour l'Enseignement et la Recherche), sur lequel est connecté l'ensemble des machines. Le Centre de ressources informatiques de Haute Normandie (CRIHAN) participe également au programme, il héberge les données volumineuses des projets scientifiques. Nous présenterons ensuite les expériences que nous avons effectuées sur l'intergiciel DIET afin de tester ses propriétés de façon à explorer sa stabilité dans un environnement à grande échelle comme Grid'5000. Nous nous sommes intéressés, en outre, au projet "Help Cure Muscular Dystrophy", un des projets sélectionnés par le programme Décrypthon. Nous avons conduit des expériences dans le but de préparer la première phase de calcul sur la grille de volontaires "World Community Grid". Nous dévoilerons l'ensemble des étapes qui ont précédées et suivies la première phase calculatoire qui a demandé quelques 80 siècles de temps processeur. Pour terminer, nous avons développé une fonctionnalité à l'intergiciel DIET, le rendant capable de gérer l'exécution de tâches ayant des dépendances. Nous nous sommes intéressés à développer des algorithmes prenant en compte plusieurs applications qui demandent l'accès aux mêmes ressources de manière concurrente. Nous avons validé cette fonctionnalité avec des applications issues des projets du programme Décrython. Ces travaux ont nécessité un développement logiciel important, d'une part sur les applications du Décrypthon elles-mêmes et sur leur portage afin de rendre transparente leur utilisation sur la grille Décrypthon, mais aussi au niveau de l'intergiciel DIET et son écosystème : DIET_Webboard, VizDIET, GoDIET, LogService, MA_DAG, etc. Les résultats présentés ont été obtenus sur trois grilles mises à notre disposition: la grille universitaire du Décrypthon, la grille d'internautes (World Community Grid) et la grille expérimentale Grid'5000.

Les établissements de santé sont confrontés à de nouveaux défis tels que le vieillissement de la population, la hausse des coûts des soins et les progrès rapides des technologies médicales. Les nouvelles politiques de contrôle du budget des soins ont été introduites pour augmenter l'efficacité, réduire les déchets et remodeler le système de santé.Ces établissements cibles présentent des réseaux complexes incluant de ressources humaines,financières, structurelles et technologiques visant à garantir les meilleurs soins. Ces enjeux concernent d'autant plus les services d'urgence engorgés par l'afflux massif des passages, qui doivent fournir des décisions rapides et assurer le dimensionnement de ses ressources afin de réduire les délais d'attente des patients sans compromettre la qualité de soin.L'objectif de cette thèse est de proposer des solutions appropriées aux services d'urgences permettant d'améliorer la prise en charge des patients en termes de temps d'attente. Nous avons commencé par analyser les problématiques de la filière des urgences afin d'engager une démarche d'amélioration. Par la suite, nous avons modélisé le processus de prise en charge des patients au service d'accueil des urgences à l'aide d'un système multi-agent ouvert et dynamique. Le système proposé permet de fournir une aide à la décision sur la planification de l'activité médicale et l'affectation des ressources humaines dans une unité où on se trouve souvent face à une situation d'urgence nécessitant une prise en charge rapide et efficace. Dans ce contexte, nous abordons le problème réactif d'optimisation de l'ordonnancement des opérations de soin et le problème de coordination du personnel médical. Nous nous intéressons au dimensionnement des ressources humaines au SU en adoptant une approche de prise en compte des compétences maîtrisées dans le but de trouver une adéquation avec celles requises par l'activité médicale afin avant tout d'accroitre la qualité, réduire les délais d'attente et permettre de dégager des gains de gestion