Les travaux de recherche effectués dans le cadre de cette thèse concernent essentiellement la conception en avant-projet de systèmes d'usinage dédiés à la production en grande série. Lors de cette phase de conception, l'objectif principal est de trouver, pour une pièce donnée, une configuration du système d'usinage qui satisfaisait, à coût minimal, les contraintes technologiques, techniques et économiques existantes. Plusieurs problèmes combinatoires posés par cet objectif sont étudiés dans la thèse. Plus concrètement, nous nous sommes intéressés aux problèmes d'optimisation de la configuration des trois types de systèmes d'usinage suivants : machines de transfert, machines à table mobile et machines à table circulaire pivotante. Pour chacun de ces systèmes, nous avons proposé, dans un premier temps, différents modèles mathématiques. Dans un deuxième temps, nous avons développé de nombreux outils d'optimisation dédiés à leur résolution, tels que des algorithmes de calcul des bornes inférieures, des procédures de pré-traitement, des algorithmes de résolution exacte et approchée, et des approches mixtes utilisant plusieurs de ces algorithmes. Ces travaux ont permis de concevoir un prototype de logiciel destiné à supporter les différentes étapes de conception en avant projet d'un système d'usinage. Ce logiciel a été testé avec succès sur plusieurs cas industriels.

Les réseaux techniques sont des infrastructures critiques qui peuvent être vulnérables aux inondations. Leur bon fonctionnement représente donc un enjeu majeur pour la gestion des risques et des territoires. Cette recherche postule que l'analyse de la résilience des réseaux techniques constitue un préalable nécessaire, mais non suffisant, à la mise en place de politiques d'amélioration de la résilience urbaine face aux inondations. Une méthodologie d'analyse de la résilience des réseaux techniques est proposée. Elle requiert l'analyse des capacités de résistance, d'absorption et de récupération de ces réseaux. Dans ce cadre, des développements ont été réalisés afin d'analyser les propriétés structurelles des réseaux techniques, les interdépendances entre les réseaux techniques et la remise en service de ces réseaux. Ces développements reposent principalement sur la théorie des graphes, les méthodes issues de la Sûreté de Fonctionnement, l'optimisation linéaire et l'analyse spatiale. Enfin, un prototype web-SIG a été développé puis appliqué à la ville de Dublin.

On se propose, dans cette étude, de montrer l'apport nouveau de la théorie des sous-ensembles flous dans le domaine de l'analyse de la décision. Dans un premier temps, on la démarque de celle des probabilités, et des probabilités subjectives en particulier, puis on étudie certaines applications des sous-ensembles flous a la prise de décision et a l'analyse structurale. On discute, ensuite, l'opportunité de l'emploi des opérateurs min et max, dans le cas d'une décision floue. Puis on présente une méthode topologique de la construction de la fonction d'appartenance. On présente ensuite une méthode d'analyse structurale basée sur des techniques floues, au lieu de la théorie des graphes, puis on étudie l'entropie floue et on la compare à l'entropie probabiliste au sens de Shannon.

Cette thèse considère principalement trois problèmes dans le domaine du contrôle distribué coopératif des systèmes multi-agents(SMA): le consensus, la navigation en formation et le maintien en formation d'un groupe d'agents lorsqu'un agent disparait. Nous proposons 3 algorithmes pour résoudre le problème du calcul distribué d'un consensus à partir de l'approche leadeur-suiveur dans le contexte SMA à dynamique non-linéaire. La référence est définie comme un leader virtuel dont on n'obtient, localement, que les données de position et de vitesse. Pour résoudre le problème du suivi par consensus pour les SMA à dynamique non-linéaire, nous considérons le suivi par consensus pour SMA de premier ordre. On propose des résultats permettant aux suiveurs de suivre le leadeur virtuel en temps fini en ne considérant que les positions des agents. Ensuite, nous considérons le suivi par consensus de SMA de second. Dans le cas de la planification de trajectoire et la commande du mouvement de la formation multi-agents. L'idée est d'amener la formation, dont la dynamique est supposée être en 3D, d'une configuration initiale vers une configuration finale (trouver un chemin faisable en position et orientation) en maintenant sa forme tout le long du chemin en évitant les obstacles. La stratégie proposée se décompose en 3 étapes. Le problème du Closing-Rank se traduit par la réparation d'une formation rigide multi-agents "endommagée" par la perte de l'un de ses agents. Nous proposons 2 algorithmes d'autoréparation systématique pour récupérer la rigidité en cas de perte d'un agent. Ces réparations s'effectuent de manière décentralisée et distribuée n'utilisant que des informations de voisinage.

L'objectif de notre travail est la réalisation d'un système interactif d'aide aux déplacements, en mode normal, et en mode dégradé de fonctionnement du réseau de transport en commun. Ce système vise par ailleurs à minimiser le temps d'attente des voyageurs, en mode dégradé, dans les pôles d'échanges et à leur assurer, dans la mesure du possible, la continuité des déplacements dans les réseaux multimodaux. Il s'agit donc d'améliorer la qualité du service rendu aux voyageurs et les maintenir informés. Une grande partie du travail de cette thèse concerne la conception, le développement et la validation des approches qui permettent de donner des solutions optimales ou quasi optimales, pour un réseau de transport normal et perturbé. Ces approches utilisent une méthode multicritère de recherche d'itinéraire qui s'appuie sur une hybridation entre un algorithme de Dijkstra modifié et un algorithme génétique, pour générer une population de chemins minimums . L'algorithme de Dijkstra modifié nous donne un ensemble de solutions servant de population initiale pour l'algorithme génétique.<br />La modélisation du réseau de transport est représentée par une architecture multi-zones . Cette architecture nous montre l'aspect distribué du système, les interactions et les relations qui peuvent avoir lieu entre les différenttes zones. Nous présentons dans ce travail un Système Multi-Agent d'Aide au Déplacement, SMAAD. Les agents de ce système utilisent le module d'optimisation développé dans la première partie. Notre travail est réalisé dans le cadre du projet « VIATIC-MOBILITE », qui est le projet 6 du pôle de compétitivité I-Trans.

Soit G = (V, E) un graphe simple fini. Soit (a, b) un couple d’entiers positifs. On note par τ(G) le nombre de sommets d’un chemin d’ordre maximum dans G. Une partition (A,B) de V(G) est une (a,b)−partition si τ(⟨A⟩) ≤ a et τ(⟨B⟩) ≤ b. Si G possède une (a, b)−partition pour tout couple d’entiers positifs satisfaisant τ(G) = a+b, on dit que G est τ−partitionnable. La conjecture de partitionnement des chemins, connue sous le nom anglais de Path Partition Conjecture, cherche à établir que tout graphe est τ−partitionnable. Elle a été énoncée par Lovász et Mihók en 1981 et depuis, de nombreux chercheurs ont tenté de démontrer cette conjecture et plusieurs y sont parvenus pour certaines classes de graphes. Le présent mémoire rend compte du statut de la conjecture, en ce qui concerne les graphes non-orientés et ceux orientés. / Let G = (V,E) be a finite simple graph. We denote the number of vertices in a longest path in G by τ(G). A partition (A,B) of V is called an (a,b)−partition if τ(⟨A⟩) ≤ a and τ(⟨B⟩) ≤ b. If G can be (a,b)−partitioned for every pair of positive integers (a, b) satisfying a + b = τ (G), we say that G is τ −partitionable. The following conjecture, called The Path Partition Conjecture, has been stated by Lovász and Mihók in 1981 : every graph is τ−partitionable. Since that, many researchers prove that this conjecture is true for several classes of graphs and digraphs. This study summarizes the different results about the Path Partition conjecture.

Cette thèse est une contribution à la modélisation imbriquée de systèmes complexes. Elle propose une méthodologie globale pour quantifier les incertitudes et leurs origines dans une chaîne de calcul formée par plusieurs modèles pouvant être reliés les uns aux autres de façon complexe. Ce travail est organisé selon trois axes. D'abord, la structure dedépendance des paramètres du modèle, induite par la modélisation imbriquée, est modélisée de façon rigoureuse grâce à la théorie des copules. Puis, deux méthodes d'analyse de sensibilité adaptées aux modèles à paramètres d'entrée corrélés sont présentées : l'une est basée sur l'analyse de la distribution de la réponse du modèle, l'autre sur la décomposition de la covariance. Enfin, un cadre de travail inspiré de la théorie des graphes est proposé pour la description de l'imbrication des modèles. La méthodologie proposée est appliquée à des exemples industriels d'envergure : un modèle multiéchelles de calcul des propriétés mécaniques du béton par une méthode d'homogénéisation et un modèle multiphysique de calcul de dommage sur la culasse d'un moteur diesel. Les résultats obtenus fournissent des indications importantes pour une amélioration significative de la performance d'une structure.

Les travaux présentés dans ce document traitent des codes identifiants dans les graphes. Cette notion, introduite à la fin des années 1990, modélise des problèmes de détection de défaillance dans les réseaux. Un code identifiant peut être vu comme une variante du problème de domination, avec une contrainte supplémentaire d'identification des sommets. La recherche de la cardinalité minimum d'un tel code est un problème NP-difficile. Les résultats obtenus sont regroupés en quatre grands thèmes. Le premier thème concerne les structures régulières (grilles, cycles, hypercubes, produits de cliques, graphes de Sierpiński), pour lesquels des résultats sur la cardinalité minimum d'un code sont présentés (bornes et valeurs exactes). Ensuite, les aspects algorithmiques sont développés, que ce soit au sujet de la recherche d'algorithmes polynomiaux pour des classes de graphes particulières (arbres, fasciagraphes) ou concernant l'approximabilité du problème. Quelques questions structurelles sont ensuite discutées, notamment la construction de graphes extrémaux pour le problème, la construction de familles de graphes admettant un code identifiant de faible cardinalité, et la structure (degrés, sous-graphes, etc.) des graphes admettant un tel code. Enfin, une nouvelle variante de ces codes est présentée, les codes identifiants adaptatifs. Cette variante permet de modéliser une situation où nous pouvons tirer parti de l'aspect dynamique du problème, et espérer interroger un nombre de sommets bien moins grand que dans le cas statique. Nous explicitons en particulier dans ce document les liens qu'entretiennent les codes identifiants avec d'autres types de structures, tels les ensembles dominants, les codes superposés, les plans projectifs, ou les jeux de Rényi.

Les travaux de recherche concernant l'ordonnancement mobilisent un nombre important de chercheurs. Cette forte émulation est principalement due au large panorama des problématiques d'ordonnancement. Parmi elles, le problème d'atelier à cheminement multiple, communément appelé " Job-Shop ", tient une place particulièrement prépondérante tant ce problème est rencontré dans le milieu industriel. De nombreux sujets de recherche, en France et à l'étranger, sont issus de cette problématique. Les problèmes de Job-Shop peuvent souvent être simplifiés en les considérant comme des problèmes cycliques. L'ordonnancement des tâches devient ainsi cyclique et son objectif est d'organiser les activités de production en répétant un cycle de base que l'on a optimisé. De nombreux paramètres entrent en jeu dans l'optimisation du cycle de base tels que la période du cycle choisie, l'ordre des opérations élémentaires pour réaliser un travail, la durée de ces opérations, le nombre de produits à réaliser par cycle, etc. Plusieurs approches ont été utilisées pour résoudre ce problème. Parmi elles, nous pouvons citer l'approche par réseaux de Petri et plus particulièrement par graphes d'événements temporisés, l'approche par les graphes, l'approche par la programmation linéaire et l'approche par la théorie des tas. L'approche par les graphes permet une représentation graphique du problème sous forme d'un graphe où les noeuds représentent les différentes opérations et où les arcs illustrent les contraintes du problème d'ordonnancement cyclique, un tel problème admet une solution réalisable si, et seulement si, le graphe associé est consistant. Cette propriété de consistance d'un problème d'ordonnancement cyclique et de son graphe permet d'élaguer l'arbre de recherche de la procédure de séparation et d'évaluation proposée pour cette approche. Concernant l'approche par la théorie des tas, le sous-problème de l'évaluation d'une solution peut être résolu aisément avec l'aide de la théorie des tas. En effet, en traduisant le problème dans une structure mathématique adaptée, l'évaluation du taux de production du cycle revient au calcul d'une valeur propre d'un produit de matrices dans lequel chacune des matrices représente une opération élémentaire. Cette propriété s'avère particulièrement intéressante dans le cas de l'évaluation successive d'un grand nombre d'ordonnancement. En outre, la théorie des tas permet une représentation très intuitive d'un ordonnancement, puisque celui-ci s'illustre comme un empilement de plusieurs briques (en fait, un " tas " de briques) dont le contour supérieur correspond aux dates de fin des dernières opérations des machines.

Dans cette thèse, nous étudions des problèmes d'identification des sommets dans les graphes. Identifier les sommets d'un graphe consiste à attribuer à chaque sommet un objet qui rend le sommet unique par rapport aux autres. Nous nous intéressons particulièrement aux codes identifiants : sous-ensembles de sommets d'un graphe, dominants, tels que le voisinage fermé de chaque sommet du graphe a une intersection unique avec l'ensemble. Les sommets du code identifiant peuvent être considérés comme des capteurs et chaque sommet du graphe comme un lieu possible pour une défaillance. Nous caractérisons tout d'abord l'ensemble des graphes pour lesquels tous les sommets sauf un sont nécessaires dans tout code identifiant. Le problème consistant à trouver un code identifiant optimal, c'est-'a-dire de taille minimale, étant NP-difficile, nous l'étudions sur quatre classes restreintes de graphes. Suivant les cas, nous pouvons résoudre complètement le problème (pour les graphes de Sierpinski), améliorer les bornes générales (pour les graphes d'intervalles, les graphes adjoints, la grille du roi) ou montrer que le problème reste difficile même restreint (pour les graphes adjoints). Nous considérons ensuite des variations autour des codes identifiants permettant plus de flexibilité pour les capteurs. Nous étudions par exemple des capteurs du plan capables de détecter des défaillances 'a un rayon connu avec une erreur tolérée. Nous donnons des constructions de tels codes et bornons leur taille pour des valeurs de rayons et d'erreurs fixés ou asymptotiques. Nous introduisons enfin la notion de coloration identifiante d'un graphe, permettant d'identifier les sommets d'un graphe avec les couleurs présentes dans son voisinage. Nous comparons cette coloration avec la coloration propre des graphes et donnons des bornes sur le nombre de couleurs nécessaires pour identifier un graphe, pour plusieurs classes de graphes.