Cette thèse est une contribution à une démarche globale de conception rationnelle des systèmes d'assemblage. Elle concerne plus précisément le problème de génération des graphes de précédence, en vue de leur utilisation par les méthodes d'équilibrage des systèmes d'assemblage. Le premier chapitre de ce travail est consacré à la description de la problématique des systèmes d'assemblage. Le deuxième chapitre présente un état de l'art des approches de génération des graphes de précédence pour l'assemblage. Les propriétés de ceux-ci sont listées et comparées à celles des autres modèles des processus d'assemblage. L'objectif du troisième chapitre est l'élaboration d'une méthode systématique d'obtention des graphes de précédence à partir d'un ensemble de gammes d'assemblage. Dans ce but, deux algorithmes sont proposés. Ils sont basés sur la vérification d'une propriété structurelle – la propriété ? – qui est nécessaire et suffisante pour assurer l'équivalence d'un ensemble de gammes à un seul graphe de précédence. Un état de l'art des méthodes de conception des systèmes d'assemblage issues de l'équilibrage des lignes d'assemblage est présenté dans le quatrième chapitre. Le problème d'équilibrage consiste à trouver l'affectation des tâches aux postes, telle qu'elle assure la minimisation du temps de cycle total. Une approche systémique est proposée par la formulation de ce problème comme problème d'optimisation discrète, en vue de la résolution par la programmation dynamique. Le dernier chapitre est dédié à l'analyse des systèmes d'assemblage avec auto-équilibrage, dont la conception évite la résolution d'un problème d'équilibrage classique. Il est suffisant qu'un tel système satisfasse une contrainte technologique simple de placement des opérateurs (humains) sur la ligne – du plus lent au plus rapide – pour qu'il atteigne spontanément un comportement optimal du point de vue de l'équilibrage. Une analyse par simulation de tels systèmes est présentée. Ils peuvent être traités comme systèmes dynamiques hybrides à commutations et sauts autonomes. La condition suffisante de l'autoéquilibrage – le "bon ordre" – est démontrée en utilisant les critères de stabilité des systèmes dynamiques discrets.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

L'objectif de ce mémoire est de fournir une nouvelle preuve pour la "Non-leaving face property" dans le cas An à l'aide de l'approximation dans les catégories amassées. Cette preuve ouvre la porte pour une généralisation pour d'autres cas.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse traite de l'étude des spanneurs multichemins, comme extension des spanneurs de graphes classiques. Un spanneur H d'un graphe G est un sous-graphe couvrant tel que pour toute paire de sommets du graphe a,b « appartient à » V(G) la distance dans le spanneur dh(a,b) n'est pas trop étirée par rapport à la distance dans le graphe d'origine dg(a,b). Ainsi il existe un facteur d'étirement (alpha, beta) tel que pour tout a,b« appartient à »V(G), dh(a,b)« est inférieur ou égal à » alpha dg(a,b)+beta. Motivés par des considérations de routage à plusieurs chemins et après la remarque que le concept de spanneur peut être étendu à toute métrique « non décroissante », nous introduisons la notion de spanneur multichemins. Après une introduction au domaine, nous parlerons des résultats obtenus concernant d'une part les spanneurs multichemins arêtes disjoints et d'autre part les spanneurs multichemins sommets disjoints. / This thesis deals with multipath spanners, as an extension of classical graph spanners. A spanner H of a graph G is a spanning subgraph such that for any pair of vertices a,b « is an element of » V(G) the distance measured in the spanner dh(a,b) isn't too much stretched compared to the distance measured in the original graph dg(a,b). As such there exists a stretch factor (alpha, beta) such that for all a,b« is an element of »V(G), dh(a,b)«is less than or equal to » alpha dg(a,b)+beta. Motivated by multipath routing and after noting that the concept of spanner can be extended to any “non decreasing” metric, we introduce the notion of multipath spanner. After an introduction to the topic, we will show the results obtained. The first part is devoted to edge-disjoint multipath spanners. The second part id devoted to vertex-disjoint spanners.

Des millions de réactions chimiques sont décrites dans des bases de données sous la forme de transformations de graphes moléculaires. Cette thèse propose différentes méthodes de fouille de donnés pour extraire des motifs pertinents contenus dans ces graphes et ainsi aider les chimistes à améliorer leurs connaissances des réactions chimiques et des molécules. Ainsi on commence par montrer comment le problème central de la recherche des schémas de réactions fréquents peut se résoudre à l'aide de méthodes existantes de recherche de sous-graphes fréquents. L'introduction du modèle général des motifs les plus informatifs permet ensuite de restreindre l'analyse de ces motifs fréquents à un nombre réduit de motifs peu redondants et représentatifs des données. Si l'application du modèle aux bases de réactions permet d'identifier de grandes familles de réactions, le modèle est inadapté pour extraire les schémas caractéristiques de méthodes de synthèse (schémas CMS) dont la fréquence est trop faible. Afin de surmonter cet obstacle, est ensuite introduite une méthode de recherche heuristique fondée sur une contrainte d’intervalle entre graphes et adaptée à l’extraction de motifs de très faible fréquence. Cette méthode permet ainsi de déterminer à partir d'exemples de réactions et sous certaines conditions le schéma CMS sous-jacent à une réaction donnée. La même approche est ensuite utilisée pour traiter le problème de la classification supervisée de sommets ou d'arêtes fondée sur leurs environnements puis exploitée pour évaluer la formabilité des liaisons d'une molécule. Les résultats produits ont pu être analysés par des experts de la synthèse organique et sont très encourageants. / Millions of chemical reactions are described in databases as transformations of molecular graphs. This thesis proposes different data-mining methods to extract relevant patterns included in those graphs and therefore to help chemists in improving knowledge about chemical reactions and molecules. One first shows how the central problem of searching frequent reaction patterns can be solved using existing graph-mining methods. Introducing the general model of most informative patterns then allows experts to reduce the analysis of these frequent patterns to a very small set of non-redundant patterns characteristic of data. If the application of this model to reaction database identifies large and characteristic families of reactions, the model doesn't allow in practice the extraction of reaction patterns characteristic of synthesis methods (abbr. CSM patterns) as their frequencies are far too low. In order to overcome this problem, is introduced a heuristic search algorithm based on a graph interval constraint and able to extract patterns with very low frequency. Thus this method determines from examples of chemical reactions and under some conditions the CSM pattern underlying a given input reaction. The same approach is then used to address the problem of supervised classification of vertices or edges based on their environment and then applied to evaluate formability of bonds in molecules. Experimental results have been analyzed by experts and are very encouraging.

L'interrogation de graphes de données est un problème fondamental qui connait un grand intérêt, en particulier pour les données structurées massives où les graphes constituent une alternative prometteuse aux bases de données relationnelles pour la modélisation des grandes masses de données. Cependant, l'interrogation des graphes de données est différente et plus complexe que l'interrogation des données relationnelles à base de tables. La tâche principale impliquée dans l'interrogation de graphes de données est la recherche d'isomorphisme de sous-graphes qui est un problème NP-complet.La recherche d'isomorphisme de sous-graphes est un problème très important impliqué dans divers domaines comme la reconnaissance de formes, l'analyse des réseaux sociaux, la biologie, etc. Il consiste à énumérer les sous-graphes d'un graphe de données qui correspondent à un graphe requête. Les solutions les plus connues de ce problème sont basées sur le retour arrière (backtracking). Elles explorent un grand espace de recherche, ce qui entraîne un coût de traitement élevé, notamment dans le cas de données massives.Pour réduire le temps et la complexité en espace mémoire dans la recherche d'isomorphisme de sous-graphes, nous proposons d'utiliser des graphes compressés. Dans notre approche, la recherche d'isomorphisme de sous-graphes est réalisée sur une représentation compressée des graphes sans les décompresser. La compression des graphes s'effectue en regroupant les sommets en super-sommets. Ce concept est connu dans la théorie des graphes par la décomposition modulaire. Il sert à générer une représentation en arbre d'un graphe qui met en évidence des groupes de sommets qui ont les mêmes voisins. Avec cette compression, nous obtenons une réduction substantielle de l'espace de recherche et par conséquent, une économie significative dans le temps de traitement.Nous proposons également une nouvelle représentation des sommets du graphe, qui simplifie le filtrage de l'espace de recherche. Ce nouveau mécanisme appelé compact neighborhood Index (CNI) encode l'information de voisinage autour d'un sommet en un seul entier. Cet encodage du voisinage réduit la complexité du temps de filtrage de cubique à quadratique. Ce qui est considérable pour les données massifs.Nous proposons également un algorithme de filtrage itératif qui repose sur les caractéristiques des CNIs pour assurer un élagage global de l'espace de recherche.Nous avons évalué nos approches sur plusieurs datasets et nous les avons comparées avec les algorithmes de l’état de l’art / Querying graph data is a fundamental problem that witnesses an increasing interest especially for massive structured data where graphs come as a promising alternative to relational databases for big data modeling. However, querying graph data is different and more complex than querying relational table-based data. The main task involved in querying graph data is subgraph isomorphism search which is an NP-complete problem. Subgraph isomorphism search, is an important problem which is involved in various domains such as pattern recognition, social network analysis, biology, etc. It consists to enumerate the subgraphs of a data graph that match a query graph. The most known solutions of this problem are backtracking-based. They explore a large search space which results in a high computational cost when we deal with massive graph data. To reduce time and memory space complexity of subgraph isomorphism search. We propose to use compressed graphs. In our approach, subgraph isomorphism search is achieved on compressed representations of graphs without decompressing them. Graph compression is performed by grouping vertices into super vertices. This concept is known, in graph theory, as modular decomposition. It is used to generate a tree representation of a graph that highlights groups of vertices that have the same neighbors. With this compression we obtain a substantial reduction of the search space and consequently a significant saving in the processing time. We also propose a novel encoding of vertices that simplifies the filtering of the search space. This new mechanism is called compact neighborhood Index (CNI). A CNI distills all the information around a vertex in a single integer. This simple neighborhood encoding reduces the time complexity of vertex filtering from cubic to quadratic which is considerable for big graphs. We propose also an iterative local global filtering algorithm that relies on the characteristics of CNIs to ensure a global pruning of the search space.We evaluated our approaches on several real-word datasets and compared them with the state of the art algorithms

Ce sujet de thèse concerne le développement d’analyse des propriétés structurelles en interaction avec des indicateurs de fiabilité. Notre étude porte sur des systèmes structurés (linéaire, bilinéaire ou linéaire à commutations), ces derniers doivent vérifier quelques propriétés importantes pour l’accomplissement de leur mission. Ces propriétés dépendent de la structure du système, d’où l’appellation "propriétés structurelles". La structure du système peut être représentée par un graphe composé de sommets et d’arcs. La vérification des propriétés structurelles dépend principalement de 4 conditions élémentaires de connectivité, de lien, de distance et de couplage complet. Nous avons développé des algorithmes permettant de les exprimer sous forme d’expressions booléennes basées sur les arcs du graphe représentant le système. Nous considérons que chaque arc est lié aux composants du système. Une défaillance au niveau des composants peut provoquer la modification de la structure du système, et donc peut rendre une propriété structurelle insatisfaite. Ainsi, les propriétés structurelles sont écrites sous forme d’expressions booléennes basées sur l’état de fonctionnement des composants. En utilisant les expressions booléennes associées aux propriétés structurelles, leur fiabilité et/ou disponibilité peut être calculée sachant les caractéristiques de sûreté de fonctionnement des composants du système. À travers cette étude, nous pouvons vérifier si, pendant le temps de mission du système, une propriété structurelle restera satisfaite et/ou respectera un niveau de performance exigé par un cahier des charges. / This thesis concerns the development of analysis of structural properties in interaction with indicators of reliability. Our study focuses on (linear, bilinear or switching) structured systems, they must verify some important properties for the accomplishment of their mission. Properties depend on the structure of the system, hence the term "structural properties". The structure of the system can be represented by a graph consisting of vertices and edges. Verification of structural properties depends mainly on four basic conditions of connectivity, link distance and complete linkage. We have developed algorithms to express the form of Boolean expressions based on the edges of the graph representing the system. We consider that each edge is linked to the system components. A failure at the component level can cause changes in the structure of the system, and therefore can make a structural property unsatisfied. Thus, the structural properties are written as boolean expressions based on the operating state of the components. Using boolean expressions associated to the structural properties, reliability and / or availability can be calculated knowing the characteristics of the system components. Through this study, we can check if during the mission time of the system, a structural property remain satisfied and / or comply with a level of performance required by the specifications

La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retournant une solution optimale mais dont l'explosion combinatoire est capturée par un paramètre de l'entrée bien choisi. Cette thèse comporte deux objectifs. Dans un premier temps, nous proposons d'étudier et d'appliquer les méthodes classiques de ces deux domaines afin d'obtenir des résultats positifs et négatifs pour deux problèmes d'optimisation dans les graphes : un problème de partition appelé Sparsest k-Compaction, et un problème de recherche d'un sous-graphe avec une cardinalité fixée appelé Sparsest k-Subgraph. Dans un second temps, nous présentons comment les méthodes de ces deux domaines ont pu se combiner ces dernières années pour donner naissance au principe d'approximation paramétrée. En particulier, nous étudierons les liens entre approximation et algorithmes de noyaux. / The theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms.

Les réseaux phylogénétiques généralisent le modèle de l'arbre pour décrire l'évolution, en permettant à des arêtes entre les branches de l'arbre d'exprimer des échanges de matériel génétique entre espèces coexistantes. De nombreuses approches combinatoires - fondées sur la manipulation d'ensembles finis d'objets mathématiques - ont été conçues pour reconstruire ces réseaux à partir de données extraites de plusieurs arbres de gènes contradictoires. Elles se divisent en plusieurs catégories selon le type de données en entrées (triplets, quadruplets, clades ou bipartitions) et les restrictions de structure sur les réseaux reconstruits. Nous analysons en particulier la structure d'une classe de réseaux restreints, les réseaux de niveau k, et adaptons ce paramètre de niveau au contexte non enraciné. Nous donnons aussi de nouvelles méthodes combinatoires pour reconstruire des réseaux phylogénétiques, à partir de clades - méthode implémentée dans le logiciel Dendroscope - ou de quadruplets. Nous étudions les limites de ces méthodes combinatoires (explosion de complexité, bruit et silence dans les données, ambiguïté des réseaux reconstruits) et la façon de les prendre en compte, en particulier par un pré-traitement des données. Finalement, nous illustrons les résultats de ces méthodes de reconstruction sur des données réelles avant de conclure sur leur utilisation dans une méthodologie globale qui intègre des aspects statistiques. / Phylogenetic networks generalize the tree concept to model Evolution, by allowing edges between branches inside the tree to reflect genetic material exchanges between coexisting species. Lots of combinatorial approaches have been designed to reconstruct networks from data extracted from a set of contradictory gene trees. These approaches can be divided into several categories depending on the kind of input, i.e. triplets, quartets, clusters and splits, and on the kind of structure restrictions they impose on reconstructed networks.We particularly analyze the structure of one class of such restricted networks, namely level-k phylogenetic networks, and adapt this level parameter to the unrooted context. We also give new combinatorial methods to reconstruct phylogenetic networks from clusters - implemented in Dendroscope - or quartets. We study the limits of combinatorial methods (complexity explosion, noise and silence in the data, ambiguity in the reconstucted network), and the way to tackle them, in particular with an appropriate data preprocessing. Finally we illustrate the results of these reconstruction methods on a dataset, and we conclude on how to use them in a global methodology which integrates statistical aspects.