Orienter un graphe c'est remplacer chaque arête par un arc de mêmes extrémités. On s'intéresse à la connexité du graphe orienté ainsi obtenu. L'orientation avec des contraintes d'arc-connexité est maintenant comprise en profondeur mais très peu de résultats sont connus en terme de sommet-connexité. La conjecture de Thomassen avance que les graphes suffisament sommet-connexes ont une orientation k-sommet-connexe. De plus, la conjecture de Frank propose une caractérisation des graphes qui admettent une telle orientation. Les résultats de cette thèse s'articulent autour des notions d'orientation, de packing, de connexité et de matroïde. D'abord, nous infirmons une conjecture de Recski sur la décomposition d'un graphe en arbres ayant des orientations avec degrés entrants prescrits. Nous prouvons également un nouveau résultat sur le packing d'arborescences enracinées avec contraintes de matroïdes. Ceci généralise un résultat fondamental d'Edmonds. Enfin, nous démontrons un nouveau théorème de packing sur les bases des matroïdes de dénombrement qui nous permet d'améliorez le seul résultat connu sur la conjecture de Thomassen. D'autre part, nous donnons une construction et un théorème d'augmentation pour une famille de graphes liée à la conjecture de Frank. En conclusion, nous réfutons la conjecture de Frank et prouvons que, pour tout entier k >= 3, décider si un graphe a une orientation k-sommet-connexe est un problème NP-complet. / Orienting an undirected graph means replacing each edge by an arc with the same ends. We investigate the connectivity of the resulting directed graph. Orientations with arc-connectivity constraints are now deeply understood but very few results are known in terms of vertex-connectivity. Thomassen conjectured that sufficiently highly vertex-connected graphs have a k-vertex- connected orientation while Frank conjectured a characterization of the graphs admitting such an orientation. The results of this thesis are structures around the concepts of orientation, packing, connectivity and matroid. First, we disprove a conjecture of Recski on decomposing a graph into trees having orientations with specified indegrees. We also prove a new result on packing rooted arborescences with matroid constraints. This generalizes a fundamental result of Edmonds. Moreover, we show a new packing theorem for the bases of count matroids that induces an improvement of the only known result on Thomassen's conjecture. Secondly, we give a construction and an augmentation theorem for a family of graphs related to Frank's conjecture. To conclude, we disprove the conjecture of Frank and prove that, for every integer k >= 3, the problem of deciding whether a graph admits a k-vertex-orientation is NP-complete.

Prédire à l’avance quels composés seront toxiques chez l’homme ou non représente un réel challenge dans le monde pharmaceutique. En effet, les mécanismes à l’origine de la toxicité ne sont pas toujours bien connus, et à cela s’ajoute le fait qu’un composé peut devenir néfaste seulement après qu’il ait été métabolisé. Nous proposons ici une approche originale utilisant les graphes condensés de réactions afin de modéliser les réactions métaboliques et prédire le devenir des xénobiotiques dans l’organisme humain. Différentes formes de toxicité sont aussi prédites : la mutagénicité et l’hépatotoxicité. Pour cette seconde toxicité, l’approche utilisée est la première à notre connaissance à prédire avec succès les molécules toxiques décrites par des données autres que résultant d’observations in vivo. / Predict in advance which compounds will be toxic in humans or not is a real challenge in the pharmaceutical world. Indeed, the mechanisms responsible for toxicity are not always well known, and in some case a compound become toxic only after it has been metabolized. We propose here a novel approach using condensed graphs of reactions to model and predict the metabolic fate of xenobiotics in the human body. Various forms of toxicity are also predicted : mutagenicity and hepatotoxicity. For this second toxicity, the approach proposed is the first to our knowledge to successfully predict the toxic molecules described by data other than resulting from observations in vivo.

Ce travail introduit un ensemble de solutions pour extraire des graphes à partir des données de l'entreprise et pour aussi faciliter le processus de recherche d'information dans ces graphes. Premièrement, nous avons défini un nouveau modèle de données appelé SPIDER-Graph permettant de modéliser des objets complexes et de définir des graphes hétérogènes. Puis, nous avons développé un ensemble d'algorithmes pour extraire le contenu des bases de données de l'entreprise et les transformer suivant ce nouveau modèle de graphe. Cette représentation permet de mettre à jour des relations non explicites entre objets, relations existantes mais non visibles dans le modèle relationnel. Par ailleurs, pour unifier la représentation de toutes les données dans l'entreprise, nous avons développé, dans une deuxième approche, une méthode de constitution d’une ontologie d'entreprise contenant les concepts et les relations les plus importantes d'une entreprise, et ceci, à partir de l’extraction des données non structurés de cette même entreprise. Ensuite, après le processus d'extraction des différents graphes de données l'entreprise, nous avons proposé une approche qui permettent d'extraire des graphes d'interactions entre des objets hétérogènes modélisant l'entreprise. Cette approche permet d'extraire des graphes de réseaux sociaux ou des graphes d'interactions. Ensuite, nous avons proposé un nouveau langage d'interrogation visuel appelé GraphVQL ( Graph Visual Query Langauge) qui permet aux utilisateurs non experts de poser leurs requêtes visuellement sous forme de patron de graphe. Ce langage propose plusieurs types de requêtes de la simple sélection et agrégation jusqu'à l'analyse des réseaux sociaux. Il permet aussi d'interroger différent type de graphes SPIDER-Graph, RDF ou GraphML en se basant sur des algorithmes de pattern matching ou de translation des requêtes sous forme de SPARQL. / The present work introduces a set of solutions to extract graphs from enterprise data and facilitate the process of information search on these graphs. First of all we have defined a new graph model called the SPIDER-Graph, which models complex objects and permits to define heterogeneous graphs. Furthermore, we have developed a set of algorithms to extract the content of a database from an enterprise and to represent it in this new model. This latter representation allows us to discover relations that exist in the data but are hidden due to their poor compatibility with the classical relational model. Moreover, in order to unify the representation of all the data of the enterprise, we have developed a second approach which extracts from unstructured data an enterprise's ontology containing the most important concepts and relations that can be found in a given enterprise. Having extracted the graphs from the relational databases and documents using the enterprise ontology, we propose an approach which allows the users to extract an interaction graph between a set of chosen enterprise objects. This approach is based on a set of relations patterns extracted from the graph and the enterprise ontology concepts and relations. Finally, information retrieval is facilitated using a new visual graph query language called GraphVQL, which allows users to query graphs by drawing a pattern visually for the query. This language covers different query types from the simple selection and aggregation queries to social network analysis queries.

La notion de communauté, transverse à  l'analyse des réseaux sociaux, a attiré une attention grandissante à  travers les sciences ces dix dernières années. Les nombreuses tentatives pour modéliser aussi bien l'incarnation sociologiquedu concept aussi bien que sa manifestation structurelle dans le réseau social n'ont jusqu'à  présent que vaguement convergé. Aucun consensus formel n'a été atteint sur les aspects quantifiables de la communauté, et ceci malgré lesliens forts la reliant aux dimensions dynamique et topologique du réseau sous-jacent.Présentant une approche novatrice à  l'évaluation des communautés, cette thèse introduit et se base sur la cohésion, une métrique qui capture la qualitéintrinsèque, en tant que communauté, d'un ensemble de sommets dans un réseau. Il a été montré au travers d'une experience à  large échelle, dans laquelle les individus sondés ont pu noter l'aspect communautaires de groupes d'amis leur étant présentés, que la cohésion, définie en lien avec la notion de triades sociales, est fortement correlée à  la perception subjective de la communauté. Reflétant la complexité des interactions sociales, il est démontré que leproblème de trouver des communautés maximalement cohésive est NP-dur. En utilisant une heuristique approximant les résultats de ce problème, un certain nombre d'applications de la cohésion à  des données réelles sont mises en avant: de son application à  la visualisation de réseaux complexes, à  l'étude de l'évolution des groupes d'agrément du sénat états-unien, à  la compréhesion des liens entre psychologie et structure du réseau social.L'utilisation de la cohésion apporte un éclairage non trivial dans l'étude de la structure des grands réseaux de terrain et dans la relation entre structure et sémantique. / Community, a notion transversal to all areas of Social Network Analysis, has drawn tremendous amount of attention across the sciences in the past decades. Numerous attempts to characterize both the sociological embodiment of the concept as well as its observable structural manifestation in the social network have to this date only converged in spirit. No formal consensus has been reached on the quantifiable aspects of community, despite it being deeply linked to topological and dynamic aspects of the underlying social network. Presenting a fresh approach to the evaluation of communities, this thesis introduces and builds upon the cohesion, a novel metric which captures the intrinsic quality, as a community, of a set of nodes in a network. The cohesion, defined in terms of social triads, was found to be highly correlated to the subjective perception of communitiness through the use of a large-scale online experiment in which users were able to compute and rate the quality of their social groups on Facebook. Adequately reflecting the complexity of social interactions, the problem of finding a maximally cohesive group inside a given social network is shown to be NP-hard. Using a heuristic approximation algorithm, applications of the cohesion to broadly different use cases are highlighted, ranging from its application to network visualization, to the study of the evolution of agreement groups in the United States Senate, to the understanding of the intertwinement between subjects' psychological traits and the cohesive structures in their social neighborhood. The use of the cohesion proves invaluable in that it offers non-trivial insights on the network structure and its relation to the associated semantic.

Cette thèse porte sur deux types de problèmes de mécanique statistique : il y est question de percolation sur les groupes et de modèles dirigés. Dans le premier cas,il s’agit de réaliser un groupe comme objet géométrique (via la notion de graphe de Cayley), puis de morceler ce dernier aléatoirement. L’étude de ce processus révèle des liens étroits entre les propriétés géométriques d’un groupe et le comportement de la percolation de Bernoulli sur celui-Ci. Dans le second cas, on s’intéresse à des modèles où haut et bas jouent des rôles différents, ce qui permet de rendre un certain nombre de questions accessibles à l’étude rigoureuse.Le chapitre 1 renforce le théorème d’indistinguabilité de Lyons et Schramm en percolation, lequel stipule que les composantes connexes infinies fournies par la percolation de Bernoulli sur un graphe de Cayley ont presque sûrement toutes la même allure. La non-Trivialité de ce renforcement est illustrée par un modèle dirigé qui vérifie la propriété d’indistinguabilité mais pas la propriété renforcée.Le chapitre 2 est le fruit d’un travail réalisé en collaboration avec Vincent Tassion.On y démontre que la valeur du paramètre critique pour la percolation de Bernoulli ne dépend essentiellement que de la structure locale du graphe de Cayley abélien considéré.Dans le chapitre 3, on introduit une version dirigée du modèle DLA, pour laquelle on établit l’existence d’une dynamique en volume infini, un contrôle sur la propagation d’information et des inégalités asymptotiques sur la largeur et la hauteur de l’agrégat. / This thesis deals with two kinds of statistical mechanics problems: percolation ongroups and directed models. In the first case, we realise the group under considerationas a geometric object (via the notion of Cayley graph) before breaking it apartrandomly. The study of this process reveals deep connections between the geometricproperties of a group and the behaviour of Bernoulli percolation on it. In the secondcase, we focus on models where up and down play different roles, which makes severalquestions less hard to tackle.Chapter 1 strengthens the Indistinguishability Theorem of Lyons-Schramm, whichstates that the infinite clusters yielded by a Bernoulli percolation on a Cayley graphalmost surely all look alike. The non-Triviality of this strengthening is illustrated bya directed model that satisfies the Indistinguishability Property but not the StrongIndistinguishability Property.Chapter 2 has been obtained in collaboration with Vincent Tassion. We show thatthe value of the critical parameter for Bernoulli percolation essentially only dependson the local structure of the considered abelian Cayley graph.In Chapter 3, we introduce a directed version of the DLA model, for which weestablish the existence of an infinite volume dynamics, control the propagation ofinformation and prove asymptotic inequalities on the width and height of the cluster.

Les simulations dites multi-physiques couplent plusieurs phases de calcul. Lorsqu’elles sont exécutées en parallèle sur des architectures à mémoire distribuée, la minimisation du temps de restitution nécessite dans la plupart des cas d’équilibrer la charge entre les unités de traitement, pour chaque phase de calcul. En outre, la distribution des données doit minimiser les communications qu’elle induit. Ce problème peut être modélisé comme un problème de partitionnement de graphe multi-critères. On associe à chaque sommet du graphe un vecteur de poids, dont les composantes, appelées « critères », modélisent la charge de calcul porté par le sommet pour chaque phase de calcul. Les arêtes entre les sommets, indiquent des dépendances de données, et peuvent être munies d’un poids reflétant le volume de communication transitant entre les deux sommets. L’objectif est de trouver une partition des sommets équilibrant le poids de chaque partie pour chaque critère, tout en minimisant la somme des poids des arêtes coupées, appelée « coupe ». Le déséquilibre maximum toléré entre les parties est prescrit par l’utilisateur. On cherche alors une partition minimisant la coupe, parmi toutes celles dont le déséquilibre pour chaque critère est inférieur à cette tolérance. Ce problème étant NP-Dur dans le cas général, l’objet de cette thèse est de concevoir et d’implanter des heuristiques permettant de calculer efficacement de tels partitionnements. En effet, les outils actuels renvoient souvent des partitions dont le déséquilibre dépasse la tolérance prescrite. Notre étude de l’espace des solutions, c’est-à-dire l’ensemble des partitions respectant les contraintes d’équilibre, révèle qu’en pratique, cet espace est immense. En outre, nous prouvons dans le cas mono-critère qu’une borne sur les poids normalisés des sommets garantit que l’espace des solutions est non-vide et connexe. Nous fondant sur ces résultats théoriques, nous proposons des améliorations de la méthode multi-niveaux. Les outils existants mettent en oeuvre de nombreuses variations de cette méthode. Par l’étude de leurs codes sources, nous mettons en évidence ces variations et leurs conséquences à la lumière de notre analyse sur l’espace des solutions. Par ailleurs, nous définissons et implantons deux algorithmes de partitionnement initial, se focalisant sur l’obtention d’une solution à partir d’une partition potentiellement déséquilibrée, au moyen de déplacements successifs de sommets. Le premier algorithme effectue un mouvement dès que celui-ci améliore l’équilibre, alors que le second effectue le mouvement réduisant le plus le déséquilibre. Nous présentons une structure de données originale, permettant d’optimiser le choix des sommets à déplacer, et conduisant à des partitions de déséquilibre inférieur en moyenne aux méthodes existantes. Nous décrivons la plate-forme d’expérimentation, appelée Crack, que nous avons conçue afin de comparer les différents algorithmes étudiés. Ces comparaisons sont effectuées en partitionnant un ensembles d’instances comprenant un cas industriel et plusieurs cas fictifs. Nous proposons une méthode de génération de cas réalistes de simulations de type « transport de particules ». Nos résultats démontrent la nécessité de restreindre les poids des sommets lors de la phase de contraction de la méthode multi-niveaux. En outre, nous mettons en évidence l’influence de la stratégie d’ordonnancement des sommets, dépendante de la topologie du graphe, sur l’efficacité de l’algorithme d’appariement « Heavy-Edge Matching » dans cette même phase. Les différents algorithmes que nous étudions sont implantés dans un outil de partitionnement libre appelé Scotch. Au cours de nos expériences, Scotch et Crack renvoient une partition équilibrée à chaque exécution, là où MeTiS, l’outil le plus utilisé actuellement, échoue une grande partie du temps. Qui plus est, la coupe des solutions renvoyées par Scotch et Crack est équivalente ou meilleure que celle renvoyée par MeTiS. / Multiphysics simulation couple several computation phases. When they are run in parallel on memory-distributed architectures, minimizing the simulation time requires in most cases to balance the workload across computation units, for each computation phase. Moreover, the data distribution must minimize the induced communication. This problem can be modeled as a multi-criteria graph partitioning problem. We associate with each vertex of the graph a vector of weights, whose components, called “criteria”, model the workload of the vertex for each computation phase. The edges between vertices indicate data dependencies, and can be given a weight representing the communication volume transferred between the two vertices. The goal is to find a partition of the vertices that both balances the weights of each part for each criterion, and minimizes the “edgecut”, that is, the sum of the weights of the edges cut by the partition. The maximum allowed imbalance is provided by the user, and we search for a partition that minimizes the edgecut, among all the partitions whose imbalance for each criterion is smaller than this threshold. This problem being NP-Hard in the general case, this thesis aims at devising and implementing heuristics that allow us to compute efficiently such partitions. Indeed, existing tools often return partitions whose imbalance is higher than the prescribed tolerance. Our study of the solution space, that is, the set of all the partitions respecting the balance constraints, reveals that, in practice, this space is extremely large. Moreover, we prove in the mono-criterion case that a bound on the normalized vertex weights guarantees the existence of a solution, and the connectivity of the solution space. Based on these theoretical results, we propose improvements of the multilevel algorithm. Existing tools implement many variations of this algorithm. By studying their source code, we emphasize these variations and their consequences, in light of our analysis of the solution space. Furthermore, we define and implement two initial partitioning algorithms, focusing on returning a solution. From a potentially imbalanced partition, they successively move vertices from one part to another. The first algorithm performs any move that reduces the imbalance, while the second performs at each step the move reducing the most the imbalance. We present an original data structure that allows us to optimize the choice of the vertex to move, and leads to partitions of imbalance smaller on average than existing methods. We describe the experimentation framework, named Crack, that we implemented in order to compare the various algorithms at stake. This comparison is performed by partitioning a set of instances including an industrial test case, and several fictitious cases. We define a method for generating realistic weight distributions corresponding to “Particles-in-Cells”-like simulations. Our results demonstrate the necessity to coerce the vertex weights during the coarsening phase of the multilevel algorithm. Moreover, we evidence the impact of the vertex ordering, which should depend on the graph topology, on the efficiency of the “Heavy-Edge” matching scheme. The various algorithms that we consider are implemented in an open- source graph partitioning software called Scotch. In our experiments, Scotch and Crack returned a balanced partition for each execution, whereas MeTiS, the current most used partitioning tool, fails regularly. Additionally, the edgecut of the solutions returned by Scotch and Crack is equivalent or better than the edgecut of the solutions returned by MeTiS.

Dans cette thèse, nous présentons trois problèmes concernant les graphes planaires.Nous travaillons tout d'abord sur les dessins planaires non-alignés, c'est-à-dire des dessins planaires de graphes sur une grille sans que deux sommets se trouvent sur la même ligne ou la même colonne.Nous caractérisons les graphes planaires possédant un tel dessin sur une grille de taille $n times n$, et nous présentons deux algorithmes générant un dessin planaire non-aligné avec arêtes brisées sur cette grille pour tout graphe planaire, avec $n-3$ ou $min(frac{2n-3}{5},$ $#{text{triangles s{'e}parateurs}}+1)$ brisures au total.Nous proposons également deux algorithmes dessinant un dessin planaire non-aligné sur des grilles d'aire $O(n^4)$. Nous donnons des résultats spécifiques concernant les graphes 4-connexes et de type triangle-emboîté.Le second sujet de cette thèse est la domination de puissance dans les graphes planaires. Nous exhibons une famille de graphes ayant un nombre de domination de puissance $gamma_P$ au moins égal à $frac{n}{6}$. Nous montrons aussi que pour tout graphe planaire maximal $G$ à $n geq 6$ sommets, $gamma_P(G) leq frac{n-2}{4}$. Enfin, nous étudions les grilles triangulaires $T_k$ à bord hexagonal de dimension $k$ et nous montrons que $frac{k}{3} - frac{1}{6} leq gamma_P(T_k) leq lceil frac{k}{3} rceil$.Nous étudions également l'énumération des orientations planaires Eulériennes. Nous proposons une nouvelle décomposition de ces cartes. En considérant les orientations des dernières $2k-1$ arêtes autour de la racine, nous définissons des sous- et sur-ensembles des orientations planaires Eulériennes paramétrés par $k$.Pour chaque classe, nous proposons un système d'équations fonctionnelles définissant leur série génératrice, et nous prouvons que celle-ci est toujours algébrique. Nous montrons ainsi que la constance de croissance des orientations planaires Eulériennes est entre 11.56 et 13.005. / In this thesis, we present results on three different problems concerning planar graphs.We first give some new results on planar non-aligned drawings, i.e. planar grid drawings where vertices are all on different rows and columns.We show that not every planar graph has a non-aligned drawing on an $n times n$-grid, but we present two algorithms generating a non-aligned polyline drawings on such a grid requiring either $n-3$ or $min(frac{2n-3}{5},$ $#{text{separating triangles}}+1)$ bends in total.Concerning non-minimal grids, we give two algorithms drawing a planar non-aligned drawing on grids with area of order $n^4$. We also give specific results for 4-connected graphs and nested-triangle graphs.The second topic is power domination in planar graphs. We present a family of graphs with power dominating number $gamma_P$ at least $frac{n}{6}$. We then prove that for every maximal planar graph $G$ of order $n$, $gamma_P(G) leq frac{n-2}{4}$, and we give a constructive algorithm.We also prove that for triangular grids $T_k$ of dimension $k$ with hexagonal-shape border, $frac{k}{3} - frac{1}{6} leq gamma_P(T_k) leq lceil frac{k}{3} rceil$.Finally, we focus on the enumeration of planar Eulerian orientations. After proposing a new decomposition for these maps, we define subsets and supersets of planar Eulerian orientations with parameter $k$, generated by looking at the orientations of the last $2k-1$ edges around the root vertex.For each set, we give a system of functional equations defining its generating function, and we prove that it is always algebraic.This way, we show that the growth rate of planar Eulerian orientations is between 11.56 and 13.005.

Les interactions entre transport et territoire sont l’objet d’une littérature scientifique permanente, questionnant les impacts économiques et démographiques d’une nouvelle infrastructure, souvent évoqués à l’échelle d’un projet. L’objectif de la thèse est de réinvestir les composantes de l’interaction par les larges échelles spatiales et temporelles, en posant l’hypothèse que la profondeur temporelle et l’échelle du territoire national sont porteuses de nouvelles explications. Ce travail s’appuie sur la collecte, l’exploitation et l’analyse de la large base de données FRANcE (French RAilway NEtwork), qui recense chaque section du réseau ferroviaire français depuis le début du XIXème siècle et les recensements démographiques. Cette base renferme également les traces de la vitesse, qui constituent une information inédite sur l’ensemble du réseau et qui permet de faire de l’accessibilité une variable décisive dans les explications. Plutôt que de se concentrer sur l’acquisition de nouvelles données au prix d’une lourde collecte, nous misons sur la construction d’un appareil méthodologique pour étudier les deux sens de l’interaction entre réseau et territoire, qui requiert toutefois une adaptation des dispositifs de structuration des données et d’analyse. La démarche de la thèse consiste en une modélisation croissante du phénomène, de la compréhension et la formalisation des objets jusqu’à la formalisation des données et des analyses, ce qui nécessite le recours à d’autres disciplines. Ce travail utilise le formalisme des graphes pour investiguer les deux sens de la relation. Il aide à étudier l’effet du réseau à partir d’une diversification de la donnée et de sa modélisation pour rendre compte de portées spatiales et temporelles. Il aide à étudier l’impact d’une structure préexistante dans la morphogénèse du réseau ferroviaire français à partir d’un modèle d’évolution endogène, entre diffusion du rail et hiérarchisation des infrastructures. Ce travail vise à mieux comprendre les liens qui unissent réseau et territoire, dont les outils méthodologiques peuvent être appliquées à d’autres réseaux, d’autres temporalités, jusqu’à des problématiques actuelles. / The interaction between space and network are frequently questioned in the academic literature, by asking the economical and demographical impacts of a new infrastructure, often studied at the scale of a project. This work aims to investigate the components of the interaction in both large spatial and temporal scales. The hypothesis is that the temporal depth and the national scale could bring new explanations. This work is based on the collect, the exploitation and the analysis of the large spatio-temporal database FRANcE (French Railway Network). It identifies all sections of the network since the 19th century and the population census. This database also contains the traces of the speed, which are novel information for network, and allows the accessibility to become a decisive variable in the explanations. Rather than acquisition new data with an intensive phase of collect, we aim to build a methodological chain to study the two senses of interaction between space and network. It requires the adaptation of data structuration and analysis. The approach of this thesis consists on the growing modelling of the phenomenon, from the comprehension to formalization of data to the analysis, which requires the use of other disciplines. This work uses the graph theory to investigate the two senses of the relationship. It permits to study the network effect in the long run by diversifying the data to identify spatial and temporal ranges. It permits to study the impact of a pre-existing structure in the morphogenesis of the network, by using a dynamic model of network evolution, between diffusion and hierarchical organization. This work aims to understand the link between space and network, where the methodological tools can be adapted to other networks, other times and actual questioning.

La prise en compte de machines à traitement par batch dans les problèmes d’ordonnancement d’ateliers complexes de type job-shop est particulièrement difficile. La fabrication de semiconducteurs est probablement l’une des applications pratiques les plus importantes pour ce types de problèmes. Nous considérons un problème d’ordonnancement de type job-shop flexible avec « p-batching », des flux rentrants, des temps de préparation dépendant de la séquence et des dates de début au plus tôt. Le but c’est d’optimiser différentes fonctions objectives régulières.Les approches existantes par graphe disjonctif pour ce problème utilise des nœuds dédiés pour représenter explicitement les batches. Afin de faciliter la modification du graphe conjonctif, notre nouvelle modélisation réduit cette complexité en modélisant les décisions de batching à travers les poids des arcs. Une importante contribution de cette thèse est un algorithme original qui prend les décisions de batching lors du parcours du graphe. Cet algorithme est complété par un déplacement (« move ») intégré qui permet de reséquencer ou réaffecter les opérations. Cette combinaison donne un voisinage riche que nous appliquons dans une approche méta-heuristique de type GRASP.Nous étendons cette approche en prenant en compte de nouvelles contraintes qui ont un rôle important dans l’application industrielle considérée. En particulier, nous modélisons de manière explicite les ressources internes des machines, et nous considérons un temps maximum d’attente entre deux opérations quelconques d’une gamme de fabrication. Les résultats numériques sur des instances de la littérature pour des problèmes plus simples ainsi que sur de nouvelles instances montrent la généricité et l’applicabilité de notre approche. Notre nouvelle modélisation permet de faciliter les extensions à d’autres contraintes complexes rencontrées dans les applications industrielles. / The integration of batching machines within a job-shop environment leads to a complex job-shop scheduling problem. Semiconductor manufacturing presumably represents one of the most prominent practical applications for such problems. We consider a flexible job-shop scheduling problem with p-batching, reentrant flows, sequence dependent setup times and release dates while considering different regular objective functions. The scheduling of parallel batching machines and variants of the job-shop scheduling problem are well-studied problems whereas their combination is rarely considered.Existing disjunctive graph approaches for this combined problem rely on dedicated nodes to explicitly represent batches. To facilitate modifications of the graph, our new modeling reduces this complexity by encoding batching decisions into edge weights. An important contribution is an original algorithm that takes batching decisions “on the fly” during graph traversals. This algorithm is complemented by an integrated move to resequence and reassign operations. This combination yields a rich neighborhood that we apply within a GRASP based metaheuristic approach.We extend this approach by taking further constraints into account that are important in the considered industrial application. In particular, we model internal resources of machines in detail and take maximum time lag constraints into account. Numerical results for benchmark instances of different problem types show the generality and applicability of our approach. The conciseness of our idea facilitates extensions towards further complex constraints needed in real-world applications.

Avec l'évolution des dispositifs d'acquisition 3D, les nuages de points sont maintenant devenus une représentation essentielle des scènes numérisées. Les systèmes récents sont capables de capturer plusieurs centaines de millions de points en une seule acquisition. Comme plusieurs acquisitions sont nécessaires pour capturer la géométrie de scènes de grande taille, un site historique par exemple, nous obtenons des nuages de points massifs, i.e., composés de plusieurs milliards de points. Dans cette thèse, nous nous intéressons à la structuration et à la manipulation de nuages de points issus d'acquisitions générées à partir de LiDARs terrestres. A partir de la structure de chaque acquisition, des graphes, représentant chacun la connectivité locale de la surface numérisée, sont construits. Les graphes créés sont ensuite liés entre eux afin d'obtenir une représentation globale de la surface capturée. Nous montrons que cette structure est particulièrement adaptée à la manipulation de la surface sous-jacente aux nuages de points massifs, même sur des ordinateurs ayant une mémoire limitée. Notamment, nous montrons que cette structure permet de traiter deux problèmes spécifiques à ce type de données. Un premier lié au ré-échantillonnage de nuages de points, en générant des distributions de bonne qualité en termes de bruit bleu grâce à un algorithme d'échantillonnage en disques de Poisson. Un autre lié à la construction de diagrammes de Voronoï centroïdaux, permettant l'amélioration de la qualité des distributions générées, ainsi que la reconstruction de maillages triangulaires. / With the evolution of 3D acquisition devices, point clouds have now become an essential representation of digitized scenes. Recent systems are able to capture several hundreds of millions of points in a single acquisition. As multiple acquisitions are necessary to capture the geometry of large-scale scenes, a historical site for example, we obtain massive point clouds, i.e., composed of billions of points. In this thesis, we are interested in the structuration and manipulation of point clouds from acquisitions generated by terrestrial LiDARs. From the structure of each acquisition, graphs, each representing the local connectivity of the digitized surface, are constructed. Created graphs are then linked together to obtain a global representation of the captured surface. We show that this structure is particularly adapted to the manipulation of the underlying surface of massive point clouds, even on computers with limited memory. Especially, we show that this structure allow to deal with two problems specific to that kind of data. A first one linked to the resampling of point clouds, by generating distributions of good quality in terms of blue noise thanks to a Poisson disk sampling algorithm. Another one connected to the construction of centroidal Voronoi tessellations, allowing to enhance the quality of generated distributions and to reconstruct triangular meshes.