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.

Aujourd’hui, la conception de réseaux est une problématique cruciale qui se pose dans beaucoup de domaines tels que le transport ou l’énergie. En particulier, il est devenu nécessaire d’optimiser la façon dont sont conçus les réseaux permettant de produire de l’énergie. On se concentre ici sur la production électrique produite à travers des parcs éoliens. Cette énergie apparait plus que jamais comme une bonne alternative à la production d’électricité via des centrales thermiques ou nucléaires.Nous nous intéressons dans cette thèse à la conception du câblage collectant l’énergie dans les parcs éoliens. On connaît alors la position de l’ensemble des éoliennes appartenant au parc ainsi que celle du site central collecteur vers laquelle l’énergie doit être acheminée. On connaît également la position des câbles que l’on peut construire, leurs capacités, et la position des nœuds d’interconnexion possibles. Il s’agit de déterminer un câblage de coût minimal permettant de relier l’ensemble des éoliennes à la sous-station, tel que celui-ci soit résistant à un certain nombre de pannes sur le réseau. / Nowadays, the design of networks has become a decisive problematic which appears in many fields such as transport or energy. In particular, it has become necessary and important to optimize the way in which networks used to produce, collect or transport energy are designed. We focus in this thesis on electricity produced through wind farms. The production of energy by wind turbines appears more than ever like a good alternative to the electrical production of thermal or nuclear power plants.We focus in this thesis on the design of the cabling network which allows to collect and route the energy from the wind turbines to a sub-station, linking the wind farm to the electrical network. In this problem, we know the location of each wind turbine of the farm and the one of the sub-station. We also know the location of possible inter-connection nodes which allow to connect different cables between them. Each wind turbine produces a known quantity of energy and with each cable are associated a cost and a capacity (the maximum amount of energy that can be routed through this cable). The optimizationproblem that we consider is to select a set of cables of minimum cost such that the energy produced from the wind turbines can be routed to the sub-station in the network induced by this set of cables, without exceeding the capacity of each cable. We focus on cabling networks resilient to breakdowns.

Pour les opérateurs, les réseaux FTTH représentent à la fois la solution de référence pour répondre à la demande croissante de trafic fixe, et un investissement considérable dû à leur mise en place. Le but de ces travaux est d'assurer le déploiement de réseaux de qualité à moindre coût. Nous commençons à présenter les différents aspects de la planification de ces réseaux qui en font un problème complexe. La littérature concernée est abordée afin d'exhiber les nouveaux défis que nous relevons. Puis nous élaborons des stratégies permettant de trouver la meilleure solution dans différents contextes. Plusieurs politiques de maintenance ou d'utilisation du génie civil sont ainsi explorées. Les problèmes rencontrés sont analysés à la lumière de divers outils d'optimisation (programmation entière, inégalités valides, programmation dynamique, approximations, complexités, inapproximabilité...) que nous utilisons et développons selon nos besoins. Les solutions proposées ont été testées et validées sur des instances réelles, et ont pour but d'être utilisées par Orange / For operators, FTTH networks are the most widespread solution to the increasing traffic demand. Their layout requires a huge investment. The aim of this work is to ensure a cost effective deployment of quality networks. We start by presenting aspects of this network design problem which make it a complex problem. The related literature is reviewed to highlight the novel issues that we solve. Then, we elaborate strategies to find the best solution in different contexts. Several policies regarding maintenance or civil engineering use will be investigated. The problems encountered are tackled using several combinatorial optimization tools (integer programming, valid inequalities, dynamic programming, approximations, complexity theory, inapproximability…) which will be developed according to our needs. The proposed solutions were tested and validated on real-life instances, and are meant to be implemented in a network planning tool from Orange

L'objectif de cette thèse consiste à présenter un nouvel algorithme pour la programmation non linéaire en nombres entiers, inspirée par la méthode Multiplicative Weights Update et qui compte sur une nouvelle classe de reformulations, appelées les reformulations ponctuelles.La programmation non linéaire en nombres entiers est un sujet très difficile et fascinant dans le domaine de l'optimisation mathématique à la fois d'un point de vue théorique et computationnel. Il est possible de formuler de nombreux problèmes dans ce schéma général et, habituellement, ils posent de réels défis en termes d'efficacité et de précision de la solution obtenue quant aux procédures de résolution.La thèse est divisée en trois parties principales : une introduction composée par le Chapitre 1, une définition théorique du nouvel algorithme dans le Chapitre 2 et l'application de cette nouvelle méthodologie à deux problèmes concrets d'optimisation, tels que la sélection optimale du portefeuille avec le critère moyenne-variance dans le Chapitre 3 et le problème du sac à dos non linéaire dans le Chapitre 4. Conclusions et questions ouvertes sont présentées dans le Chapitre 5. / This thesis presents a new algorithm for Mixed Integer NonLinear Programming, inspired by the Multiplicative Weights Update framework and relying on a new class of reformulations, called the pointwise reformulations.Mixed Integer NonLinear Programming is a hard and fascinating topic in Mathematical Optimization both from a theoretical and a computational viewpoint. Many real-word problems can be cast this general scheme and, usually, are quite challenging in terms of efficiency and solution accuracy with respect to the solving procedures.The thesis is divided in three main parts: a foreword consisting in Chapter 1, a theoretical foundation of the new algorithm in Chapter 2, and the application of this new methodology to two real-world optimization problems, namely the Mean-Variance Portfolio Selection in Chapter 3, and the Multiple NonLinear Separable Knapsack Problem in Chapter 4. Conclusions and open questions are drawn in Chapter 5.

La tolérance aux pannes est une propriété très importante des réseaux optiques de nouvelle génération. Cette thèse aborde la conception des mécanismes de protection contre des pannes liées à la défaillance d’une fibre optique ou à une catastrophe naturelle. Deux systèmes de protection classiques, à savoir la protection par des cycles préconfigurés(p-cycles) et la protection du chemin de secours, sont étudiés pour atteindre une efficacité de protection élevée, tout en considérant le coût de l’équipement optique,la consommation d’énergie et l’utilisation de la ressource spectrale. Ces problèmes de survivabilité sont d’abord formulés en utilisant la programmation linéaire en nombres entiers (PLNE), et ensuite résolus soit par algorithmes heuristiques, soit par une approche de décomposition.La panne d’une seule fibre optique est le scénario le plus courant. Nous allons donc considérer d’abord des pannes liées à la défaillance d’une fibre optique dans les réseaux optiques multi-débit. Pour réduire le coût des transpondeurs, un système de protection par p-cycles de longueur adaptable et peu coûteux est proposé. Spécifiquement, les p cycles de longueur limitée sont conçus pour utiliser un débit approprié en fonction du coût du transpondeur et de la portée de transmission. Un modèle de programmation linéaire en nombres entiers (PLNE) sans énumération des cycles candidats est formulé pour générer directement les p-cycles de coût dépenses d’investissement minimum. De plus, un algorithme GPA (Graph Partitioning in Average) et un algorithme d’estimation des nombres de cycles (EI) sont développés pour rendre le modèle PLNE plus efficace au niveau du temps de calcul. En ce qui concerne la consommation d’énergie des réseaux optiques élastiques résilients,nous proposons d’utiliser un schéma de p-cycles dirigés, efficaces en énergie,pour protéger le trafic asymétrique. En raison de l’avantage de distinguer du volume de trafic dans les deux directions, les p-cycles dirigés consomment peu d’énergie en attribuant de créneaux ou slots du spectre et des formats de modulation différents à chaque direction.Un modèle PLNE est formulé pour minimiser la consommation d’énergie totale sous contraintes de génération du cycle dirigée, d’allocation de spectre, d’adaptation de modulation et de capacité de protection. Pour le passage à l’échelle, le modèle PLNE est décomposé en deux sous-problèmes: une méthode d’énumération de cycles améliorée et un modèle PLNE simplifié pour la sélection des cycles. Nous avons montré que les p-cycles dirigés obtiennent une meilleure performance comparant les p-cyclesiii non-dirigés pour le trafic asymétrique en termes de la consommation d’énergie et de l’utilisation du spectre.Afin d’améliorer l’efficacité d’utilisation du spectre dans réseaux optiques élastiques, une protection par p-cycles (SS-p-cycle) à spectre partagé est proposée. Les SS-p-cycles permettent de réduire l’utilisation du spectre et le taux de fragmentation spectrale en exploitant un partage de spectre spécial entre plusieurs p-cycles ayant des liens communs.Les modèles PLNE est conçus dans les cas "sans" ou "avec" conversion spectrale afin de minimiser l’utilisation du spectre. Ces modèles peuvent obtenir la solution optimale pour un petit réseaux optiques élastiques, et une heuristique efficace est développée pour résoudre les instances à grande échelle. Les résultats de simulations montrent que les SS-p-cycles ont des avantages significatifs pour réduire l’utilisation de la ressource spectrale et la défragmentation des fréquence. De plus, la conversion du spectre aide les SS-p-cycles à acquérir une meilleure utilisation du spectre. / Network survivability is a critical issue for optical networks to maintain resilience against network failures. This dissertation addresses several survivability design issues against single link failure and large-scale disaster failure in optical networks. Twoclassic protection schemes, namely pre-configured Cycles (p-Cycle) protection and path protection, are studied to achieve high protection capacity efficiency while taking intoaccount the equipment cost, power consumption and resource usage. These survivable network design problems are first formulated by mathematical models and then offered scalable solutions by heuristic algorithms or a decomposition approach.We first consider single link failure scenario. To cut the multi-line rates transponderscost in survivable Mixed-Line-Rate (MLR) optical networks, a distance-adaptive andlow Capital Expenditures (CAPEX) cost p-cycle protection scheme is proposed withoutcandidate cycle enumeration. Specifically, path-length-limited p-cycles are designed touse appropriate line rate depending on the transponder cost and transmission reach.A Mixed Integer Linear Programming (MILP) model is formulated to directly generate the optimal p-cycles with the minimum CAPEX cost. Additionally, Graph Partitioning in Average (GPA) algorithm and Estimation of cycle numbers (EI) algorithm are developed to make the proposed MILP model scalable, which are shown to be efficient.Regarding the power consumption in survivable Elastic Optical Networks (EONs),power-efficient directed p-cycle protection scheme for asymmetric traffic is proposed.Owing to the advantage of distinguishing traffic amount in two directions, directedp-cycles consume low power by allocating different Frequency Slots (FSs) and modulation formats for each direction. An MILP model is formulated to minimize total power consumption under constraints of directed cycle generation, spectrum assignment,modulation adaptation and protection capacity allocation. To increase the scalability, the MILP model is decomposed into an improved cycle enumeration and a simplified Integer Linear Programming (ILP) model. We have shown that the directedp-cycles out perform the undirected p-cycles in terms of power consumption and spectrum usage.In order to improve the spectrum usage efficiency in p-cycle protection, a SpectrumShared p-cycle (SS-p-cycle) protection is proposed for survivable EONs with and without spectrum conversion. SS-p-cycles permit to reduce spectrum usage and Spectrum Fragmentation Ratio (SFR) by leveraging potential spectrum sharing among multiplep-cycles that have common link(s). The ILP formulations are designed in both cases of with and without spectrum conversion to minimize the spectrum usage of SS-p-cycleswhich can obtain the optimal solution in small instance, and a time-efficient heuristic algorithm is developed to solve large-scale instances. Simulation results show that SSp-cycles have significant advantages on both spectrum allocation and defragmentation efficiency, and the spectrum conversion does help SS-p-cycle design to acquire better spectrum utilization.

In contexts involving multiple agents (players), determining how they can cooperate through the formation of coalitions and how they can share surplus benefits coming from the collaboration is crucial. This can provide decision-aid to players and analysis tools for policy makers regulating economic markets. Such settings belong to the field of cooperative game theory. A critical element in this area has been the size of the representation of these games: for each possible partition of players, the value of each coalition on it must be provided. Symmetric partition function form games (SPFGs) belong to a class of cooperative games with two important characteristics. First, they account for externalities provoked by any group of players joining forces or splitting into subsets on the remaining coalitions of players. Second, they consider that players are indistinct, meaning that only the number of players in each coalition is relevant for the SPFG. Using mixed-integer programming, we present the first representation of SPFGs that is polynomial on the number of players in the game. We also characterize the family of SPFGs that we can represent. In particular, the representation is able to encode exactly all SPFGs with five players or less. Furthermore, we provide a compact representation approximating SPFGs when there are six players or more and the SPFG cannot be represented exactly. We also introduce a flexible framework that uses stability methods inspired from the literature to identify a stable social-welfare maximizing game outcome using our representation. We showcase the value of our compact (approximated) representation and approach to determine a stable partition and payoff allocation to a competitive market from the literature. / Dans tout contexte impliquant plusieurs agents (joueurs), il est impératif de déterminer comment les agents coopéreront par la formation de coalitions et comment ils partageront les bénéfices supplémentaires issus de la collaboration. Ceci peut fournir une aide à la décision aux joueurs, ou encore des outils d'analyse pour les responsables en charge de réguler les marchés économiques. De telles situations relèvent de la théorie des jeux coopérative. Un élément crucial de ce domaine est la taille de la représentation de ces jeux : pour chaque partition de joueurs possible, la valeur de chaque coalition qu'on y retrouve doit être donnée. Les jeux symétriques à fonction de partition (SPFG) appartiennent à une classe de jeux coopératifs possédant deux caractéristiques principales. Premièrement, ils sont sensibles aux externalités, provoquées par n'importe quel groupe de joueurs qui s'allient ou défont leurs alliances, qui sont ressenties par les autres coalitions de joueurs. Deuxièmement, ils considèrent que les joueurs sont indistincts, et donc que seul le nombre de joueurs dans chaque coalition est à retenir pour représenter un SPFG. Par l'utilisation d'outils de programmation mixte en nombres entiers, nous présentons la première représentation de SPFG qui est polynomiale en nombre de joueurs dans le jeu. De surcroît, nous caractérisons la famille des SPFG qu'il est possible de représenter, qui inclut notamment tous les SPFG de cinq joueurs ou moins. De plus, elle dispose d'une approximation compacte pour le cas où, dans un jeu à six joueurs ou plus, le SPFG ne peut pas être représenté de façon exacte. Également, nous introduisons un cadre flexible qui utilise des méthodes visant la stabilité inspirées par la littérature pour identifier, à l'aide de notre représentation, une issue stable qui maximise le bien-être social des joueurs. Nous démontrons la valeur de notre représentation (approximée) compacte et de notre approche pour sélectionner une partition stable et une allocation des profits dans une application de marché compétitif provenant de la littérature.

De nos jours, atteindre un niveau élevé de satisfaction des employés à l’intérieur d’horaires efficients est une tâche importante et ardue à laquelle les compagnies font face. Dans ce travail, nous abordons une nouvelle variante du problème de création d’horaire de personnel face à une demande inconnue, en tenant compte de la satisfaction des employés via l’incertitude endogène qui découle de la combinaison des préférences des employés envers les horaires, et de ceux qu’ils reçoivent. Nous abordons ce problème dans le contexte de la création d’horaire d’employés remplaçants, un problème opérationnel de l’industrie du transport en commun qui n’a pas encore été étudié, bien qu’assez présent dans les compagnies nord-américaines. Pour faire face aux défis qu’amènent les deux sources d’incertitude, les absences des employés réguliers et des employés remplaçants, nous modélisons ce problème en un programme stochastique en nombres entiers à deux étapes avec recours mixte en nombres entiers. Les décisions de première étape consistent à trouver les journées de congé des employés remplaçants. Une fois que les absences inconnues des employés réguliers sont révélées, les décisions de deuxième étape consistent à planifier les tâches des employés remplaçants. Nous incorporons les préférences des employés remplaçants envers les journées de congé dans notre modèle pour observer à quel point la satisfaction de ces employés peut affecter leurs propres taux d’absence. Nous validons notre approche sur un an de données de la ville de Los Angeles. Notre travail est présentement en cours d’implémentation chez un fournisseur mondial de solutions logicielles pour les opérations de transport en commun. / Nowadays, reaching a high level of employee satisfaction in efficient schedules is an important and difficult task faced by companies. In this work, we tackle a new variant of the personnel scheduling problem under unknown demand by considering employee satisfaction via endogenous uncertainty depending on the combination of their preferred and received schedules. We address this problem in the context of reserve staff scheduling, an operational problem from the transit industry that has not yet been studied, although rather present in North American transit companies. To handle the challenges brought by the two uncertainty sources, regular employee and reserve employee absences, we formulate this problem as a two-stage stochastic integer program with mixed-integer recourse. The first-stage decisions consist in finding the days off of the reserve employees. After the unknown regular employee absences are revealed, the second-stage decisions are to schedule the reserve staff duties. We incorporate reserve employees’ preferences for days off into the model to examine how employee satisfaction may affect their own absence rates. We validate our approach on one year of data from the city of Los Angeles. Our work is currently being implemented in a world-leader software solutions provider for public transit operations.

Plusieurs pays possèdent des programmes de don croisé de rein (PDCR). Le but de ces programmes est d’aider les patients ayant un donneur incompatible à obtenir une greffe, en échangeant les donneurs incompatibles entre les patients. Pour pouvoir obtenir des bassins de paires incompatibles de plus grande taille, il est possible d’élargir les PDCR pour y inclure plusieurs pays ou hôpitaux. Par contre, on doit s’attendre à ce que ces derniers agissent de façon stratégique pour maximiser le nombre de leurs patients obtenant une greffe. Avec ce cadre, on peut définir le problème de don croisé de rein à plusieurs agents. Dans ce mémoire, nous modélisons ce problème comme un jeu coopératif à utilité non- transférable et nous présentons le noyau faible comme solution à ce jeu. Nous étudions empiriquement notre solution sur des exemples basés sur des données réelles et montrons qu’elle est atteignable en pratique. Nous comparons aussi le noyau faible à une autre solution présente dans la littérature: les couplages résistants aux rejets. / In various countries, kidney paired donation programs (KPDs) are implemented. These programs aim to help patients with an incompatible donor to obtain a transplant by swapping the donors between the patients. In order to increase the size of the pool of incompatible patient-donor pairs and potentially enhance patient benefits, KPDs can be extended to include multiple countries or hospitals. However, unlike existing nationwide KPDs, strategic behaviour from these entities (agents) is to be expected. This gives rise to the multi-agent kidney exchange problem. In this work, we model for the first time this problem as a non-transferable utility game. We also propose and argue in favour of the use of the weak core as a solution concept for the game. Using integer programming tools, we empirically study our solution concept on instances from the literature, which are derived from real-world data, and show that it is attainable in practice. We also compare the weak core to another recently presented solution concept from the literature, the rejection-proof matching.

Cette thèse aborde les facettes dynamiques des principes fondamentaux du problème de l'appariement stable plusieurs-à-un. Nous menons notre étude dans le contexte du choix de l'école et de l'appariement entre les hôpitaux et les résidents. Dans la première étude, en utilisant le modèle résident-hôpital, nous étudions la complexité de calcul de l'optimisation des variations de capacité des hôpitaux afin de maximiser les résultats pour les résidents, tout en respectant les contraintes de stabilité et de budget. Nos résultats révèlent que le problème de décision est NP-complet et que le problème d'optimisation est inapproximable, même dans le cas de préférences strictes et d'allocations de capacités disjointes. Ces résultats posent des défis importants aux décideurs qui cherchent des solutions efficaces aux problèmes urgents du monde réel. Dans la seconde étude, en utilisant le modèle du choix de l'école, nous explorons l'optimisation conjointe de l'augmentation des capacités scolaires et de la réalisation d'appariements stables optimaux pour les étudiants au sein d'un marché élargi. Nous concevons une formulation innovante de programmation mathématique qui modélise la stabilité et l'expansion des capacités, et nous développons une méthode efficace de plan de coupe pour la résoudre. Des données réelles issues du système chilien de choix d'école valident l'impact potentiel de la planification de la capacité dans des conditions de stabilité. Dans la troisième étude, nous nous penchons sur la stabilité de l'appariement dans le cadre de priorités dynamiques, en nous concentrant principalement sur le choix de l'école. Nous introduisons un modèle qui tient compte des priorités des frères et sœurs, ce qui nécessite de nouveaux concepts de stabilité. Notre recherche identifie des scénarios où des appariements stables existent, accompagnés de mécanismes en temps polynomial pour leur découverte. Cependant, dans certains cas, nous prouvons également que la recherche d'un appariement stable de cardinalité maximale est NP-difficile sous des priorités dynamiques, ce qui met en lumière les défis liés à ces problèmes d'appariement. Collectivement, cette recherche contribue à une meilleure compréhension des capacités et des priorités dynamiques dans les scénarios d'appariement stable et ouvre de nouvelles questions et de nouvelles voies pour relever les défis d'allocation complexes dans le monde réel. / This research addresses the dynamic facets in the fundamentals of the many-to-one stable matching problem. We conduct our study in the context of school choice and hospital-resident matching. In the first study, using the resident-hospital model, we investigate the computational complexity of optimizing hospital capacity variations to maximize resident outcomes, while respecting stability and budget constraints. Our findings reveal the NP-completeness of the decision problem and the inapproximability of the optimization problem, even under strict preferences and disjoint capacity allocations. These results pose significant challenges for policymakers seeking efficient solutions to pressing real-world issues. In the second study, using the school choice model, we explore the joint optimization of increasing school capacities and achieving student-optimal stable matchings within an expanded market. We devise an innovative mathematical programming formulation that models stability and capacity expansion, and we develop an effective cutting-plane method to solve it. Real-world data from the Chilean school choice system validates the potential impact of capacity planning under stability conditions. In the third study, we delve into stable matching under dynamic priorities, primarily focusing on school choice. We introduce a model that accounts for sibling priorities, necessitating novel stability concepts. Our research identifies scenarios where stable matchings exist, accompanied by polynomial-time mechanisms for their discovery. However, in some cases, we also prove the NP-hardness of finding a maximum cardinality stable matching under dynamic priorities, shedding light on challenges related to these matching problems. Collectively, this research contributes to a deeper understanding of dynamic capacities and priorities within stable matching scenarios and opens new questions and new avenues for tackling complex allocation challenges in real-world settings.

Dans le cadre industriel et académique, les méthodologies de développement logiciel exploitent de plus en plus le concept de “modèle” afin d’appréhender la complexité des systèmes temps réel critiques. En particulier, celles-ci définissent une étape dans laquelle un modèle fonctionnel, conçu comme un graphe de blocs fonctionnels communiquant via des échanges de signaux de données, est déployé sur un modèle de plateforme d’exécution matérielle et un modèle de plateforme d’exécution logicielle composé de tâches et de messages. Cette étape appelée étape de déploiement, permet d’établir une architecture opérationnelle du système nécessitant une validation des propriétés temporelles du système. Dans le contexte des systèmes temps réel dirigés par les évènements, la vérification des propriétés temporelles est réalisée à l’aide de l’analyse d’ordonnançabilité basée sur l’analyse des temps de réponse. Chaque choix de déploiement effectué a un impact essentiel sur la validité et la qualité du système. Néanmoins, les méthodologies existantes n’offrent pas de support permettant de guider le concepteur d’applications durant l’exploration de l’espace des architectures possibles. L’objectif de ces travaux de thèse consiste à mettre en place des techniques d’analyse et de synthèse automatiques permettant de guider le concepteur vers une architecture opérationnelle valide et optimisée par rapport aux performances du système. Notre proposition est dédiée à l’exploration de l’espace des architectures en tenant compte à la fois des quatre degrés de liberté déterminés durant la phase de déploiement, à savoir (j) le placement des éléments fonctionnels sur les éléments de calcul et de communication de la plateforme d’exécution, (ii) le partitionnement des éléments fonctionnels en tâches temps réel et des signaux de données en messages, (iii) l’affectation de priorités d’exécution aux tâches et aux messages du système et (iv) l’attribution du mécanisme de protection des données partagées pour les systèmes temps réel périodiques. Nous nous intéressons principalement à la satisfaction des contraintes temporelles et celles liées aux capacités des ressources de la plateforme cible. De plus, nous considérons l’optimisation des latences de bout-en-bout et la consommation mémoire. Les approches d’exploration architecturale présentées dans cette thèse sont basées sur la technique d’optimisation PLNE (programmation linéaire en nombres entiers) et concernent à la fois les applications activées périodiquement et celles dont l’activation est pilotée par les données. Contrairement à de nombreuses approches antérieures fournissant une solution partielle au problème de déploiement, les méthodes proposées considèrent l’ensemble du problème de déploiement. Les approches proposées dans cette thèse sont évaluées à l’aide d’applications génériques et industrielles. / Modern development methodologies from the industry and the academia exploit more and more the ”model” concept to address the complexity of critical real-time systems. These methodologies define a key stage in which the functional model, designed as a network of function blocks communicating through exchanged data signals, is deployed onto a hardware execution platform model and implemented in a software model consisting of a set of tasks and messages. This stage so-called deployment stage allows establishment of an operational architecture of the system, thus it requires evaluation and validation of the temporal properties of the system. In the context of event-driven real-time systems, the verification of temporal properties is performed using the schedulability analysis based on the response time analysis. Each deployment choice has an essential impact on the validity and the quality of the system. However, the existing methodologies do not provide supportto guide the designer of applications in the exploration of the operational architectures space. The objective of this thesis is to develop techniques for analysis and automatic synthesis of a valid operational architecture optimized with respect to the system performances. Our proposition is dedicated to the exploration of architectures space considering at the same time the four degrees of freedom determined during the deployment phase, (i) the placement of functional elements on the computing and communication resources of the execution platform, (ii) the partitioning of function elements into real time tasks and data signals into messages, (iii) the priority assignment to system tasks and messages and (iv) the assignment of shared data protection mechanism for periodic real-time systems. We are mainly interested in meeting temporal constraints and memory capacity of the target platform. In addition, we are focusing on the optimization of end-to-end latency and memory consumption. The design space exploration approaches presented in this thesis are based on the MILP (Mixed Integer Linear programming) optimization technique and concern at the same time time-driven and data-driven applications. Unlike many earlier approaches providing a partial solution to the deployment problem, our methods consider the whole deployment problem. The proposed approaches in this thesis are evaluated using both synthetic and industrial applications.