Les réseaux maillés sans fil sont une solution efficace, de plus en plus mise en œuvre en tant qu’infrastructure, pour interconnecter les stations d’accès des réseaux radio. Ces réseaux doivent absorber une croissance très forte du trafic généré par les terminaux de nouvelle génération. Cependant, l’augmentation du prix de l’énergie, ainsi que les préoccupations écologiques et sanitaires, poussent à s’intéresser à la minimisation de la consommation énergétique de ces réseaux. Ces travaux de thèse s’inscrivent dans les problématiques d’optimisation de la capacité et de la minimisation de la consommation énergétique globale des réseaux radio maillés. Nous définissons la capacité d’un réseau comme la quantité de trafic que le réseau peut supporter par unité de temps. Ces travaux s’articulent autour de quatre axes. Tout d’abord, nous abordons le problème d’amélioration de la capacité des réseaux radio maillés de type WIFI où l’accès au médium radio se base sur le protocole d’accès CSMA/CA. Nous mettons en lumière, les facteurs déterminants qui impactent la capacité du réseau, et l’existence d’un goulot d’étranglement qui limite cette capacité du réseau. Ensuite, nous proposons une architecture de communication basée sur l’utilisation conjointe de CSMA/CA et de TDMA afin de résoudre ce problème de goulot d’étranglement. Dans la deuxième partie de cette thèse, nous nous intéressons aux réseaux maillés sans fil basés sur un partage des ressources temps-fréquence. Afin de calculer des bornes théoriques sur les performances du réseau, nous développons des modèles d’optimisation basés sur la programmation linéaire et la technique de génération de colonnes. Ces modèles d’optimisation intègrent un modèle d’interférence SINR avec contrôle de puissance continue et variation de taux de transmission. Ils permettent, en particulier, de calculer une configuration optimale du réseau qui maximise la capacité ou minimise la consommation d’énergie. Ensuite, dans le troisième axe de recherche, nous étudions en détail le compromis entre la capacité du réseau et la consommation énergétique. Nous mettons en évidence plusieurs résultats d’ingénierie nécessaires pour un fonctionnement optimal d’un réseau maillé sans fil. Enfin, nous nous focalisons sur les réseaux cellulaires hétérogènes. Nous proposons des outils d’optimisation calculant une configuration optimale des stations de base qui maximise la capacité du réseau avec une consommation efficace d’énergie. Ensuite, afin d’économiser l’énergie, nous proposons une heuristique calculant un ordonnancement des stations et leur mise en mode d’endormissement partiel selon deux stratégies différentes, nommées LAFS et MAFS. / Wireless mesh networks (WMN) are a promising solution to support high data rate and increase the capacity provided to users, e.g. for meeting the requirements of mobile multimedia applications. However, the rapid growth of traffic load generated by the terminals is accompanied by an unsustainable increase of energy consumption, which becomes a hot societal and economical challenges. This thesis relates to the problem of the optimization of network capacity and energy consumption of wireless mesh networks. The network capacity is defined as the maximum achievable total traffic in the network per unit time. This thesis is divided into four main parts. First, we address the problem of improvement of the capacity of 802.11 wireless mesh networks. We highlight some insensible properties and deterministic factors of the capacity, while it is directly related to a bottleneck problem. Then, we propose a joint TDMA/CSMA scheduling strategy for solving the bottleneck issue in the network. Second, we focus on broadband wireless mesh networks based on time-frequency resource management. In order to get theoretical bounds on the network performances, we formulate optimization models based on linear programming and column generation algorithm. These models lead to compute an optimal offline configuration which maximizes the network capacity with low energy consumption. A realistic SINR model of the physical layer allows the nodes to perform continuous power control and use a discrete set of data rates. Third, we use the optimization models to provide practical engineering insights on WMN. We briefly study the tradeoff between network capacity and energy consumption using a realistic physical layer and SINR interference model. Finally, we focus on capacity and energy optimization for heterogeneous cellular networks. We develop, first, optimization tools to calculate an optimal configuration of the network that maximizes the network capacity with low energy consumption. We second propose a heuristic algorithm that calculates a scheduling and partial sleeping of base stations in two different strategies, called LAFS and MAFS.

Les systèmes temps-réel critiques sont de plus en plus complexes, et les exigences fonctionnelles et non-fonctionnelles ne cessent plus de croître. Le flot de conception de tels systèmes doit assurer, parmi d’autres propriétés, le déterminisme fonctionnel et la prévisibilité temporelle. Le déterminisme fonctionnel est inhérent aux modèles de calcul flot de données (ex. KPN, SDF, etc.) ; c’est pour cela qu’ils sont largement utilisés pour modéliser les systèmes embarqués de traitement de flux. Un effort considérable a été accompli pour résoudre le problème d’ordonnancement statique périodique et à mémoire de communication bornée des graphes flot de données. Cependant, les systèmes embarqués temps-réel optent de plus en plus pour l’utilisation de systèmes d’exploitation temps-réel et de stratégies d’ordonnancement dynamique pour gérer les tâches et les ressources critiques. Cette thèse aborde le problème d’ordonnancement temps-réel dynamique des graphes flot de données ; ce problème consiste à assigner chaque acteur dans un graphe à une tâche temps-réel périodique (i.e. calcul des périodes, des phases, etc.) de façon à : (1) assurer l’ordonnançabilité des tâches sur une architecture et pour une stratégie d’ordonnancement (ex. RM, EDF) données ; (2) exclure statiquement les exceptions d’overflow et d’underflow sur les buffers de communication ; et (3) optimiser les performances du système (ex. maximisation du débit, minimisation des tailles des buffers). / The ever-increasing functional and nonfunctional requirements in real-time safety-critical embedded systems call for new design flows that solve the specification, validation, and synthesis problems. Ensuring key properties, such as functional determinism and temporal predictability, has been the main objective of many embedded system design models. Dataflow models of computation (such as KPN, SDF, CSDF, etc.) are widely used to model stream-based embedded systems due to their inherent functional determinism. Since the introduction of the (C)SDF model, a considerable effort has been made to solve the static-periodic scheduling problem. Ensuring boundedness and liveness is the essence of the proposed algorithms in addition to optimizing some nonfunctional performance metrics (e.g. buffer minimization, throughput maximization, etc.). However, nowadays real-time embedded systems are so complex that real-time operating systems are used to manage hardware resources and host real-time tasks. Most of real-time operating systems rely on priority-driven scheduling algorithms (e.g. RM, EDF, etc.) instead of static schedules which are inflexible and difficult to maintain. This thesis addresses the real-time scheduling problem of dataflow graph specifications; i.e. transformation of the dataflow specification to a set of independent real-time tasks w.r.t. a given priority-driven scheduling policy such that the following properties are satisfied: (1) channels are bounded and overflow/underflow-free; (2) the task set is schedulable on a given uniprocessor (or multiprocessor) architecture. This problem requires the synthesis of scheduling parameters (e.g. periods, priorities, processor allocation, etc.) and channel capacities. Furthermore, the thesis considers two performance optimization problems: buffer minimization and throughput maximization.

L’agriculture française est soumise à de fortes pressions. Elle subit une injonction forte à évoluer vers l’agroécologie, à adopter les principes de la production intégrée, à réduire l’usage de pesticides. Dans ces conditions, une transition vers des systèmes agricoles plus respectueux de l’environnement ne doit pas dégrader la compétitivité des exploitations et le revenu des agriculteurs.Le travail présenté ici a pour ambition de contribuer à la réflexion sur les possibilités de changer les modèles d’agriculture. L’objectif est d’évaluer les conséquences économiques et environnementales d’une adoption généralisée des principes de protection intégrée sur une région agricole en fonction de la diversité des situations de production. La Région Bourgogne est retenue dans le cadre de ce travail. Elle dispose de ressources expérimentales en production intégrée grâce à l’investissement historique de la recherche, du développement et de l’enseignement agricole dans cette région. Par ailleurs, la Bourgogne présente un bon compromis entre la diversité de ses situations de production en grandes cultures et le nombre de situations contrastées à considérer pour rendre compte de l’ensemble du territoire. Dans un premier temps, nous avons caractérisé la diversité des situations de production de la Bourgogne et la diversité des systèmes de culture, et nous avons étudié comment les systèmes de culture sont déterminés par les situations de production. Puis nous avons mis en place une méthode pour générer des systèmes de culture optimisés sur le plan économique dans le cadre des contraintes locales et des principes de protection intégrée. Cette méthode mobilise la programmation linéaire sous contrainte, mise en œuvre avec le logiciel GAMS. Elle a été testée pour deux situations de production contrastées de la Bourgogne, correspondant aux zones de plaines sans élevage et aux plateaux argilo-calcaires superficiels. Nous avons évalué les systèmes de culture simulés pour un ensemble de critères de la durabilité économique, sociale et environnementale. Nous les avons comparés aux performances des systèmes actuels dans ces milieux.Les résultats confirment que les systèmes de culture optimisés avec les principes de la protection intégrée sont différents en fonction du contexte de production. La performance économique est plutôt améliorée par rapport aux systèmes actuels dans la situation à fort potentiel, alors qu’elle est dégradée sur les sols de plateaux. Tous les indicateurs environnementaux considérés sont améliorés dans les deux types de milieu. Le travail permet d’identifier certains inconvénients de la protection intégrée, liés à l’augmentation de la charge de travail et à la complexité de gestion des systèmes.Avec les résultats obtenus et les méthodes proposées, le travail alimente les débats sur la durabilité des systèmes agricoles dans le domaine des grandes cultures. / The agriculture in France is under intense pressure. Farmers are asked to change their crop management, to evolve toward agroecology, to follow the principles of Integrated Pest Management (IPM) and to reduce pesticide use. However such an evolution toward an alternative agricultural model will be possible only if innovative cropping systems are able to maintain competitive and profitable farms.The aim of our work is to contribute to the debates about this issue, by evaluating ex ante the potential consequences of adopting the principles of IPM over one whole agricultural region, taking into account the diversity of production situations within this region. We considered the Burgundy region for several reasons. This region has many experimental resources and available expertise on IPM. This agricultural area also has few but contrasted production situations. Both economic and environmental issues were considered.First, we studied the diversity of production situations and of cropping systems in the area, based on agricultural data sets, and we showed to what extent cropping systems are determined by the context. Then we developed a method to design fictive cropping systems, based on the optimisation of profitability while fulfilling the principles of IPM, and considering the constraints of the production situation. We used the GAMS software to implement this method based on linear programming. The method was tested on two contrasted production situations, namely the lowlands with high agricultural potential and no livestock, and the shallow soils of the plateau. We evaluated the generated cropping systems for a range of criteria covering different issues of sustainability, and we compared the performances to those of current cropping systems in these areas.Results corroborated that IPM-based cropping systems would be different in contrasted production situations. Profitability would be improved in the lowlands with high agricultural potential, whereas it would be negatively affected in the shallow soils of the uplands. All the environmental indicators that we used would be improved in both situations. Our work identified hindrances for the development of IPM, related for example to the increase in the workload at the farm level, and the increase in the system complexity.Both methods that we developed and the results we obtained should contribute to the current debates about the possible transition of arable cropping toward sustainability.

Le problème de dimensionnement et planification d'agents en centre d'appels consiste à déterminer sur une période le nombre d'interlocuteurs requis afin d'atteindre la qualité de service exigée et minimiser les coûts induits. Ce sujet fait l'objet d'un intérêt croissant pour son intérêt théorique mais aussi pour l'impact applicatif qu'il peut avoir. Le but de cette thèse est d'établir des approches en contraintes en probabilités en considérant l'incertitude de la demande.Tout d'abord, la thèse présente un modèle en problème d'optimisation stochastique avec contrainte en probabilité jointe traitant la problématique complète en une étape afin d'obtenir un programme facile à résoudre. Une approche basée sur l'idée de continuité est proposée grâce à des lois de probabilité continues, une nouvelle relation entre les taux d'arrivées et les besoins théoriques et la linéarisation de contraintes. La répartition du risque global est faite pendant le processus d'optimisation, permettant une solution au coût réduit. Ces solutions résultantes respectent le niveau de risque tout en diminuant le coût par rapport à d'autres approches.De plus, le modèle en une étape est étendu pour améliorer sa représentation de la réalité. D'une part, le modèle de file d'attente est amélioré et inclus la patience limitée des clients. D'autre part, une nouvelle expression de l'incertitude est proposée pour prendre la dépendance des périodes en compte.Enfin, une nouvelle représentation de l'incertitude est considérée. L'approche distributionally robust permet de modéliser le problème sous l'hypothèse que la loi de probabilité adéquate est inconnue et fait partie d'un ensemble de lois, défini par une moyenne et une variance données. Le problème est modélisé par une contrainte en probabilité jointe. Le risque à chaque période est définie par une variable à optimiser.Un problème déterministe équivalent est proposé et des approximations linéaires permettent d'obtenir une formulation d'optimisation linéaire. / The staffing and shift-scheduling problems in call centers consist in deciding how many agents handling the calls should be assigned to work during a given period in order to reach the required Quality of Service and minimize the costs. These problems are subject to a growing interest, both for their interesting theoritical formulation and their possible applicative effects. This thesis aims at proposing chance-constrained approaches considering uncertainty on demand forecasts.First, this thesis proposes a model solving the problems in one step through a joint chance-constrained stochastic program, providing a cost-reducing solution. A continuous-based approach leading to an easily-tractable optimization program is formulated with random variables following continuous distributions, a new continuous relation between arrival rates and theoritical real agent numbers and constraint linearizations. The global risk level is dynamically shared among the periods during the optimization process, providing reduced-cost solution. The resulting solutions respect the targeted risk level while reducing the cost compared to other approaches.Moreover, this model is extended so that it provides a better representation of real situations. First, the queuing system model is improved and consider the limited patience of customers. Second, another formulation of uncertainty is proposed so that the period correlation is considered.Finally, another uncertainty representation is proposed. The distributionally robust approach provides a formulation while assuming that the correct probability distribution is unknown and belongs to a set of possible distributions defined by given mean and variance. The problem is formulated with a joint chance constraint. The risk at each period is a decision variable to be optimized. A deterministic equivalent problem is proposed. An easily-tractable mixed-integer linear formulation is obtained through piecewise linearizations.

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.

L'hybridation des sources de puissance dans le domaine des applications embarquées s'est imposée comme une solution adéquate pour répondre aux législations environnementales et atteindre une meilleure efficacité énergétique. Toutefois, le choix dans le dimensionnement des composants et la stratégie de commande doivent répondre à un cahier des charges, souvent complexe et hétérogène, tout en limitant les coûts du système. La résolution de ce problème d'optimisation incluant de nombreuses variables peut s'avérer complexe à cause des non-linéarités présentes dans le problème formulé. Il faut donc disposer d'outils de résolution efficaces et capables de fournir une solution fiable. Dans cette thèse, nous proposons une méthode d'optimisation globale pour le dimensionnement et la commande optimale de véhicules hybrides basée sur l'optimisation combinatoire, et en particulier sur la programmation linéaire en nombres entiers (PLNE). A partir d'un problème d'optimisation non linéaire, le problème initial est reformulé en une multitude de sous-problèmes linéaires en nombres entiers sur lesquels un algorithme de Branch & Bound parallèle est exécuté. Afin de résoudre des problèmes de grande taille, un second algorithme basé sur le Branch & Cut est développé. Cette méthode est déployée pour l'étude d'un système d'alimentation hybride d'une mini-excavatrice électrique. Le problème d'optimisation, dans lequel des contraintes énergétiques et des contraintes de vieillissement sont implantées, est évalué suivant différents paramètres du cahier des charges. Enfin, cette approche est également appliquée pour l'optimisation de trajectoires d'un système multi-actionneur synchronisés. / Hybridization of power sources for embedded applications becomes an interesting solution to respect environmental legislation and achieve a higher energy efficiency. However, the choice for components sizing and the energy management strategy need to meet specifications while reducing costs. To solve this optimization problems including several types of variables can be complex because of non linearities included in the formulated problem. Therefore the use of effective solving tools, able to provide a reliable solution, is required. In this thesis, a global optimization method is proposed for the design and the optimal control of hybrid vehicles based on combinatorial optimization, particularly on integer linear programming. From a non-linear optimization problem, the initial problem is reformulated into a multitude of integer linear sub-problems for which a parallel Branch & Bound algorithm is executed. In order to solve large-scale problems, a second algorithm based on the Branch & Cut is developed. This method is used for the study of a hybrid power supply system of a mini-excavator electric. The optimization problem, where energy constraints and aging constraints are implemented, is evaluated according to several parameters and specifications. Finally, this approach is also applied for the optimization of trajectories for a synchronized multi-actuators system.

De nos jours, la demande en trafic mobile a considérablement augmenté. Face à cette croissance, plusieurs propositions font l'objet d'étude pour remédier à un tel défi. L’architecture des réseaux d’accès de type Cloud (C-RAN) est l’une des propositions pour faire face à cette demande croissante, et constitue une solution candidate potentielle pour les réseaux futurs 5G. L'architecture C-RAN dissocie deux éléments principaux de la station de base: La BBU ou ``Baseband Unit", qui constitue une unité intelligente pour le traitement des données en bande de base, et le RRH ou ``Remote Radio Head", constituant en une antenne passive pour fournir l'accès aux utilisateurs (UEs). Grâce à l’architecture C-RAN, les BBUs sont centralement regroupées, alors que les RRHs sont distribués sur plusieurs sites. Plusieurs avantages sont ainsi dérivés, tels que le gain en multiplexage statistique, l’efficacité d’utilisation des ressources, et l’économie de puissance. Contrairement à l’architecture conventionnelle où chaque RRH est exclusivement associé à une BBU, dans l’architecture C-RAN, plusieurs RRHs sont regroupés en une seule BBU lorsque les conditions de charge sont faibles. Ceci présente plusieurs avantages, tel que l’amélioration en efficacité énergétique et la minimisation en consommation de puissance. Dans cette thèse, nous adressons le problème d’optimisation des associations BBU-RRH. Nous nous intéressons à l’optimisation des regroupements des RRHs aux BBUs en tenant compte de critères multiples. Plusieurs contraintes sont ainsi envisagées, tel que la réduction de la consommation d'énergie sous garantie de Qualité de Service (QoS) minimale. En outre, la prise en compte du changement du niveau d’interférence en activant/désactivant les BBUs est primordiale pour l’amélioration de l’efficacité spectrale. En plus, décider dynamiquement de la réassociation des RRHs aux BBUs sous des conditions de charges variables représente un défi, vu que les UEs connectés aux RRHs changeant leurs associations font face à des ``handovers" (HOs). / The demand on mobile traffic has been largely increasing nowadays. Facing such growth, several propositions are being studied to cope with this challenge. Cloud-Radio Access Networks Architecture (C-RAN) is one of the proposed solutions to address the increased demand, and is a potential candidate for future 5G networks. The C-RAN architecture dissociates two main elements composing the base station: The Baseband Unit (BBU), consisting in an intelligent element to perform baseband tasks functionalities, and the Remote Radio Head (RRH), that consists in a passive antenna element to provide access for serviced User Equipments (UEs). In C-RAN architecture, the BBUs migrate to a Cloud data center, while RRHs remain distributed across multiple sites. Several advantages are derived, such as statistical multiplexing gain, efficiency in resource utilization and power saving. Contrarily to conventional architecture, where each RRH is associated to one BBU, in C-RAN architecture, multiple RRHs can be embraced by one single BBU when network load conditions are low, bringing along several benefits, such as enhanced energy efficiency, and power consumption minimization. In this thesis, the BBU-RRH association optimization problem is addressed. Our aim is to optimize the BBU-RRH association schemes, taking into consideration several criteria. The problem presents many constraints: For example, achieving minimized power consumption while guaranteeing a minimum level of Quality of Service (QoS) is a challenging task. Further, taking into account the interference level variation while turning ON/OFF BBUs is paramount to achieve enhanced spectral efficiency. Moreover, deciding how to re-associate RRHs to BBUs under dynamic load conditions is also a challenge, since connected UEs face handovers (HOs) when RRHs change their associations.

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.

Cette thèse s'inscrit dans la littérature relative au problème d'arbitrage durée, coût et qualité en gestion de projet. Nous développons un modèle d'accélération des projets de fabrication par le recours au travail temporaire et aux heures supplémentaires. Nous prenons en compte l'impact de la main d'œuvre additionnelle sur la durée via les pertes de productivité et sur la qualité des activités qui composent le projet. La qualité de toute activité est mesurée par le pourcentage d'items validés dans sa check-list de contrôle qualité. Nous proposons une formulation linéaire du problème de minimisation de la durée du projet sous contrainte de budget et de respect d'un seuil de qualité minimum pour chacune des activités que le projet comporte. Le programme d'optimisation mixte qui en résulte est appliqué au cas d'un projet de fabrication d'une motrice TGV et permet d'obtenir une planification prévisionnelle de la main d'œuvre pour atteindre la durée optimale d'exécution. Le modèle peut également être utilisé pour accélérer un projet en cours d'exécution ou à des fins plus stratégiques de dimensionnement des postes de travail. / We address the discrete time resource-constrained project scheduling problem in which each activity has a specified work content and its resource usage may vary from period to period. We consider temporary work and overtime as additional renewable resources for crashing the project. We assume that the project quality may be affected by crashing as well as its completion time through productivity loss due to overmanning. We develop a Mixed-Integer Linear Programming (MILP) model to minimise the makespan subject to a budget constraint and to acceptable quality levels for all activities so as to avoid rework. The proposed approach is applied to an actual manufacturing project of a very high speed train motor coach.

Le déséquilibre d'un sommet dans un graphe orienté est la valeur absolue de la différence entre son degré sortant et son degré entrant. Nous étudions le problème de trouver une orientation des arêtes du graphe telle que l'image du vecteur dont les composantes sont les déséquilibres des sommets par une fonction objectif f est maximisée. Le premier cas considéré est le problème de maximiser le minimum des déséquilibres sur toutes les orientations possibles. Nous caractérisons les graphes dont la valeur objective optimale est nulle. Ensuite nous donnons plusieurs résultats concernant la complexité du problème. Enfin, nous introduisons différentes formulations du problème et présentons quelques résultats numériques. Par la suite, nous montrons que le cas f=1/2 | |·| |₁ mène au célèbre problème de la coupe de cardinalité maximale. Nous introduisons de nouvelles formulations ainsi qu'un nouveau majorant qui domine celui de Goemans et Williamson. Des résultats théoriques et numériques concernant la performance des approches sont présentés. Pour finir, dans le but de renforcer certaines des formulations des problèmes étudiés, nous étudions une famille de polyèdres spécifique consistant en l'enveloppe convexe des matrices d'affectation 0/1 (où chaque colonne contient exactement une composante égale à 1) annexée avec l'indice de leur ligne non-identiquement nulle la plus basse. Nous donnons une description complète de ce polytope ainsi que certaines de ses variantes qui apparaissent naturellement dans le contexte de divers problèmes d'optimisation combinatoire. Nous montrons également que résoudre un programme linéaire sur un tel polytope peut s'effectuer en temps polynomial / The imbalance of a vertex in a directed graph is the absolute value of the difference between its outdegree and indegree. In this thesis we study the problem of orienting the edges of a graph in such a way that the image of the vector which components are the imbalances of the vertices of the graph under an objective function f is maximized. The first case considered is the problem of maximizing the minimum imbalance of all the vertices over all the possible orientations of the input graph. We first characterize graphs for which the optimal objective value is zero. Next we give several results concerning the computational complexity of the problem. Finally, we deal with several mixed integer programming formulations for this problem and present some numerical experiments. Next, we show that the case for f=1/2 | |·| |₁ leads to the famous unweighted maximum cut problem. We introduce some new formulations along with a new bound shown to be tighter than Michel Goemans & David Williamson's. Theoretical and computational results regarding bounds quality and performance are also reported. Finally, in order to strengthen some formulations of the studied problems, we study a specific class of polytopes. Consider the polytope consisting in the convex hull of the 0/1 assignment matrices where each column contains exactly one coefficient equal to 1 appended with their index of the lowest row that is not identically equal to the zero row. We give a full description of this polytope and some of its variants which naturally appear in the context of several combinatorial optimization problems. We also show that linear optimization over those polytopes can be done in polynomial time