Au cours de ces dernières décennies, les systèmes technologiques ont beaucoup évolué. Dans le même temps, leurs installations sont de plus en plus distribuées sur plusieurs sites. Ceci conduit à la résolution de problèmes logistiques lors des prises de décision en vue d'actions de maintenance qui exigent par ailleurs des approches coopératives dans un contexte de gestion à distance. Dans ce travail, nous étudions des méthodes d'aides à la décision temps-réel pour la maintenance des systèmes multi-sites distribués dans un environnement à ressources partagées, avec des contraintes logistiques non négligeables entre les différents sites. Les exigences sont de planifier et d'ordonnancer les tâches de maintenance, de les affecter en temps-réel aux ressources de maintenance disponibles, tout en minimisant les coûts inhérents au fonctionnement et en maîtrisant les délais d'intervention des ressources. Les coûts sont relatifs notamment au fonctionnement en état dégradé (état critique), aux fréquences trop élevées ou au déficit de maintenance. Ils dépendent aussi de combinaisons linéaires ou convexes d'ensemble de paramètres tels que les temps de réponse (temps de séjour), les retards et avances ainsi que des facteurs de pondération des tâches de maintenance. Les coûts sont également fonction de la disponibilité, cette dernière étant révélatrice des dégradations des entités constituant le système. Pour satisfaire ces exigences, différents problèmes doivent être résolus dans le but de maintenir la disponibilité du système au dessus d'une limite minimale, de minimiser le coût des opérations de maintenance et d'affecter en temps-réel les tâches aux ressources de maintenance, le tout dans un processus optimal de décision. Ce processus doit tenir compte de différentes contraintes : dates d'arrivée inégales des tâches, temps logistiques non négligeables entre les sites, séquences optimales des tâches d'une intervention, précédences entre les tâches d'une même entité et critères de priorité et d'urgence de chaque tâche. Dans cette démarche, les caractéristiques et lois de comportement en fiabilité et en maintenabilité, et les sollicitations d'intervention sur les entités sont connues. Pour résoudre ces problèmes, nous proposons une approche mettant en oeuvre des méthodes d'ordonnancement d'activités (tâches ou actions) de maintenance basées sur des règles de priorité dont nous montrons l'optimalité locale (par rapport au temps) dans ce document. Partant d'une ressource de maintenance, ces règles de décision s'inspirent des principes d'ordonnancement sur une seule machine. Elles sont utilisées dans des algorithmes d'aide à la décision en temps-réel pour la planification dynamique des tâches de maintenance des systèmes distribués. Aux solutions fournies par la plupart de ces règles nous avons déterminé des bornes inférieures. Nous avons structuré ce document en six chapitres dont le premier introduit de façon générale la maintenance et ses différentes pratiques dans les entreprises. Le chapitre 2 propose une analyse de l'état de l'art des travaux de recherche scientifique dans le domaine de la gestion des activités de maintenance. Ensuite, dans le chapitre 3, des approches de résolution des problèmes relatifs aux coûts des états critiques du système sont proposées. Le chapitre 4 traite alors les différents problèmes relatifs aux contraintes de délais sur les opérations de maintenance induisant notamment des coûts combinés liés aux états critiques et aux retards d'intervention d'une part, et des coûts dus aux avances ou retards des tâches d'autre part. Il apparut alors nécessaire d'étudier la robustesse des performances des approches proposées dans les chapitres 3 et 4 en environnements incertains. Cette étude fût donc réalisée dans le chapitre 5 par des simulations Monte Carlo de la maintenance à partir des données d'un système réel soumis à des aléas de défaillance appelant des actions correctives. Enfin, de l'ensemble des investigations menées dans ce travail furent tirées les principales conclusions et les perspectives proposées dans le chapitre 6.

Le cadre de ce travail est l'étude coordonnée de lois de contrôle et d'ordonnancement. Le premier objectif est de proposer et évaluer une approche de contrôle de la dégradation de la Qualité de Contrôle (QdC) par rejet sélectif d'instances de tâches ou de messages selon le<br />modèle (m,k)-firm. Plus particulièrement, nous avons étudié l'impact de distribution de rejets sur la QdC d'une boucle de contrôle et, sur la base des résultats obtenus, nous avons spécifié une méthode de co-conception permettant de déterminer les paramètres (gain) optimaux de la loi de contrôle et les paramètres de la contrainte (m,k)-firm spécifiant le rejet sélectif d'instances. Cette proposition a été validée sur modèles à l'aide de techniques analytiques, par simulation ainsi que grâce à des expérimentations. Notre deuxième objectif est d'étudier le problème de l'ordonnancement d'un ensemble de tâches temps réel réalisant chacune les algorithmes de contrôle dans une application centralisée évolutive. Nous proposons un mécanisme d'ordonnancement qui ajuste en ligne les contraintes<br />(m,k)-firm des tâches suivant la configuration courante de l'application de manière à ce qu'un critère reflétant la performance globale de l'application soit optimal à tout instant.

Un objet multiboîte est composé de plusieurs parties identiques qui doivent être rangées dans des boîtes différentes. La hauteur d'une boîte est alors la somme des hauteurs des objets qu'elle contient. Ce concept généralise et englobe de nombreux problèmes de la littérature de la recherche opérationnelle.<br /><br />Une classification de ces modèles est proposée. Les bases théoriques sont posées. En particulier, la complexité pour les principaux types d'objets et objectifs est déterminée.<br /><br />Une étude détaillée est effectuée lorsque les objets ont des largeurs constantes et que l'on veut minimiser la hauteur de la boîte la plus haute. Des bornes inférieures, des heuristiques avec de très bonnes garanties de performance et un algorithme génétique sont proposés pour résoudre ce modèle. Leurs comportements théoriques et expérimentaux sont analysés.

Cette thèse porte sur la construction d'algorithmes et de programmes parallèles qui s'adapte automatiquement à la plate-forme d'exécution (nombre de processeurs, vitesses des processeurs, ...) et ce, de manière dynamique inconsciente (en anglais oblivious). La construction que nous proposons est basée sur la technologie développée au sein de l'équipe Moais consistant au couplage récursif et dynamique : d'un algorithme séquentiel (qui minimise le nombre d'opérations, mais pas le temps parallèle) ; et d'un algorithme parallèle à grain fin (qui minimise le temps parallèle sur un nombre non borné de ressources, mais pas le nombre d'opérations). Les deux algorithmes sont entrelacés à la volée par un ordonnancement à grain fin de type vol de travail. Outre une analyse théorique du couplage (borne inférieure, optimalité asymptotique), nous proposons une implantation " générique " que nous instancions sur différents exemples (un nouvel algorithme parallèle adaptatif de calcul des préfixes, algorithmes adaptatifs de fusion, de partition et tris, plusieurs algorithmes adaptatifs de la librairie standard C++). Dans cette thèse, nous proposons aussi un nouvel algorithme parallèle statique optimal du calcul des préfixes.

L'objet de cette thèse est l'étude de la parallélisation d'algorithmes du calcul scientifique et<br />leur implémentation sur des ordinateurs parallèles à mémoire partagée et sur des réseaux systoliques.<br /> Un accent particulier est mis sur l'obtention de résultats de complexité. La thèse est organisée autour<br /> d'articles et textes de conférences qui sont analysés et discutés dans une première partie de façon à <br />permettre de replacer les problèmes traités dans leur contexte.<br />Dans le premier chapitre, nous présentons les principaux résultats théoriques concernant <br />l'étude de complexité des algorithmes parallèles, ainsi qu'une description critique de l'architecture <br />de référence, qui est une machine de type MIMD à mémoire partagée. Le chapitre suivant est dédie" à <br />l'ensemble des résultats de complexité concernant les algorithmes de diagonalisation et <br />l'élimination de Gauss, il a pour but d'illustrer la méthodologie. Il existe en tout dix écritures possibles de la méthode de Gauss, qui conduisent principalement à deux grandes classes de graphes de précédente, conceptuellement différents : les graphes de type "glouton" et ceux du type "2 pas".<br />Ces types de graphes se rencontrent d'une manière plus générale dans d'autres problèmes <br />d'algèbre linéaire et même dans certaines méthodes non numériques de la théorie des graphes. <br />Nous développons les résultats de complexité concernant ces deux types de graphes sur les exemples<br /> les plus courant (versions kji et kij de Gauss en parallèle), puis nous montrons comment adapter<br /> l'étude en prenant en compte t'es temps de communication entre tes processeurs, ce qui rend le modèle<br /> théorique plus réaliste.<br />Le chapitre 6 est consacré aux architectures systoliques. Le problème du chemin algébrique permet <br />d'unifier plusieurs problèmes informatiques. Nous présentons un réseau résolvant ce problème en Sn-2 <br />pas sur un réseau de taille n(n+l ). De plus, quelques modifications permettent de calculer des projections<br /> en filtrage adaptatif en vu d'obtenir une solution en temps réel pour le traitement numérique des signaux.<br />Avant de conclure, nous présentons des résultats complémentaires de parallélisation effective sur d'autres<br /> types d'architectures : l'étude de l'algorithme du gradient conjugué sur des super calculateurs <br />(CRAY-XMP et IBM 3090-VF).

Etude de certains problèmes liés aux ordonnancements et à leur implantation sur micro-ordinateur. Dans une première partie on s'intéresse à des problèmes d'ordonnancement à contraintes potentielles avec des spécificités données. Dans la seconde partie, on étudie diverses représentations géographiques des résultats (variantes de la méthode de Gantt), qui se feront sur un nombre minimun de lignes. Dans la dernière partie on s'intéresse aux problèmes d'ordonnancement à contraintes disjonctives

Cette thèse s'inscrit dans le cadre des grappes dans le projet Grid'5000 (Projet Français pour les grilles). Grid'5000 est une plate-forme expérimentale qui offre la possibilité aux chercheurs de soumettre aux gestionnaires de ressource des programmes (travaux) et d'associer pour chaque requête un environnement. Une grappe est un ensemble de noeuds de calcul, connectés entre eux via un réseau dédié. Le processus de déploiement d'environnement sur les noeuds de calcul n'est pas sans conséquence. Un des problèmes que l'on rencontre est la défaillance des machines. Le démarrage excessif lors de de la phase déploiement peut causer un endomagement de celles-ci. Nous avons ainsi modélisé ce problème sous forme d'un problème d'ordonnancement bicritère. Le premier critère à minimiser comptabilise pour chaque machine (processeur) le nombre de déploiements effectués. Il permet ainsi permet de définir le nombre total de déploiements sur toutes les machines. Nous avons également considéré un second critère à minimiser, le makespan. Nous avons défini un algorithme Groups List Scheduling, basé sur une approche budget, avec un relâchement des contraintes d'optimalité. Cette approche nous a permis de définir une solution (alpha, beta)-budget-relaxée-approchée pour un problème d'optimisation bicritère. Dans le cadre du problème d'ordonnancement bicritère avec déploiement, l'algorithme GLS donne ainsi une solution (4,2)-budget-approchée-relaxée. Nous avons ensuite abordé ce problème d'ordonnancement bicritère avec déploiement en utilisant l'approche «courbe de Pareto». Nous avons défini un algorithme polynômial, qui permet de construire une courbe de Pareto (4+epsilon, 2)-approchée, à partir des solutions fournies par l'algorithme GLS. Une analyse expérimentale nous a permis d'évaluer les performances de l'algorithme GLS et de valider ainsi les rapports

LRO et EAQUE constituent un environnement pour générer des systèmes experts. Un noyau important existe, à la fois pour définir une certaine représentation des connaissances (LRO, langage oriente objet), et pour définir une structure de contrôle appropriée (EAQUE, moteur d'inférence). Pour chaque instantiation du système EAQUE-LRO a une application particulière, les interfaces adéquates sont écrites par l'ingénieur cognitif, après dialogue avec les experts du domaine. Eaque a été instancié pour des problèmes d'ordonnancement (ORDF), pour la simplification d'expressions mathématiques (CALINT), et pour simuler un interpréteur PROLOG (EALOG).

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.

.