Dans cette thèse, nous traitons essentiellement des problèmes de lot sizing en désassemblage avec une structure de produits à désassembler à deux niveaux sans composants communs. Nous traitons deux problèmes différents. Dans le premier problème, nous considérons un seul produit et la contribution porte sur le développement de deux modèles de programmation en nombres entiers. Le premier modèle est considéré sans ventes perdues où toutes les demandes doivent être satisfaites, et le deuxième est considéré avec ventes perdues où les demandes peuvent ne pas être satisfaites. Pour la résolution de ce problème, nous développons d’abord une approche analytique permettant de calculer les stocks de surplus (avant la résolution du problème) à la fin de l’horizon de planification. Ensuite, nous adaptons trois heuristiques connues pour leurs performances et largement utilisées dans le problème lot sizing en production « Silver Meal, Part Period Balancing et Least Unit Cost ». Dans le deuxième problème, nous considérons plusieurs produits avec contrainte de capacité et la contribution porte sur l’extension des deux modèles précédents. Le premier est également considéré sans ventes perdues et le deuxième avec ventes perdues. En ce qui concerne la résolution de ce problème et compte tenu de sa complexité, un algorithme génétique est d’abord proposé. Ensuite, afin d’améliorer cet algorithme, nous intégrons une heuristique Fix-and-Optimize dans ce dernier tout en proposant une approche hybride. Finalement, des tests sont effectués sur de nombreuses instances de la littérature afin de montrer l’efficacité et les limites de chaque approche de résolution / In this thesis, we mainly deal with lot sizing problems by disassembling with a structure of products to disassemble with two levels and without commonality components. We treat two different problems. In the first problem, we consider a single product whose contribution focuses on developing the two programming models integers. The first model is considered without lost sales where all demands must be satisfied, and the second one is considered with lost sales where demands may not be met. To solve this problem, we first develop an analytical approach to calculate the surplus stocks (before solving the problem) at the end of the planning horizon. Then we adapt three heuristics known for their performance and widely used in the lot sizing problem of production "Silver Meal, Part Period Balancing and Least Unit Cost". In the second problem, we consider a number of products with capacity constraint, and the contribution relates to the extension of the two previous models. The first is considered without lost sales and the second with lost sales. Regarding the resolution of this problem and given its complexity, a genetic algorithm is first proposed. Then, to improve this algorithm, we integrate a Fix-and-Optimize heuristic in the latter while offering a hybrid approach. Finally, various tests are performed on different literature instances to demonstrate the effectiveness and limitations of each solving approach

Cette thèse a pour but d’apporter des solutions méthodologiques pour la mutualisation des transports entre les fournisseurs et les plateformes de la grande distribution. Cette mutualisation permet en effet de réduire les coûts, les émissions de CO2, et d’augmenter la qualité de service. Elle est organisée autour d’un réseau de plateformes de cross-docking appelées Centres de Routage Collaboratifs, développé par la société 4S Network. Nos travaux consistent à modéliser et résoudre à l’aide de techniques de recherche opérationnelle plusieurs problèmes d’optimisation du transport dans le réseau mutualisé. Le verrou scientifique majeur est de résoudre conjointement un problème de plan de chargement (Service Network Design Problem) dans un réseau logistique national, et des problèmes de tournées de véhicules à une échelle régionale. Nous prenons en compte des contraintes additionnelles issues du monde industriel et les tarifs réellement pratiqués par les transporteurs, notamment des coûts non linéaires.Les problèmes d’optimisation résultants sont résolus au moyen de méthodes ditesmatheuristiques, c’est-à-dire combinant des approches exactes telles que la génération de colonnes et des approches (méta)heuristiques telles que la recherche tabou. Les algorithmes développés dans cette thèse ont donné lieu à unoutil logiciel aujourd’hui en exploitation chez 4S Network. / The main purpose of this PhD. thesis is to provide methodological solutions for a collaborative transport between suppliers and retail platforms. The outcomes of this collaboration are numerous:cost reduction, greenhouse gas emission reduction and higher quality of service. The network is structured around cross-docking platforms developed by the company 4S Network. We model and solve several optimization problems in this collaborative network, using operationsresearch techniques. The major scientific challenge is to simultaneously solve a Service Network Design Problem in a national logistics network and several Vehicle Routing Problems at regional level. We consider additional constraints and prevailing pricing arising from the carriers, in particular non-linear costs. The resulting optimization problems are solved by matheuristic methods, that combine exact approaches as column generation and (meta)heuristic approaches as tabu search. The algorithms developed in this thesis are the core functions of a software tool developed for 4S network.

Dans plusieurs pays européens, la capacité de l’infrastructure est complètement exploitée aux heures de pointe et aux points critiques : une grande quantité de trains traversent ces points critiques dans un laps de temps très réduit. Dans cette situation le retard d’un train provoqué par un conflit de circulation peut se propager dans tout le réseau. Le problème de la gestion opérationnelle du trafic ferroviaire consiste à trouver les modifications des itinéraires et des ordonnancements des trains qui minimisent la propagation des retards. Dans cette thèse, nous proposons une approche de décomposition de Benders pour la formulation linéaire en nombres entiers à variables mixtes utilisée dans l’algorithme RECIFE-MILP. Après avoir constaté que l’approche de décomposition standard de Benders ne permet pas de trouver rapidement une solution de bonne qualité pour certaines instances du problème, nous étudions trois approches alternatives afin d’améliorer la performance de notre algorithme. Nous proposons d’abord une approche que nous appelons la reformulation réduite de Benders. Ensuite, nous introduisons des inégalités dans la formulation du problème maître de Benders. Finalement, nous scindons le processus de résolution en trois étapes au lieu de deux comme dans la décomposition standard de Benders. L'analyse expérimentale montre que la combinaison de la première et dernière approche surpasse l’algorithme original RECIFE-MILP dans la résolution de grandes instances sous certaines conditions. / In railway systems, during congested traffic situations, the infrastructure capacity is completely exploited for trains circulation. In these situations, when traffic is perturbed some trains must be stopped or slowed down for ensuring safety, and delays occur. The real-time Railway Traffic Management Problem (rtRTMP) is the problem of modifying trains route and schedule to limit delay propagation. In this thesis, we propose a Benders decomposition of a MILP-based algorithm for this problem, named RECIFE-MILP. After observing that the standard Benders decomposition (BD) does not allow the effective solution of rtRTMP instances, we study three possible approaches to improve the performance. Specifically, we first propose a modification of the problem reformulation which is typical of BD, obtaining what we call reduced BD. Then, we introduce some inequalities to the Benders master problem. Finally, we split the solution process in three steps rather than two as in the standard BD. As we show in a thorough experimental analysis, the combination of the first and last approaches outperforms the original RECIFE-MILP algorithm when tackling large instances with some specific features.

Cette thèse s'inscrit dans le cadre du projet ANR HOST (Hôpital : Optimisation, Simulation et évitement des Tensions) qui vise à étudier et résoudre le problème de tension aux urgences hospitalières. Le projet cherche premièrement à définir rigoureusement la notion de tension et puis d'utiliser des outils mathématiques pour proposer des solutions qui prennent en compte la complexité du système de santé. Malgré la récurrence des phénomènes de tension, ils sont limités dans le temps et sollicitent par conséquent des solutions à court terme. La difficulté de trouver des solutions efficaces est principalement due à l'incertitude et au dynamisme caractéristique du service des urgences. D'une année à une autre, l'intensité de l'épidémie, et donc le nombre de patients se présentant aux urgences peut varier drastiquement. De plus, pour un même nombre de patients, il est difficile d'estimer correctement la charge de travail qu'il représente. L'objectif de cette thèse est donc de proposer des solutions stratégiques, tactiques et opérationnelles de gestion des ressources en prenant en compte les aléas caractéristiques des urgences. D'un point de vue stratégique nous étudions la distribution optimale de la capacité de travail sur une période épidémique. Ensuite, nous traitons le problème de confection des postes de travail journalier en fonction de la dynamique de la demande. Nous étudions également la possibilité d'affecter des postes d'astreinte aux médecins pendant les périodes épidémiques. Finalement, nous traitons le problème d'affectation des heures supplémentaires aux ressources dans un contexte plus opérationnel. / In France, the problem of overcrowding in Emergency Departments (ED) is particularly relevant today because of increasing admissions and budget restrictions in health establishments. Formally, overcrowding can be defined as a situation where the demand surpasses the service capacity. Studies that have dealt with ED overcrowding have mostly dealt with issues of patient flow management and resource management.Our work focuses on resource management and more particularly on the impact that human resources have on ED overcrowding. In the first part of the study, we formulate the capacity allocation problem in a generic form. As such, we examine the capacity management problem and derive interesting properties for a general demand distribution and a normal demand distribution. Then, we examine the cyclic shift scheduling problem as it exists in ED. This research allows us to examine different cyclic scheduling strategies and answer the question of whether lack of flexibility in the schedules has an impact on the waiting time of patients. We propose an original stochastic linear formulation for the problem that accounts for the non-stationary work demand. After that we evaluate two scheduling mechanisms to reduce overcrowding in EDs: on-call duties and overtime hours. We study the conditions under which these mechanisms can be beneficial. The on-call duties problem is modeled as a two-stage stochastic optimization problem and the overtime management problem as a Markov decision problem.

Dans les dernières décennies, l'augmentation de la consommation des services de soins et la croissance de la population ont fait de l'élimination du gaspillage et l'amélioration continue de la productivité de plus en plus cruciale pour les hôpitaux. La productivité et l'efficacité d'un hôpital dépendent des conditions de travail des soignants qui sont influencés fortement par l'organisation des lieux de travail et des installations [Dares (2013)]. L’agencement des installations consiste à "déterminer l'organisation physique d'un système de production et de trouver l’arrangement le plus efficace de ‘n’ installations dans ‘n’ positions" [Singh et Sharma (2006)]. L’agencement des installations a un grand impact sur la productivité et l'efficacité du fonctionnement d'un hôpital. Etant conscient de ce besoin, le travail que nous présentons vise à trouver une solution à l’agencement des salles du Bloc Opératoire "le coeur de l'hôpital", ainsi que les salles annexes en proposant un outil intelligent que nous mettons à la disposition des maitres d’ouvrages pour optimiser leur conception du bloc opératoire. Les méthodes que nous avons explorées pour la réalisation de ce travail sont les méthodes exactes, les heuristiques, les métaheuristiques et les méthodes intelligentes, ce qui nous a permis de comparer les différentes approches afin de fournir la meilleure solution pour différents scénarios de problèmes. Nous présentons les contributions majeures de notre travail, à commencer par l'application de la programmation mathématique en nombres entiers mixtes (Mixed Integer Programming (MIP)) pour résoudre le problème d’agencement du bloc opératoire (Operating Theater Layout Problem (OTLP)) comme la première contribution scientifique. Ce travail considère trois structures différentes (multi-section, multi-étage et multi-rangé) dans deux types d'environnement différents, tout en optimisant deux fonctions objectifs différents. La combinaison de ces différentes composantes donne lieu à neuf modèles MIP pour résoudre l’OTLP pour lesquels une solution optimale a été atteinte pour des problèmes avec jusqu'à quarante salles. L'utilisation de Systèmes Multi-Agents (MAS) pour résoudre le problème d’agencement des installations est la deuxième contribution scientifique que nous présentons dans le cinquième chapitre. Dans la littérature, on retrouve un seul travail [Tarkesh et al., (2009)] ayant appliqué le MAS pour résoudre des problèmes de petites tailles, ce qui rend notre travail, le premier adoptant MAS pour répondre à la fois le FLP sous environnement statique et dynamique pour des problèmes de grande taille en utilisant un algorithme en trois étapes pour résoudre OTLP. La plate-forme multi-agents développée exploite les trois différents protocoles de communication d’agents, à savoir la coordination, la coopération et la négociation pour concevoir différentes architectures d’agents afin de faire face à l’OTLP statique et dynamique. La dernière contribution consistant en l'utilisation de l’optimisation par essaim de particules (Particle Swarm Optimization (PSO)) sous une représentation continue de l’espace de recherche pour résoudre le problème d’agencement multi-rangée est présentée dans le sixième chapitre. Puisque la PSO est généralement utilisé pour résoudre les problèmes d’affectation ou les FLP avec une représentation discrète, la formulation actuelle est parmi les rares travaux traitant la représentation continue du FLP. Nous avons conçu une nouvelle technique de codage des particules et des heuristiques appropriées pour générer des solutions initiales et pour effectuer la procédure de recherche locale. Une autre nouveauté est liée à l'application de la PSO à un problème de structure multi-rangé, qui n'a pas été abordé auparavant car à notre connaissance, les travaux avec la PSO ont formulé le FLP comme une structure d’une seule rangée ou dans le meilleur des scénarios, comme une structure à deux rangées / In the last decades, the important increasing consumption of health care and the growing of population make elimination of waste and continuous productivity improvement more and more critical for hospitals to provide their care services effectively and efficiently. The productivity and efficiency of a hospital depends on the caregivers working conditions, which are impacted greatly by the work place and the facilities organization [Dares (2013)]. Facilities planning “determines the physical organization of a production system and finding the most efficient arrangement of ‘n’ indivisible facilities in ‘n’ locations” [Singh & Sharma (2006)]. Thus, facilities planning has a great impact on the productivity and efficiency of running a hospital. Being aware of this need, the work we present aims to find a solution to facilities planning for the Operating Theater “the heart of hospital” by proposing an intelligent tool we make available to decision makers for optimizing their operating theater design. Our research work focuses on the use of operational research methods in order to find a solution for this optimization problem. Methods we explored for the realization of this work were variant, namely exact algorithm, heuristics, metaheuristics and intelligent methods, which allow us to compare different issues in order to provide the best solution to different scenarios of problems. Thus, in this dissertation we present the major contribution of our work, starting with the application of Mixed Integer Programming (MIP) to solve Operating Theater Layout Problem (OTLP) as the first scientific contribution. This work considers three different formulations (i.e. the multi-sections, the multi-floors and the multi-rows) in two different environment types (i.e. static and dynamic) while optimizing two different objective functions (i.e. to minimize the total traveling cost and to maximize the total adjacency rate). The combination of these different components gives rise to nine MIP models to solve the OTLP for which optimal solution was provided to problems with until forty facilities. These contributions are presented in the third and fourth chapters. The use of Multi-Agent System (MAS) to solve Facility Layout Problem (FLP) is the second scientific contribution we present in chapter five. In literature, only one work [Tarkesh et al., (2009)] applied the MAS to solve small sized problems, which makes our work the first one adopting MAS to address both the static and dynamic FLP for large sized problems using a novel algorithm running in three steps to solve OTLP. The developed multi-agent platform exploit the three different agents’ protocols of communication, namely coordination, cooperation and negotiation to conceive different agents’ architectures to deal with the static and dynamic OTLP. The last contribution consisting on the use of Particle Swarm Optimization (PSO) under continuous layout representation to solve multi-rows FLP is presented in chapter six. Since the PSO is generally used to solve assignment problems or discrete FLP, the actual formulation is among the few works dealing with the continuous one. This leads us to conceive a novel encoding technique and the appropriate heuristics to generate initial solutions and to perform the local search procedure. Another novelty is related to the application of PSO to a multi-rows layout problem, which was not addressed before. To the best of our knowledge, PSO works usually formulate the FLP as a single row or in the best of scenarios, as a double-rows problem

Le Capital-Investissement et plus particulièrement les opérations de LBO, occupent une place importante dans l'économie mondiale et française. Ce travail de recherche a pour objet l'analyse de l'impact des leviers organisationnels et de gouvernance sur la performance opérationnelle et la rentabilité des entreprises françaises sous LBO. Nous présentons ainsi, en premier lieu, dans les deux premiers chapitres de cette thèse, une revue complète de la littérature, ainsi que le modèle théorique de l'impact des leviers organisationnels et de gouvernance sur la performance opérationnelle et la rentabilité des entreprises sous LBO en privilégiant une approche actionnariale de la gouvernance.Ensuite, dans le cadre des troisième et quatrième chapitres de cette thèse, nous examinons de façon empirique, d'une part, l'impact de la mise en place des opérations de LBO sur la performance opérationnelle des entreprises françaises, et, d'autre part, les effets des leviers organisationnels et de gouvernance sur la rentabilité des entreprises françaises sous LBO.Nos résultats confirment en partie les résultats anglo-saxons concernant l'impact positif des opérations de LBO sur la performance de la société cible, ils sont obtenus en effectuant une double analyse comparative : la première en comparant l'évolution de la performance avant et après la mise en place du LBO, et la deuxième en effectuant une comparaison par rapport à un groupe de contrôle composé d'entreprises aux caractéristiques comparables mais qui n'ont pas fait l'objet d'un LBO.Enfin, nous proposons un modèle explicatif des effets des leviers organisationnels et de gouvernance sur la rentabilité des entreprises sous LBO. / Private Equity, especially Leverage Buyout activity (LBO), is now an important concern in the world economy and also in France. This kind of investment is an important alternative to capital market.The main purpose of this thesis is to examine the effects of corporate governance and organizational mechanisms on the performance of French firms leveraged buyout.We presented in the first part of this thesis, the first and second chapter of it, the history of the emergence of these investments in the world and especially in France, and an overview of the literature on private equity and leveraged buyouts, focusing on our theoretical framework which is based on corporate governance theories, especially on agency theory and financial performance.Moreover, we discussed the literature about the relation between operating performance, corporate governance and Leverage Buyout. As part of this thesis and in the third and fourth chapters, we proposed an empirical study of the impact of LBO on operating performance.This research also proposes a new approach to the relationship governance-performance by a financial modelling of the relation between corporate governance and performance in the case of leveraged buyout firms in France.This thesis is a contribution to the Leverage Buyout and Private Equity literature from a theoretical and empirical point of view. It also has implications for the managers of private firms.

La gestion de la distribution de l’énergie électrique dans un système multi-source (véhicule hybride électrique) est primordiale. Elle permet d’augmenter les performances du système en minimisant la consommation de combustible utilisée par la source principale, tout en respectant la demande et les différentes contraintes de fonctionnement de la chaîne énergétique et de sécurité du système. Dans cette thèse, dans le cas où le profil de mission est connu, une approche combinatoire est proposée en modélisant le problème de gestion d’énergie sous la forme d’un problème d’optimisation avec satisfaction des contraintes. Celui-ci est résolu par une méthode exacte issue de la recherche opérationnelle, conduisant à des solutions optimales en des temps de calcul fortement réduits en comparaison avec ceux obtenus par l’application de la programmation dynamique ou la commande optimale. Pour éprouver la sensibilité aux perturbations, une étude de robustesse est menée sur la base de l’analyse de la solution de pire-cas d’un scénario sur des profils de mission d’un véhicule. Les cas pratiques d’utilisation imposent de ne connaître la demande du moteur électrique qu’à l’instant présent, selon le mode de conduite du chauffeur. Afin de gérer l’énergie du véhicule en temps réel, un algorithme en ligne, basé sur une approche de type floue, est développé. Pour mesurer la qualité de la solution floue obtenue, une étude de performance est réalisée (recherche de l’optimum global), en ayant recours à une optimisation hors-ligne sur des profils de mission de référence, basée sur une modélisation non linéaire du problème de gestion d’énergie. Les résultats obtenus ont permis de valider la qualité de la solution floue résultante. / Managing the distribution of electrical energy in a multi-source system (hybrid electric vehicle) is paramount. It increases the system performance by minimizing the fuel used by the primary source, while respecting demand, the differents operating constraints of the energy chain and system security. In this thesis, where the mission profile is known, a combinatorial approach is proposed by modeling the problem of energy management as an optimization problem with constraint satisfaction. The problem is solved using an exact method from operations research, leading to optimal solutions with reduced computation time in comparison with those obtained by applying dynamic programming or optimal control strategies. To test the perturbation sensitivity, robustness study is conducted, based on the analysis of the worst-case solution of the worst scenario, which can be achieved on the vehicle mission profile. In practical cases, the vehicle demand is unknown, and we have only the information about the instantaneous demand, which depends on driving style of the driver. In order to manage on line the energy of the vehicle, an on-line algorithm, based on a fuzzy approach is developed. To measure the quality of the fuzzy solution obtained, a performance study is carried out (finding the optimum solution), using an off-line optimization under reference mission profiles, based on non-linear modeling of the power management problem. The results were used to validate the quality of the resulting fuzzy solution.

Le mémoire présente le problème de la planification tactique des “blocks” pour le transport ferroviaire intermodal, qui a été peu étudié jusqu’à présent. Nous proposons un nouveau modèle de design de réseau en tenant compte de la spécificité du transport intermodal. La recherche se concentre sur le contexte nord-américain et fait suite à une étroite collaboration avec l’une des principales compagnies ferroviaires nord-américaines. Le “blocking” constitue une importante opération de transport ferroviaire de marchandises, par laquelle des wagons d’origines et de destinations potentiellement différentes sont regroupés pour être d´eplacés et manipulés comme une seule unité, ce qui permet des économies d’échelle. La littérature se limite aux travaux traitant le problème classique du blocage des trains, où la demande est exprimée en termes de wagons. A notre connaissance, aucun travail préalable n’a été consacrè à un contexte de transport intermodal, où la demande est exprimée en termes de conteneurs à dèplacer d’un terminal d’origine donné vers un terminal de destination donné, introduisant ainsi un processus de consolidation supplémentaire. Nous proposons un modèle de “blocking” qui prend en compte plusieurs types de conteneurs et wagons, intégrant l’affectation conteneur-wagon. Nous présentons un nouveau modèle de design de réseau à trois couches en temps continu formulé sous la forme d’un programme linéaire mixte en nombres entiers (MILP), dans le but de minimiser le coût total de transport composé par la sélection de blocs, les coûts d’exploitation et la gestion du coût de la demande. Le modèle peut être résolu en utilisant un solveur commercial pour des tailles réalistes. Nous illustrons les performances et l’intérêt de la méthode proposée à travers une étude de cas approfondie d’un important chemin de fer nord-américain. / The thesis presents the tactical block-planning problem for intermodal railroads, which has been little studied so far. We propose a new block service network design model considering the specificity of intermodal rail. The research focuses on the North American context and follows a close collaboration with one of the major North American railroad companies. Blocking constitutes an important rail freight transport operation, by which cars with potentially different origins and destinations are grouped to be moved and handled as a single unit, yielding economies of scale. The literature is limited to works addressing the classical train blocking problem, where demand is given in terms of cars to be blocked among specific OD pairs. To the best of our knowledge, no prior work has been dedicated to an intermodal transportation context, where demand is expressed in terms of containers to be moved from a given origin terminal to a given destination terminal, hence introducing an additional consolidation process. We propose a blocking model that considers several types of containers and railcars, integrating the container-to-car assignment. We present a new continuous-time, three-layer service network design model formulated as a Mixed Integer Linear Program (MILP), with the objective of minimizing the total transportation cost composed by block selection, operation costs, and handling demand cost. The model can be solved using commercial solver for realistic sizes. We illustrate the performance and interest of the proposed method through an extensive case study of a major North American railroad.

Cette thèse étudie le problème du routage des locomotives qui se pose à la Compagnie des chemins de fer nationaux du Canada (CN) - le plus grand chemin de fer au Canada en termes de revenus et de taille physique de son réseau ferroviaire. Le problème vise à déterminer la séquence des activités de chaque locomotive sur un horizon de planification donné. Dans ce contexte, il faut prendre des décisions liées à l'affectation de locomotives aux trains planifiés en tenant compte des besoins d'entretien des locomotives. D’autres décisions traitant l'envoi de locomotives aux gares par mouvements à vide, les déplacements légers (sans tirer des wagons) et la location de locomotives tierces doivent également être prises en compte. Sur la base d'une formulation de programmation en nombres entiers et d'un réseau espace-temps présentés dans la littérature, nous introduisons une approche par horizon roulant pour trouver des solutions sous-optimales de ce problème dans un temps de calcul acceptable. Une formulation mathématique et un réseau espace-temps issus de la littérature sont adaptés à notre problème. Nous introduisons un nouveau type d'arcs pour le réseau et de nouvelles contraintes pour le modèle pour faire face aux problèmes qui se posent lors de la division de l'horizon de planification en plus petits morceaux. Les expériences numériques sur des instances réelles montrent les avantages et les inconvénients de notre algorithme par rapport à une approche exacte. / This thesis addresses the locomotive routing problem arising at the Canadian National Railway Company (CN) - the largest railway in Canada in terms of both revenue and the physical size of its rail network. The problem aims to determine the sequence of activities for each locomotive over the planning horizon. Besides assigning locomotives to scheduled trains and considering scheduled locomotive maintenance requirements, the problem also includes other decisions, such as sending locomotives to stations by deadheading, light traveling, and leasing of third-party locomotives. Based on an Integer Programming formulation and a Time-Expanded Network presented in the literature, we introduce a Rolling Horizon Approach (RHA) as a method to find near-optimal solutions of this problem in acceptable computing time. We adapt a mathematical formulation and a space-time network from the literature. We introduce a new type of arcs for the network and new constraints for the model to cope with issues arising when dividing the planning horizon into smaller ones. Computational experiments on real-life instances show the pros and cons of our algorithm when compared to an exact solution approach.

Ce manuscrit aborde des problèmes d’ordonnancement et de transport avec une modélisation explicite du transport. De tels problèmes se modélisent communément sous forme de graphes qui sont évalués afin d’obtenir les dates de début des opérations.Les évaluations classiques des graphes sont effectuées au moyen d’algorithmes de plus long chemin permettant d’obtenir une solution semi-active, où toutes les dates des opérations sont au plus tôt. Néanmoins, ces évaluations permettent généralement de ne prendre en compte que des critères de temps ou de distance à minimiser. Les travaux présentés dans ce manuscrit proposent de tenir compte de critères de qualité de service dans la fonction objectif. Cette prise en considération nécessite de nouvelles fonctions d’évaluation du graphe afin d’obtenir des solutions non nécessairement semi-actives permettant de maximiser la qualité de service. En effet, une solution semi-active propose rarement une qualité de service optimale. Les critères de qualité de service adoptés portent sur les ordonnancements et sur le transport.Trois problèmes intégrés sont successivement traités. Le premier problème est un problème de Job-shop avec transport et qualité de service, appelé Job-shop Scheduling Problem with Routing (JSPR). Des pièces, définies par une succession d’opérations, sont à fabriquer sur différentes machines, et entre deux opérations, la pièce doit être transportée de machine en machine. Le critère de qualité de service dans ce problème est dépendant des délais entre, d’une part les différentes opérations sur les machines, et d’autre part entre les différentes opérations de transport. Les gammes opératoires et les opérations de transport sont dépendantes les unes des autres.Le second problème est un problème de Workforce Scheduling and Routing Problem (WSRP), assimilable à un problème de planification de visites à domicile par un ensemble d’employés, et où le transport est pris en compte. Pour ce problème, le critère de qualité de service dépend des dates de début des visites. Les tournées sont indépendantes les unes des autres.Le troisième problème est le Generalised Workforce Scheduling and Routing Problem (GWSRP), qui prend en compte des contraintes de coordination entre les employés. Les tournées de ces derniers sont dépendantes les unes des autres. Elles nécessitent d’être toutes considérées simultanément pour évaluer les dates des visites respectant les contraintes de coordination et maximisant la qualité de service.Pour chaque problème, une nouvelle fonction d’évaluation est proposée. Pour le JSPR, cette fonction est basée sur l’algorithme de (Cordeau and Laporte, 2003) qui est initialement prévu pour le Dial-A-Ride Problem, ainsi que sur l’insertion de time-lags dans le graphe disjonctif du JSPR. Cette évaluation est incluse dans une métaheuristique. Pour le WSRP, la fonction d’évaluation est basée sur un algorithme de calcul du plus court chemin avec un algorithme de type programmation dynamique à labels. Elle est généralisée pour être utilisée dans une génération de colonnes. Et enfin, pour le GWSRP, l’évaluation est effectuée par un modèle PPC qui combiné à une génération de colonnes définissent tous deux un schéma d’optimisation global. / This manuscript addresses scheduling and transport problems where the transport is explicitly taken into account. Such problems are commonly modelled by graphs that are evaluated to obtain the starting times of operations.Classic graph evaluations are performed using longer path algorithms to obtain a semi-active solution, where all operations are left shifted. Nevertheless, these evaluations generally allow only time or distance criteria to be taken into account. The work presented in this thesis propose to take the quality of service criteria into account in the objective function. These considerations require new graph evaluation functions in order to obtain non-semi-active solutions that maximise the quality of service. Indeed, a semi-active solution rarely offers maximum quality of service. Three integrated problems are successively addressed. The first problem is a Job-shop Scheduling Problem with transport and quality of service, referred to as Job-shop Scheduling Problem with Routing (JSPR). Jobs, defined by a succession of operations, are to be performed on different machines, and between two operations, the job must be transported from a machine to another machine. The quality of service criterion in this problem depends on the delay between, on the one hand, the different operations belonging to the same job, and on the other hand, between the different transport operations. Machine-operations and transport-operations are dependent.The second problem is a Workforce Scheduling and Routing Problem (WSRP), which is similar to a problem of planning home services by a set of employees, and where transport is taken into account. For this problem, the quality of service criterion depends on the starting times of the visits. The trips of employees are independent.The third problem is the Generalised Workforce Scheduling and Routing Problem (GWSRP), which takes coordination constraints between employees into account. The trips are dependent on each other. The evaluation function of the starting times must consider simultaneously all trips in order to respect all coordination constraints and to maximise the service quality.For each problem, a new evaluation function is proposed. For the JSPR, this function is based on the algorithm of (Cordeau and Laporte, 2003) which is introduced first for the Dial-A-Ride Problem. The evaluation function, for the JSPR, is based on the insertion of time-lags in the disjunctive graph. This evaluation is included in a metaheuristic. For the WSRP, the evaluation function is based on the dynamic labelling algorithm used for an Elementary Shortest Path Problem With Resource Constraints. This function is generalised in order to be included in a column generation scheme. Finally, for the GWSRP, the evaluation is performed by a PPC model combined with a generation of columns and both define an overall optimisation scheme.