Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable. / Location decisions are frequently subject to dynamic aspects such as changes in customer demand. Often, flexibility regarding the geographic location of facilities, as well as their capacities, is the only solution to such issues. Even when demand can be forecast, finding the optimal schedule for the deployment and dynamic adjustment of capacities remains a challenge. In this thesis, we focus on multi-period facility location problems that allow for dynamic capacity adjustment, in particular those with complex cost structures. We investigate such problems from different Operations Research perspectives, presenting and comparing several mixed-integer programming (MIP) models, assessing their use in practice and developing efficient solution algorithms. The thesis is divided into four parts. We first motivate our research by an industrial application, in which a logging company needs to locate camps to host the workers involved in forestry operations. We present a MIP model that allows for the construction of additional camps, the expansion and relocation of existing ones, as well as partial closing and reopening of facilities. The model uses particular capacity constraints that involve integer rounding on the left hand side. Economies of scale are considered on several levels of the cost structure. The usefulness of the model is assessed by two case studies. The second part introduces the Dynamic Facility Location Problem with Generalized Modular Capacities (DFLPG). The model generalizes existing formulations for several dynamic facility location problems and provides stronger linear programming relaxations than the specialized formulations. The model can address facility location problems where the costs for capacity changes are defined for all pairs of capacity levels, as it is the case in the previously introduced industrial problem. It is applied to three special cases: capacity expansion and reduction, temporary facility closing and reopening, and the combination of both. We prove dominance relationships between our formulation and existing models for the special cases. Computational experiments on a large set of randomly generated instances with up to 100 facility locations and 1000 customers show that our model can obtain optimal solutions in shorter computing times than the existing specialized formulations. Given the complexity of such models for large instances, the third part of the thesis proposes efficient Lagrangian heuristics. Based on subgradient and bundle methods, good quality solutions are found even for large-scale instances with up to 250 facility locations and 1000 customers. To improve the final solution quality, a restricted model is solved based on the information collected through the solution of the Lagrangian dual. Computational results show that the Lagrangian based heuristics provide highly reliable results, producing good quality solutions in short computing times even for instances where generic solvers do not find feasible solutions. Finally, we adapt the Lagrangian heuristics to solve the industrial application. Two different relaxations are proposed and compared. Extensions of the previous concepts are presented to ensure a reliable solution of the problem, providing high quality solutions in reasonable computing times.

Maitriser les coûts de fabrication des circuits intégrés tout en augmentant leur densité est d'une importance primordiale pour maintenir une certaine rentabilité dans l’industrie du semi-conducteur. Parmi les différents composants d’un circuit, nous nous intéressons aux connections verticales et métalliques, connues sous le nom de « vias ». Durant la fabrication, un processus de lithographie complexe est utilisé pour former une disposition de vias est formée sur une plaque de silicium, à l’aide d’un un masque optique. Pour des raisons de fabrication, une distance minimum entre les vias doit être respectée. Lorsque cette distance n’est pas respectée, nous parlons de « conflit ». Afin de supprimer ces conflits, l’industrie utilise une technique qui permet de décomposer une disposition de vias cible en plusieurs sous-ensembles, où les contraintes de distance minimum sont respectées : la formation des sous-ensembles individuels se fait en séquence sur la plaque de silicium en utilisant un masque optique par sous-ensemble. Cette technique est appelée Multiple Patterning (MP). Il y a de nombreuses façons de décomposer une disposition de vias et le but est d’assigner les vias à un nombre minimum de masques, car les masques sont coûteux. Minimiser le nombre de masques est équivalent à minimiser le nombre de couleurs dans un graphe disque unitaire. Ce problème est NP-difficile, mais un certain nombre de « bonnes » heuristiques existent. Une technique récente et prometteuse basée sur l’auto-assemblage et direction des molécules, aussi connue sous le nom Directed Self Assembly (DSA), permet de grouper les vias en conflits à condition de respecter certaines contraintes. L’objectif est de trouver la meilleure façon de grouper les vias afin de minimiser le nombre de masques tout en respectant les contraintes liées à DSA. Ce problème est un problème de coloration de graphes où les sommets de chaque couleurs définissent un ensemble de chemins « indépendants » de longueurs au plus k que nous appelons aussi le problème de coloration par k-chemins. Durant la modélisation, nous avons distingué deux problèmes de coloration par k-chemins pertinents: le problème général et le problème induit. Les deux problèmes sont connus pour être NP-difficile, ce qui explique l’utilisation d’heuristiques dans l’industrie pour trouver une décomposition valide en sous-ensembles. Dans cette étude, nous nous intéressons à des méthodes exactes afin de concevoir des solutions optimales et d’évaluer la qualité de l’heuristique développée en industrie (chez Mentor Graphics). Nous présentons différentes méthodes: une approche par programmation linéaire en nombre entier (ILP) où nous étudions plusieurs formulations, une approche par programmation dynamique pour résoudre le cas induit quand k=1 ou k=2 et lorsque les graphes ont une petite longueur arborescente ; enfin, nous étudions le cas particulier des graphes lignes. Les résultats des différentes études numériques montrent que les formulations ILP « naïves » sont les meilleures. Elles listent tous les chemins possibles de longueur au plus k. Les tests sur des données industrielles ayant au plus 2000 sommets (plus grande composante connexe parmi celles qui constituent une instance) ont montré que les deux problèmes, général et induit, sont résolus en moins de 6 secondes, pour k=1 et k=2. La programmation dynamique, appliquée au problème induit de coloration par k-chemins quand k=1 et k=2, montre des résultats équivalents à ceux de la formulation ILP naïve. Cependant, nous nous attendons à de meilleurs résultats par programmation dynamique quand la valeur de k augmente. Enfin, nous montrons qu’un cas particuliers des graphes lignes peut être résolu en temps polynomial en exploitant les propriétés de l’algorithme d'Edmonds et des couplages dans les graphes bipartis. / Controlling the manufacturing costs of integrated circuits while increasing their density is of a paramount importance to maintain a certain degree of profitability in the semi-conductor industry. Among various components of a circuit, we are interested in vertical metallic connections known as “vias”. During manufacturing, a complex lithography process is used to form an arrangement of vias on a silicon wafer support, using an optical mask. For manufacturing reasons, a minimum distance between the vias must be respected. Whenever this is not the case, we are talking about a “conflict”. In order to eliminate these conflicts, the industry uses a technique that decomposes an arrangement of vias in several subsets, where minimum distance constraints are respected: the formation of the individual subsets is done, in sequence, on a silicon wafer using one optical mask per subset. This technique is called Multiple Patterning (MP). There are several ways to decompose an arrangement of vias, the goal being to assign the vias to a minimum number of masks, since the masks are expensive. Minimizing the number of masks is equivalent to minimizing the number of colors in a unit disk graph. This is a NP-hard problem however, a number of “good” heuristics exist. A recent and promising technique is based on the direction and self-assembly of the molecules called Directed Self Assembly (DSA), allows to group vias in conflict according to certain conditions. The main challenge is to find the best way of grouping vias to minimize the number of masks while respecting the constraints related to DSA. This problem is a graph coloring problem where the vertices within each color define a set of independent paths of length at most k also called a k-path coloring problem. During the graph modeling, we distinguished two k-path coloring problems: a general problem and an induced problem. Both problems are known to be NP-hard, which explains the use of heuristics in the industry to find a valid decomposition into subsets. In this study, we are interested in exact methods to design optimal solutions and evaluate the quality of heuristics developed in the industry (at Mentor Graphics). We present different methods: an integer linear programming (ILP) approach where we study several formulations, a dynamic programming approach to solve the induced case when k=1 or k=2 and when the graphs have small tree-width; finally, we study a particular case of line graphs. The results of the various numerical studies show that the naïve ILP formulations are the best, they list all possible paths of length at most k. Tests on a snippet of industrial instances of at most 2000 vertices (a largest connected component among those constituting an instance) have shown that the two problems, general and induced, are solved in less than 6 seconds, for k=1 and k=2. Dynamic programming, applied to the induced k-path coloring when k=1 and k=2, shows results equivalent to those of the naïve ILP formulation, but we expect better results by dynamic programming when the value of k increases. Finally, we show that the particular case of line graphs can be solved in polynomial time by exploiting the properties of Edmonds’ algorithm and bipartite matching.

Cette thèse a pour objectif de modéliser et résoudre des problèmes d’optimisation d’un système d’auto-partage avec des voitures électriques dit « à un seul sens », où les utilisateurs peuvent prendre une voiture dans une station et la laisser ensuite dans une autre. Ce fonctionnement conduit généralement à une situation de déséquilibre dans la répartition des voitures avec certaines stations pleines et d’autres vides. Une des solutions utilisées par les opérateurs d’autopartage pour pallier ce problème est le recours à des agents pour déplacer les voitures selon le besoin. Identifier et répondre à ce besoin est un problème d’optimisation non trivial, notamment à cause de l’usage de véhicules électriques, ce qui engendre des contraintes de rechargement de batteries et d’autonomie. Le problème d’optimisation est décomposé en deux sous-problèmes : le premier est le problème d’affectation des voitures aux clients, ainsi que leurs routages, que nous nommons ROCSP pour Recharging One way Car Sharing Problem ; le second problème est celui du planning des agents et leurs routages que nous nommons ESRP pour Employee Scheduling Routing Problem. 1. Résolution du ROCSP : deux modélisations en Programmation Linéaire en Nombres Entiers (PLNE) sont proposées, la première basée sur les flots et la deuxième sur les chemins, ce qui fait que les deux modèles intègrent de manière différente les contraintes de recharge électrique. Comme la résolution exacte à travers les modèles PLNE s’avère très gourmande en temps de calcul et non adaptée aux instances d’auto-partage de taille réelle, nous proposons des heuristiques qui permettent dans un temps raisonnable d’optimiser la redistribution des voitures et la gestion du service. Ces heuristiques permettent de calculer le nombre de voitures et les différentes opérations de relocalisation (redistribution des voitures) à réaliser sur une journée donnée. 2. Résolution du ESRP : un modèle PLNE est proposé pour la résolution exacte du ESRP, et, en complément, des heuristiques sont proposées pour une résolution approchée et relativement rapide. L’objectif est la détermination du nombre minimal d’agents nécessaire pour effectuer les opérations de relocalisation qui découlent du premier problème, le ROCSP. Dans une partie prospective, et une fois les ROCSP et ESRP résolus dans leur version statique, nous nous focaliserons sur une autre variante du problème avec réservation dynamique. Nous proposons également d’explorer un nouveau concept - l’auto-copartage - qui se veut une hybridation entre autopartage et covoiturage. Les algorithmes proposés ont été validés sur le réseau Auto Bleue de la ville de Nice essentiellement, qui gère une flotte de véhicules électriques, en s’appuyant sur des modèles de génération de flux pour estimer la demande, mais aussi d’autres instances que nous avons générées pour simuler d’autres villes, au sein d’un Système d’Information Géographique. / This thesis aims at modelling and solving optimization problems related to the management of one-way-electric-car-sharing systems, where users can take a car from a station, use it, and then return it to another station. This generally leads to an imbalanced distribution of cars, with some full stations and other empty ones. A solution to this problem, implemented by car-sharing operators, is to employ staff agents to move cars as needed. However, identifying this need is a non-trivial optimization problem, especially since the system may be more constrained when the vehicles used are electric, which generates battery recharging and autonomy constraints. The global optimization problem addressed is then divided into two sub-problems. The first one is assigning the cars to customers, as well as their routing; it is denoted by ROCSP (Recharging OneWay Car Sharing Problem). The second problem involves agents planning and routing; it is denoted by ESRP (Employee Scheduling Routing Problem). 1. For the ROCSP, we propose two Mixed-integer linear programming (MILP) modelizations of the problem: One based on flows and the other based on paths. This means that the two models include the battery-recharging constraints in two different ways. As the exact resolution through the MILP models is quite expensive in terms of computational time and is not adapted for the resolution of real-size car-sharing instances, we introduce heuristics that enable the optimization of cars-redistribution and service management of the service within a reasonable amount of time. These heuristics allows the calculation of the number of cars and the various redistribution operations to be performed on a given day. 2. For the ESRP, this second problem is also addressed with MILP models for the exact resolution, and some heuristics are suggested for an approximate resolution. This process has reasonable calculation time and aims at finding the minimum number of agents to perform the necessary relocation operations that stem from the first problem, namely, the ROCSP. Once the ROCSP and ESRP solved in their static versions, we then focus on the ROCSP by exploring another variant of the problem : ROCSP with dynamic reservation. We also suggest to explore a new concept : Auto-CoPartage, which is a hybridization of car-sharing and carpooling. The stated algorithms are validated on the Auto Bleue electrical vehicles fleet in the network of the city of Nice, essentially by relying on flow generation models to estimate the demand, but also using other instances that we have generated for other cities. All the data are handled using a Geographical Information System.

Ce manuscrit synthétise plus d'une décade de notre recherche académique sur le sujet d'optimisation de codes bas niveau, dont le but est une intégration dans un compilateur optimisant ou dans un outil d'optimisation semi-automatique. Dans les programmes bas niveau, les caractéristiques du processeur sont connues et peuvent être utilisées pour générer des codes plus en harmonie avec le matériel. Nous commençons notre document par une vue générale sur le problème d'ordonnancement des phases de compilation. Actuellement, des centaines d'étapes de compilation et d'optimisation de codes existent; un problème fondamental et ouvert reste de savoir comment les combiner et les ordonner efficacement. Pour pallier rapidement cette difficulté, une stratégie du moindre effort consiste à appliquer une compilation itérative en exécutant successivement le programme avant de décider de la technique d'optimisation de code à employer et avec quels paramètres. Nous prouvons que l'approche de compilation itérative ne simpli fie pas fondamentalement le problème, et l'utilisation de modèles statiques de performances reste un choix raisonnable. Un problème classique de con it entre deux étapes de compilation est celui qui lie l'allocation de registres et l'ordonnancement d'instructions. Nous montrons comment gérer efficacement cet antagonisme en séparant les contraintes de registres des contraintes d'ordonnancement d'instructions. Cela est possible grâce à la notion de saturation en registres (RS), qui est le besoin maximal en registres pour tous les ordonnancements possibles d'un graphe. Nous apportons une contribution formelle et une heuristique efficace, qui permettent la détection de contraintes de registres toujours véri fiées; ils peuvent par conséquent être négligées. Nous introduisons la plate-forme SIRA, qui permet de garantir l'absence de code de vidage avant l'ordonnancement d'instructions. SIRA est un modèle basé sur la théorie des graphes permettant de borner le besoin maximal en registres pour tout pipeline logiciel, sans altérer, si possible, le parallélisme d'instructions. SIRA modélise les contraintes cycliques des registres dans différentes architectures possibles : avec plusieurs types de registres, avec tampons ou les d'attente, et avec des bancs de registres rotatifs. Nous apportons une heuristique efficace qui montre des résultats satisfaisants, que ce soit comme outil indépendant, ou comme passe intégrée dans un vrai compilateur. Dans le contexte des processeurs exhibant des retards d'accès aux registres (VLIW, EPIC, DSP), nous attirons l'attention sur le problème qui peut survenir lorsque les contraintes de registres sont traitées avant l'ordonnancement d'instructions. Ce problème est la création de circuits négatifs ou nuls dans le graphe de dépendances de données. Nous montrons comment éliminer ces circuits indésirables dans le contexte de SIRA. SIRA définit une relation formelle entre le nombre de registres alloués, le parallélisme d'instructions et le facteur de déroulage d'une boucle. Nous nous basons sur cette relation pour écrire un algorithme optimal qui minimise le facteur de déroulage tout en sauvegardant le parallélisme d'instructions et en garantissant l'absence de code de vidage. D'après nos connaissances, ceci est le premier résultat qui démontre que le compactage de la taille de code n'est pas un objectif antagoniste à l'optimisation des performances de code. L'interaction entre la hiérarchie mémoire et le parallélisme d'instructions est un point central si l'on souhaite réduire le coût des latences d'opérations de chargement. Premièrement, notre étude pratique avec des micro-benchmarks montre que les processeurs superscalaires ayant une exécution dans le désordre ont un bug de performances dans leur mécanisme de désambiguation mémoire. Nous montrons ensuite qu'une vectorisation des opérations mémoire résoud ce problème pour des codes réguliers. Deuxièmement, nous étudions l'optimisation de préchargement de données pour des codes VLIW embarqués irréguliers. Finalement, avec l'arrivée des processeurs multicoeurs, nous observons que les temps d'exécution des programmes deviennent très variables. A fin d'améliorer la reproductibilité des résultats expérimentaux, nous avons conçu le Speedup-Test, un protocole statistique rigoureux. Nous nous basons sur des tests statistiques connus (tests de Shapiro-Wilk, F de Fisher, de Student, de Kolmogorov-Smirnov, de Wilcoxon- Mann-Whitney) a n d'évaluer si une accélération observée du temps d'exécution médian ou moyen est signi cative.

En biologie structurale, il est couramment admit que la structure tridimensionnelle d'une protéine détermine sa fonction. Ce paradigme permet de supposer que deux protéines possédant des structures tridimensionnelles similaires peuvent partager un ancêtre commun et donc posséder des fonctions similaires. Déterminer la similarité entre deux structures de protéines est une tâche importante qui a été largement étudiée. Parmi toutes les méthodes proposées, nous nous intéressons à la mesure de similarité appelée “maximisation du recouvrement de cartes de contacts” (ou CMO), principalement parce qu'elle fournit des scores de similarité pouvant être utilisés pour obtenir de bonnes classifications automatiques des structures de protéines. Dans cette thèse, la comparaison de deux structures de protéines est modélisée comme une recherche de sous-graphe dans des graphes k-partis spécifiques appelés graphes d'alignements, et nous montrons que cette tâche peut être efficacement réalisée en utilisant des techniques avancées issues de l'optimisation combinatoire. Dans la seconde partie de cette thèse, nous modélisons CMO comme une recherche de sousgraphe maximum induit par les arêtes dans des graphes d'alignements, problème pour lequel nous proposons un solveur exact qui surpasse les autres algorithmes de la littérature. Même si nous avons réussi à accélérer CMO, la procédure d'alignement requière encore trop de temps de calculs pour envisager des comparaisons à grande échelle. La troisième partie de cette thèse est consacrée à l'accélération de CMO en utilisant des connaissances issues de la biologie structurale. Nous proposons une approche hiérarchique pour résoudre CMO qui est basée sur les structures secondaires des protéines. Enfin, bien que CMO soit une très bonne mesure de similarité, les alignements qu'elle fournit possèdent souvent de fortes valeurs de déviation (root mean squared deviation, ou RMSD). Pour palier à cette faiblesse, dans la dernière partie de cette thèse, nous proposons une nouvelle méthode de comparaison de structures de protéines basée sur les distances internes que nous appelons DAST (pour Distance-based Alignment Search Tool). Elle est modélisée comme une recherche de clique maximum dans des graphes d'alignements, pour laquelle nous présentons un solveur dédié montrant de très bonnes performances.

No description available.

Le cadre de cette thèse est l'optimisation des opérations aéroportuaires. Nous nous intéressons à trois problèmes de gestion des avions dans un aéroport : l'affectation aux points de stationnement, le routage au sol entre les pistes et les points de stationnement, et l'ordonnancement des décollages et des atterrissages.Ce travail a été réalisée en collaboration étroite avec la société Amadeus. Nos approches ont été testées et validées avec des données réelles provenant d'aéroports européens.Nous proposons une formulation en Programme Linéaire en Nombres Entiers (PLNE) du problème d'affectation aux points de stationnement. Nous montrons que trouver une affectation réalisable est un problème NP-Complet et nous proposons diverses améliorations visant à réduire le temps de résolution de notre modèle. Nous obtenons ainsi des solutions de meilleure qualité que celles de la littérature, tout en conservant un temps de calcul raisonnable.Le problème de routage au sol est modélisé en adaptant un PLNE de la littérature. Nous montrons que les indicateurs de l'industrie sont en contradiction avec l'objectif de réduction du temps de roulage, et donc des émissions de pollutions. Nous proposons de nouveaux indicateurs basés sur l'heure de décollage, et non sur l'heure de départ du point de stationnement.Enfin, nous nous intéressons à l'intégration de l'ordonnancement à la piste avec le routage au sol. Nous montrons qu'une meilleure intégration permet de réduire le temps de roulage et d'améliorer la gestion de la piste. Nous proposons une heuristique séquentielle basée sur une modélisation en PLNE innovante du problème d'ordonnancement à la piste. Nous montrons que cette heuristique fournit des solutions de bonne qualité en temps raisonnable, contrairement à l'approche exacte de la littérature. / In this thesis, we address the optimization of aircraft ground operations at airports, focusing on three main optimization problems: the stand allocation, the ground routing between stands and runways, and the sequencing of take-offs and landings.These works result from a close collaboration with Amadeus. Our approaches have been tested and validated with real data from European airports.The stand allocation problem is formulated as a Mixed Integer Program (MIP). We show that finding an allocation plan respecting operational requirements is NP-Complete and we strengthen our model in several directions. We obtain better solutions than the literature withing reasonable computation times for an industrial application.The ground routing problem is modeled by a MIP formulation adapted from the literature. We show that the main indicators of the industry are in contradiction with the objective of reducing taxi times and therefore air pollution. We propose new indicators based on take-off times instead of push back times.Lastly, we focus on the integration of the runway sequencing with the ground routing. We highlight that a better integration allows to reduce taxi times while improving the management of the runway. We propose a sequential heuristic based on an innovative MIP formulation of the runway sequencing problem. This heuristic is shown to provide high quality solutions in reasonable computation times, unlike the exact approach from the literature.

Les problèmes d’ordonnancement de rendez-vous en tête-à-tête sont des problèmes dans lesquels des personnes souhaitent se rencontrer par deux lors de courts rendez-vous qui se déroulent lors d’une session unique. Dans cette thèse, nous référençons plusieurs applications de ce type de problèmes et proposons des notations qui généralisent les notations standards de problèmes d’ordonnancement α|β|γ. Nous nous intéressons en particulier à un cas dans lequel deux populations distinctes se rencontrent, des participants peuvent arriver en retard et des rencontres sont interdites. L’objectif est de minimiser le nombre maximal d’attentes des participants. Nous étudions dans un premier temps la complexité de ces problèmes : nous démontrons que plusieurs cas sans rencontre interdite sont polynomiaux et que le cas général est NP-complet au sens fort. Nous proposons ensuite des bornes inférieures. Puis nous développons plusieurs méthodes de résolution. Des modèles de programmation linéaire en nombres entiers et un modèle de programmation par contraintes sont tout d’abord proposés. Des règles de dominance permettant de limiter les symétries sont intégrées à ces modèles dans le but de limiter l’espace des solutions. Enfin, nous proposons une recherche à divergence limitée (limited discrepancy search) qui est une méthode approchée basée sur l’exploration d’un arbre de recherche tronqué. Dans cette méthode, nous exploitons le plus possible les propriétés de symétrie du problème pour faciliter la convergence vers une bonne solution. Toutes ces méthodes sont testées et comparées sur un ensemble de 300 instances générées aléatoirement d’après des paramètres réalistes. / One-to-one meeting scheduling problems are problems where a population of actors want to meet each other during short time slots that take place in a single session. In this thesis, we reference several applications of this type of problems found in the literature and introduce a notation extending the well-known scheduling notation α|β|γ. We are particularly interested in a case in which two distinct populations meet, participants may arrive late and some meetings are forbidden. The objective is to minimize the maximum number of participants waiting slots. First, we study the complexity of these problems: we show that several cases with no forbidden meeting are polynomial and that the general case is NP-complete in the strong sense. We then propose lower bounds. After that, we develop several resolution methods. Integer linear programming models and a constraint programming model are developed. To limit the solution space, we add dominance rules based on symmetries to these methods. Finally, we present a limited discrepancy search (i.e. an approximate method based on the exploration of a truncated tree search). In this method, we use as much as possible the symmetry properties of the problem to facilitate the convergence to a good solution. All these methods are tested and compared on a set of 300 randomly generated instances from realistic parameters.

Les incitations économiques et environnementales poussent dorénavant à intégrer des considérations énergétiques dès les premiers stades de développement des réseaux. Dans les réseaux sans fil multi-sauts, l'approche la plus courante consiste à répartir le trafic sur l'ensemble des nœuds afin de réduire équitablement la consommation énergétique de chacun, avec pour objectif la maximisation de la durée de vie du réseau. Or cette approche n'est pas optimale vis-à-vis de la consommation globale du réseau, le niveau d'activité d'un nœud n'ayant souvent que peu d'influence sur sa propre consommation. Nous montrons que la meilleure approche consiste à éteindre un maximum de nœuds. Parmi les travaux réalisés, nous avons développé une solution s'appuyant sur de la programmation linéaire en nombres entiers et des simulations de graphes et de réseaux. La solution proposée permet ainsi une agrégation de flux optimale, réduisant significativement le nombre de nœuds utilisés dans le réseau. Afin de la rendre applicable en pratique, une heuristique est détaillée permettant une mise en œuvre distribuée grâce à l'utilisation d'une métrique de routage. Ainsi, tout algorithme de plus court chemin peut nativement réaliser de l'agrégation de flux efficace. Il est important de souligner que la qualité de service en termes de débit est respectée. En effet, les interférences sont prises en compte et il est possible de profiter de la synergie offerte par l'utilisation conjointe de l'agrégation de flux et du codage réseau. Nos résultats améliorent significativement les méthodes d'économie d'énergie basées sur l'extinction des nœuds en leur permettant d'en éteindre davantage. / Economic and ecologic incentives are now leading people to design networks with energetic considerations at early stages of development. Most of the works for multi-hop wireless networks tend to spread the traffic uniformly over the network to reduce the energy consumption of each node individually. However, considering that the traffic of a node doesn't impact significantly its energy consumption, this approach is not optimal regarding the global energy consumption of the network. Finding a way to turnoff as much node as possible seems then to be a better way. This PhD thesis focus on routing a set of flows over a multi-hop wireless network while minimizing the number of used nodes. This is done by using a distributed metric that allows the shortest path routing algorithms to perform flow aggregation. Using integer linear programming and simulations, we proposed an efficient solution to aggregate flows to significantly reduce the number of nodes used in the network. It allows, then, to improve algorithms that reduce the energy consumption of networks by increasing the number of nodes that can be turned off.

La plupart des systèmes ferroviaires subissent une demande croissante de capacité. Pour y faire face, il faut construire de nouvelles infrastructures ou exploiter plus efficacement celles existantes, notamment en définissant des grilles horaires optimisées. Dans la littérature, la plupart des approches de construction des grilles sont basées sur des représentations macroscopiques de l'infrastructure, ce qui peut conduireà des solutions infaisables ou inefficaces. En revanche, les approches microscopiques reposent sur une modélisation réaliste du système ferroviaire, ce qui garantit la faisabilité et l'efficacité des résultats. Néanmoins, en raison de leur complexité, l'utilisation de ces approches est généralement limitée à une seule gare. Malgré l'optimisation de la grille horaire, les travaux de maintenance peuvent avoir un fort impact sur les circulations des trains. En présence de maintenances, il peut donc être nécessaire de redéfinir la grille horaire pour assurer une exploitation efficace de la capacité. Nous présentons deux contributions principales sous forme de deux approches microscopiques : une pour la conception de grilles horaires et l'autre pour leur redéfinition en cas de maintenance. La deuxième est la première approche microscopique qui apparaît dans la littérature pour aborder ce problème tout en considérant des aspects comme les limitations temporaires de vitesse. Nous démontrons la validité de nos approches et leur applicabilité dans des scénarios réels. De plus, nous montrons que les approches microscopiques peuvent être utilisées pour traiter des zones de l'infrastructure contenant plusieurs gares. / Most railway systems experience a growing demand of railway capacity. To face this demand, either new infrastructure must be built or a more efficient exploitation of the existing one must be attained. Timetables play a determinant role in the efficient capacity exploitation. Most timetabling approaches in the literature are based on macroscopic representations of the infrastructure. This may lead to inefficient and in some cases, impractical solutions. Instead, microscopic approaches are based on more realistic modelling of the elements of the railway system. This guarantees the feasibility of the timetables while promoting an efficient capacity exploitation. However, due to their complexity, the scope of microscopic approaches is typically restricted to main stations. Despite the optimization of timetables, the performance of infrastructure maintenance may severely impact the trains' circulations in the network. Therefore, the timetable may have to be rearranged to ensure an efficient capacity exploitation. We present two main contributions in this thesis: first, a microscopic approach for timetable design. Second, a microscopic approach for timetable rearrangement to cope with maintenance. This is the first microscopic approach in the literature to tackle this problem while also considering specific aspects as temporary speed limitations. After a thorough experimental analysis, we demonstrate the validity of our approaches and their practical applicability in real life scenarios. In particular, we show that microscopic approaches can be used to tackle large areas of the infrastructure, including several stations.