Le thème de ce mémoire est l'ordonnancement dans les ateliers de production. L'objectif est d'étudier différents modèles classiques en analysant les liens et différences entre ces modèles et les problèmes pratiques associés. Les méthodes utilisées sont l'analyse de problèmes de nos partenaires industriels, l'étude de la complexité des problèmes ou de la structure des solutions et la proposition de méthodes de résolution exactes ou approchées. Le premier axe de cette thèse est l'étude de problèmes d'ordonnancement avec contraintes de ressources d'entrée/sortie. Les environnements considérés sont les flowshops robotisés et le nouveau modèle d'indisponibilité des opérateurs. Le second axe abordé concerne l'ordonnancement avec high multiplicity où les pièces sont agrégées en catégories. La description complète d'un ordonnancement (c'est-à-dire les instants de fabrication des tâches) n'est que pseudo-polynomiale de la taille de l'instance.

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques. / Integer linear programming is a robust and efficient approach to solve large-scale instances of combinatorial problems. However, problems constantly gain in complexity and sometimes impose strong constraints on computation times. We must then develop specialised methods to compute heuristic primal solutions to the problem and derive lower bounds on the optimal value, and thus prove the quality of our primal solutions. We propose to guide a reformulation approach for mixed integer programs with Lagrangian relaxations. After the identification of a strong relaxation, a mechanical process leads to a second integer formulation. This reformulation is equivalent to the initial one, but its linear relaxation is equivalent to the strong Lagrangian dual. We will show that the reformulation approach unifies and generalises prior formulations and lower bounding approaches, and that it exposes a simple mechanism to reduce the size of reformulations in return for weaker bounds. Nevertheless, our reformulations are large. We address this issue by solving their linear relaxations with specialised methods. Finally, we apply the reformulation approach to two location problems. This yields novel formulations for both problems; some are very large but, thanks to the aforementioned specialised methods, still practical.

Pour garantir la pérennité de l'entreprise, celle-ci doit souvent chercher des contrats à l'export. Dans le domaine de la Défense, ces contrats s'accompagnent souvent de transferts de technologie (ToT) vers le pays acquéreur. Ceux-ci sont partiels et un compromis est nécessaire entre la protection de la propriété industrielle, celle du secret national et les demandes du client. C'est dans ce contexte, et notamment au sein de DCNS que nous cherchons de nouvelles techniques de protection logicielles. Face aux échecs des différentes techniques de protections actuelles (obfuscations et packer) qui ne proposent que de ralentir la compréhension des données, une nouvelle approche de protection est envisagée. L'idée principale est de filtrer les accès mémoires des données identifiées comme sensibles. Cette solution, qui s'inscrit dans un environnement industriel défini (architecture Intel et système d'exploitation Linux), doit impacter au minimum le système et les applications fournis par DCNS. Nous proposons une architecture qui s'appuie sur les dernières technologies Intel et particulièrement sur la virtualisation matérielle. Celle-ci nous permet d'obtenir un haut niveau de privilège et de contrôler finement les applications. Notre solution permet de protéger les données exécutables des binaires de type ELF, dans les architectures 32 et 64 bits, sans modification du système cible. Nous détaillons les différentes étapes pour protéger l'exécution d'un processus (du chargement à son arrêt) ainsi que les problèmes rencontrés et les choix pour y remédier. Nous montrons également, à travers différentes mesures, l'efficacité d'une telle architecture et son faible impact sur les performances globales. Dans notre implémentation, seules les données exécutables sont protégées, nous proposons donc des pistes d'améliorations pour couvrir la totalité du binaire en mémoire. Et nous étudions les évolutions possibles pour intégrer notre protection dans une architecture de confiance et ainsi, renforcer sa persistance face aux attaques. Notre solution permet donc par construction d'interdire toutes les lectures et écritures des données exécutables sensibles et s'adapte à tous les systèmes d'exploitation Linux sans aucune modification du système.

A cause de leur aspect strat égique et des divers challenges qu'ils repr ésentent en termes de mod élisation et de r ésolution, les probl èmes de localisation et de conception de r éseaux ont été largement étudi es par les sp écialistes en recherche opérationnelle. Par ailleurs, bien que les études de cas dans ce domaine soient rares dans la litt érature, plusieurs travaux r écents ont int égr é certains aspects op érationnels afi n de rendre ces probl èmes d'optimisation plus r éalistes. L'objet de notre projet de recherche est le d éveloppement d'un mod èle de conception d'un r éseau de distribution prenant en compte plusieurs aspects op érationnels inspir és d'une étude de cas dans le domaine de l'automobile. Bien que nos choix de mod élisation soient motiv és par cette étude de cas, ils restent applicables dans d'autres secteurs industriels. Le r éseau de distribution consid ér é se compose de trois niveaux : les usines au premier niveau, les centres de distribution (CD) au deuxi ème niveau et les clients au dernier niveau. Nous supposons que le nombre et la localisation des usines ainsi que le nombre et la localisation des clients sont connus. Etant donn é la demande des clients et une liste de CD potentiels, l'objectif est de d éterminer la localisation des CD a ouvrir et d'y a ffecter les clients de mani ère a minimiser le coût total. Nos contributions par rapport aux travaux existants concernent la mod élisation et la r ésolution du probl ème ainsi que les tests num ériques eff ectu és. En termes de mod élisation, nous consid érons divers aspects op érationnels qui ont été pris en compte s épar ément dans la litt érature mais jamais combin és dans un même mod èle. Plus particuli èrement, nous introduisons un "clustering" en pr étraitement afi n de mod éliser les tourn ées de camions. Nous int égrons également des contraintes de volume minimum sur les axes de transport pour assurer l'utilisation de camions pleins, des contraintes de volume minimum et de capacit é maximale sur les centres de distribution, des contraintes de distance de couverture maximale et des contraintes d'uni-aff ectation. Par ailleurs, nous étudions une extension multi-p ériodes du probl ème en utilisant un "clustering" dynamique pour mod éliser des tourn ées de camions multi-p ériodes. En termes de r ésolution, comme le probl ème étudi é est NP-di ffcile au sens fort, nous proposons di fférentes m éthodes heuristiques performantes bas ées sur la relaxation lin éaire. A travers les tests eff ectu és, nous montrons que ces m éthodes fournissent des solutions proches de l'optimale en moins de temps de calcul que l'application directe d'un solveur lin éaire. Nous analysons également la structure des r éseaux de distribution obtenus et nous comparons les r ésultats issus de plusieurs versions du mod èle afi n de montrer la valeur ajout ée du "clustering" ainsi que de l'approche multi-p ériodes.

L'Indonésie, l’une de plus grands archipels, a été menacé avec la pollution provenant de la marée noire. Le gouvernement d’Indonésie en coopération avec le gouvernement Français a développé un système d'observation de l'océan par satellite afin de supporter de développement durable. Ce système est intégré dans les systèmes d'océanographie opérationnelle dans le cadre du projet de développement des infrastructures de l'océanographie spatiale (INDESO). Le contexte de cette thèse est dans le cadre du projet INDESO notamment dans applications d’INDESO pour suivre des déversements de pétrole dans les mers d’Indonésie. Dans ce contexte,cette thèse propose de nouvelles méthodologies et analyses. Cette thèse comportait deux contributions principales. La première contribution est sur la récupération des paramètres de dérive des déversements d'hydrocarbures à partir d'une analyse conjointe des observations SAR (Synthetic Aperture Radar) et des résultats d'un modèle de transport de déversement de pétrole. Dans cette première partie, nous estimons les paramètres de dérive de pétrole. On a exploité un modèle de transport de déversement de pétrole lagrangien,de sorte que la dérive simulée de déversement d'hydrocarbures modèles puisse correspondre à l'observation de satellite. Pour confirmer l'origine du déversement de pétrole détecté à une date donnée par une observation de SAR, nous avons effectué des simulations avec différentes dates de début de fuite, duré de fuite et différentes valeurs de pondération deux facteurs dominants i.e. vent et courant. Nous avons développé une nouvelle méthode pour l'assimilation de ces paramètres de fuite de pétrole à comparer avec d'une détection dérivée d'un déversement d'hydrocarbures. Nous avons appliqué la méthodologie proposée sur le plus grand accident en Indonésie, l'accident de Montara. La deuxième contribution est l'évaluation globale du risque de déversement d'hydrocarbures en Indonésie. Nous sommes concentrés sur la zone de gestion des pêches de l'Indonésie. Dans cette analyse, nous avons proposé une méthodologie qui considère le déversement de pétrole, qui a des sources différentes et leurs impacts à l'environnement, mais aussi sur les perspectives sociales et économiques. Pour l'évaluation de la vulnérabilité des zones marines protégées, nous avons également exploité le modèle de 2D lagrangien. L'accent mis sur les zones de gestion des pêches (FMA) afin de fournir une analyse synoptique sur l'ensemble du territoire maritime d’Indonésie. Chaque FMA présente les caractéristiques spécifiques des paramètres environnementaux etsocio-économiques. Nous avons évalué le risque de déversement d'hydrocarbures dans chaque zone de gestion sur la base de tous ces facteurs. Le résultat de cette étude peut être utilisé dans la planification d'une action pour réduire les impacts négatifs du déversement d'hydrocarbures. / Indonesia as the biggest archipelago has a major threat coming from oil spill. Due to the increasing concerns of environment protection for sustainable development, the government of Indonesia in cooperation with government of France developed an ocean observation system with one of its pilot applications is oil spills monitoring. This system is integrated in the operational oceanography systems within the project of Infrastructure Development of Space Oceanography (INDESO). The context of this thesis is in the frame of INDESO project particularly in the monitoring of oil spill in the Indonesian seas. Within the context above, this thesis propose new methodologies and analyses. This thesis involved two main contributions. The first contribution addressed the retrieval of oil spill drift parameters from a joint analysis of SAR observations of an oil spill and of outputs of a Lagrangian oil spill transport model. In this first part, we estimate oil spill drift parameters. The proposed framework exploited a Lagrangian oil spill transport model such that the simulated oil spill drift could match a SAR-based observation of an oil spill. In the considered 2D Lagrangian model there were two dominant factors, i.e. wind and surface current. To confirm the origin of the oil spill detected on a given date through a SAR observation, we performed simulations with various leakage starting dates, leakage durations, and different values of wind and current weighing coefficients. We developed a novel framework for the assimilation of these oil leakage parameters from a SAR-derived detection of an oil spill. We applied the proposed methodology on the most famous oil spill accident in Indonesia, the Montara case. The second contribution was the global assessment of oil spill risk inIndonesia. We focused on the 11 Indonesia Fisheries Management Area to support the sustainability development of marine and fisheries. In this analysis we proposed methodology that considered the oil spillfrom different source and their impacts not only to the environment, but also from social and economic perspectives. For the assessment of vulnerability of Marine Protected Areas to oil spill pollution, we also exploited the oil spill trajectory model. The focus was given to Fisheries Management Areas as a means to provide synoptic analysis over theentire Indonesian maritime territory. Using different information from many institutional reports, we collected and analyzed the potential source of oil spill in each FMA. Each FMA has specific characteristics in terms environmental and socioeconomic features. We assessed the oil spill risk in each FMA based on all these factors. The result of this study can be used in the mitigation planning to reduce the negative impacts of oil spill.

Alors que la pression, dans le contexte actuel de concurrence mondialisée, s'accumule sur les managers logistiques afin d'opérationnaliser les stratégies développées par leur hiérarchie, les pratiques logistiques sont de plus en plus diverses et sophistiquées; le choix de telle ou telle pratique pour telle ou telle stratégie devient de moins en moins évident. Si tel que le stipule la théorie de la contingence, les pratiques ne sont pas équivalentes quel que soit le contexte stratégique, quel modèle de performance opérationnelle peut-on proposer? C'est ainsi que nous suggérons dans cette étude la construction d'un modèle taxonomique comprenant stratégies commerciales et concurrentielles des entreprises, pratiques supply chain et performance opérationnelle à partir d'une étude empirique menée au Maroc auprès de 119 entreprises manufacturières. Les résultats de notre investigation confirment l'émergence de cinq profils supply chain d'entreprises issus de la revue de littérature : « Stratégies multiples », « Innovation », « low cost », « Qualité » et « Résiduel ». L'approche configurationnelle nous montre ici que l'alignement de la stratégie commerciale, la stratégie concurrentielle, et la pratique supply chain aboutit à une meilleure performance opérationnelle, par contraste avec les entreprises non alignées du groupe « résiduel ». / Pressure, in today's context of globalized competition, is accumulating on the shoulders of logistics managers so they execute the strategies developed by their hierarchy. However, logistics practices are more and more diverse and sophisticated, and the choice of the right practice for the right strategy is less and less obvious. If, as stated by Contingency Theory, practices are not equivalent in any given strategic context, which operational performance model can be suggested? Hence, we develop a taxonomic model comprising generic strategies, competitive priorities, supply chain practices and operational performance based on the empirical study of 119 manufacturing Moroccan companies. Our investigation confirms the emergence of five supply chain profiles which resulted from our literature review: “Multiple strategies”, “Innovation”, “Low Cost”, “Quality” and “Residual” profiles. The configuration approach indicates here that the alignment of generics strategies with the competitive priorities and the supply chain practices lead to better operational performance, in contrast with the unaligned companies of the residual group.

La recherche est développée en connexion avec l'évolution de la qualité et de l'efficience de la logistique inversée des déchets urbains. Après avoir observé comment la logistique inversée est exécutée au Brésil, plus spécifiquement dans deux villes brésiliennes (Fortaleza, l'Etat du Ceará et Osasco, l'Etat de São Paulo), nous avons suggéré une optimisation d'un point de vue quantitative et qualitative. Autrement dit, l'introduction d'un procédure d'optimisation dans les modelés courants de l'administration traditionnelle de la logistique inversée. En réalité, le management public peut apporter performance et efficience s'il utilise des outils mathématiques, computationnelles et managériales appropriées. Le modèle mathématique, formulé dans la thèse, est capable d'analyser et optimiser quantitativement l'emplacement d' installations pour la logistique inverse et d'indiquer quelle est la meilleure localisation pour que le management public puisse acquérir plus de performance et d'efficience dans sa gestion des déchets urbains. Pour optimiser les solutions, dans le contexte de la gestion des déchets urbains, nous utilisons la technique de programmation liner.Un programme computationnelle a été développé pour cette recherche pour faire des simulations. L'efficience et la versatilité de ce programme ont été utilisées pour faire l'analyse de deux exemples au Brésil en déterminant la localisation optimisée des installations à Fortaleza et à Osasco. Finalement, tandis que la recherche opérationnelle est la base de la construction de ce modèle mathématique, le modèle de partenariat public-privé est l'indication du type idéal de management pour la gestion des déchets urbains. / The research is developed in connection with the evolution in quality and efficiency of reverse logistics of urban solid waste. Therefore, after observing how reverse logistics is currently being executed in two Brazilian cities (Fortaleza, State of Ceará and Osasco, State of São Paulo), quantitative and qualitative management optimization procedures are suggested. In other words, such optimization procedures suggest that traditional management models currently used in public administration can enhance performance and efficiency if appropriate mathematical, computational and managerial tools are used.A mathematical model was formulated capable to accomplish an optimized quantitative analysis for the location of facilities within the ambit of reverse logistics and, then, it was indicated which is the best type of public management so that the proposed model is used with high performance and efficiency. To optimize solutions in the context of urban solid waste management, linear programming techniques are used.A computer program developed for this research was used to perform the simulations. The efficiency and versatility of the computer program were evaluated through the analysis of several examples for determining the optimized location of facilities in Fortaleza and in Osasco.Operational research is the basis for the construction of the mathematical model while the public-private partnership management model is the indication of the type of appropriate management so that the aforementioned mathematical and computational tool may present optimized solutions in the proposed reverse logistics urban solid waste management model.

Cette thèse porte sur le développement de modèles mathématiques et d’algorithmes d’optimisation pour la conception de chaînes logistiques durables. Nous proposons des modèles mono-périodiques, multi-produits et multi-modes de transport à quatre niveaux (fournisseurs, unités de production, entrepôts et clients) couvrant les piliers économique et environnemental du développement durable. Les variables de décision concernent la localisation des sites logistiques intermédiaires (unités de production et entrepôts), les choix de technologie et de mode de transport, et la détermination des flux de produits. Un premier modèle est basé uniquement sur la minimisation des coûts totaux. Ce modèle est étendu au cas bi-objectif en considérant la minimisation des émissions de CO2. Nous proposons une procédure d’optimisation basée sur la recherche à voisinage large (LNS : Large Neighborhood Search). L’application de cette méthode à un problème à variables mixtes tel que la conception de chaîne logistique est inédite. Notre extension au cas bi-objectif fait intervenir l’algorithme récent de recherche locale multi-directionnelle. Les expérimentations numériques permettent d’évaluer la pertinence de nos modèles et de comparer les performances de nos algorithmes à celles d’un solveur du marché. / This thesis focuses on the development of mathematical models and optimization algorithms for the design of sustainable supply chains. We propose single-period, multi-commodity, multi-mode, four level models (suppliers, production facilities, warehouses and customers) covering economic and environmental pillars of sustainable development. The decision variables are related to the location of the intermediate logistics sites (production units and warehouses), the choice of technology and mode of transport, and the determination of product flow. A first model is based solely on minimizing total costs. This model is extended to bi-objective minimization by considering CO2 emissions. We propose an optimization procedure based on the Large Neighborhood Search (LNS) metaheuristic, which had almost never been applied to problems with mixed variables such as design supply chain. Our extension to the bi-objective case involves the use of the multi-directional local search (MDLS). Extensive numerical experiments assess the relevance of our model and compare the performance of our algorithms to those of a state-of-the-art solver.

Cette thèse aborde le problème de tournées de véhicules périodiques (PVRP) lorsqu'il est appliqué au transport de marchandises convoitables. Des contraintes spécifiques relatives à la sécurité du convoi doivent être définies.Le problème de tournées de véhicules périodiques avec dispersion des instants de service (PVRPTS) est alors décrit puis modélisé mathématiquement. Le but est de servir un ensemble de clients sur plusieurs jours en respectant un degré de variation définit dans les heures de service. Le modèle obtenu est discuté et deux heuristiques constructives sont proposées et évaluées pour sa résolution.Une recherche locale itérée avec redémarrages (MS-ILS) est proposée pour ce problème. Les résultats obtenus montrent que cette méthode surpasse les deux précédentes sur toutes les instances de test. Elle est ensuite évaluée sur un problème plus classique de la littérature : le problème de tournées de véhicules avec fenêtres horaires souples (VRPSTW) et s'avère très compétitive, produisant de nouvelles meilleures solutions.La MS-ILS est ensuite transposée au problème de tournées de véhicules régulières (ConVRP). Contrairement au PVRPTS, il s'agit dans le ConVRP de servir régulièrement des clients aux demandes intermittentes. La méthode montre une flexibilité remarquable et produit de bons résultats.Pour finir, les développements effectués chez Nexxtep Technologies sont présentés. Ils comprennent la conception d'un logiciel commercial pour l'optimisation de tournées de véhicules et l'implémentation des méthodes développées / This thesis is dedicated to the periodic vehicle routing problem when applied to the transportation of valuable goods. Specifics constraints have to be defined to ensure the security of the convoy.The periodic vehicle routing problems with time spread constraints on services (PVRPTS) is defined and a mathematical model is given. The goal is to serve a set of customers over several days such that their visit times differ by a minimum amount. The depicted model is discussed and two constructive heuristics are designed and assessed.A Multi-start iterated local search (MS-ILS) is proposed to solve this problem. The results shows that the method outperform the two previous heuristics. For the sake of comparison with previous approaches, the MS-ILS is evaluated on a more classical problem : the vehicle routing problem with soft time windows (VRPSTW). The method proves to be very competitive, producing new best known solutions.The MS-ILS is then adapted to solve the consistent vehicle routing problem (ConVRP). Unlike the PVRPTS, the goal of the ConVRP is to deliver customers with intermittent demands with regularity in terms of service times and drivers. The method demonstrate his flexibility and produce good results. Finally, the developments performed at Nexxtep Technologies are depicted. They encompass commercial-software design and implementation of the proposed methods

Cette thèse porte sur l'étude du problème de tournées de véhicules compartimentés (Multi-Compartment Vehicle Routing Problem ou MC-VRP) dans le contexte de l'industrie de la nutrition animale. Les travaux de recherche et d'application sont concentrés sur la distribution dans le domaine agroalimentaire.En dépit d'une large application industrielle, les problèmes de MC-VRP ont été peu étudiés dans la littérature scientifique. Trois variantes du MC-VRP sont traitées dans cette thèse. D'une part, nous proposons les algorithmes "Greedy Randomized Adaptive Search Procedure" (GRASP) et "Iterated Local Search procedure" (ILS) pour résoudre le MC-VRP avec un compartiment de taille fixe dédié à chaque produit. Une extension de ce problème à des compartiments de tailles variables (Flexible Compartments Vehicle Routing Problem ou FC-VRP) est également résolue. D'autre part, nous proposons un GRASP et un Multi Start ILS pour la résolution du MC-VRP avec décisions d'affectation de chaque compartiment à un client et un produit.En dernier lieu, des travaux d'application industrielle sont présentés. Des tests d'évaluation de performances ont été réalisés dans un contexte de distribution d'aliments au bétail chez la société Nestal. Des outils d'aide à la décision ont été développés et mis en place dans cette société / This research concerns solving the Multi-Compartment Vehicle Routing Problem (MC-VRP) in the context of animal nutrition industry. Research and application work focuses on distribution in food industry.Despite its vast application in industry, little attention has been paid to the MC-VRP. We address three classes of MC-VRP in this research. Firstly, we propose two metaheuristics, "Greedy Randomized Adaptive Search Procedure" (GRASP) and "Iterated Local Search procedure" (ILS), in order to solve a MC-VRP with a fixed-sized compartment dedicated to each product. Also, an extension of this problem to variable-sized compartments which we call Flexible Compartments Vehicle Routing Problem (FC-VRP) is studied. Further, we propose a GRASP and a Multi Start ILS to solve a MC-VRP problem with assignment decisions of each compartment to one client and one product. Finally, some application work is presented. Experiments intended to measure performance in the context of food distribution to cattle were conducted for Nestal company. Decision support tools had been developed and implemented for this company