Dans cette thèse, nous traitons des problèmes d'intégration des décisions prises aux niveaux planification (tactique) et ordonnancement (opérationnel). Que ce soit en théorie ou en pratique, ces deux niveaux sont habituellement traités indépendamment l'un de l'autre. Ainsi, les objectifs de production à réaliser sont souvent incohérents avec la capacité réelle de l'atelier. Cette thèse propose des méthodes de résolution pour des problèmes intégrés de planification et d'ordonnancement. Nous développons un nouveau modèle mathématique qui prend en compte de manière originale les contraintes de séquencement des opérations sur les machines, garantissant ainsi la faisabilité du plan de production. Ce modèle est résolu à l'aide d'une heuristique Lagrangienne pour une séquence des opérations axée. Notre approche est originale à double titre : dans la mise à jour des multiplicateurs Lagrangiens (puisque il existe un nombre exponentiel de contraintes de capacité dans notre modèle), et par la proposition d'une nouvelle procédure de lissage pour la construction d'une solution réalisable. Nous développons ensuite deux approches, basées sur le recuit simulé et la recherche taboue, qui permettent d'améliorer la séquence des opérations sur les ressources et ainsi de chercher un plan de production optimal associé à une séquence réalisable. De nombreux résultats expérimentaux ont été effectués et valident l'efficacité de nos approches.

L’objectif de cette thèse est de proposer un outil pour la planification de la production d’un fournisseur et d’étudier les moyens d’améliorer la coordination entre ce fournisseur et les usines clientes. Appliquée à l’industrie automobile, cette thèse se base sur le cas des usines de mécanique (usines de moteurs, de boîtes de vitesse, et de pièces de liaison au sol) qui fournissent les usines d’assemblage de véhicules.En analysant la demande des usines clientes, nous mettons en évidence les facteurs de variabilité de cette demande et proposons des pistes pour améliorer la coordination avec le fournisseur à travers un partage de l’information plus efficace. Pour la planification de la production du fournisseur, nous proposons un modèle mathématique sous forme de programme linéaire en nombres entiers. Ce modèle permet de définir un plan de production détaillé en respectant les contraintes existantes et en visant quatre objectifs : satisfaire la demande prévisionnelle, atteindre les stocks de sécurité, équilibrer les stocks entre les produits, et lisser la production. L’intérêt apporté par ce modèle est démontré par des tests réalisés sur des données réelles. Sachant que le modèle proposé est destiné à être utilisé dans le cadre d’une planification à horizon glissant, nous analysons par simulation l’influence de deux paramètres : la fréquence de planification et la longueur de l’horizon gelé. Nous donnons des préconisations sur le choix de ces paramètres de manière à assurer un bon compromis entre le taux de service, le niveau de stock, et la stabilité de la planification. Enfin, pour améliorer la coordination entre les usine clientes et le fournisseur, nous étudions deux pistes en particulier : l’amélioration de la fiabilité des prévisions communiquées au fournisseur et l’allongement du délai qui lui est accordé pour satisfaire la demande. L’intérêt de mettre en œuvre ces propositions est évalué par simulation. / The objective of this thesis is to provide a production planning tool for a supplier and to explore ways to improve the coordination between this supplier and customer plants. Based on a case study in the automotive industry, this thesis considers the case of powertrain plants (units producing engines, gearboxes, and chassis parts) that supply the car assembly plants.By analyzing the customer plant demand, we highlight the variability causes of this demand and we propose ways to improve coordination with the supplier through a more efficient information sharing. To plan the production of the supplier, we propose a mathematical model which is a mixed integer linear program. This model provides a detailed production plan respecting existing constraints and targeting four objectives: satisfying the forecasted demand, reaching safety stock levels, balancing stock levels between products, and leveling the production. The value of this model is demonstrated by tests using real data. As this model is intended to be used as part of a rolling horizon planning, we analyze the influence of two parameters: planning frequency and length of the frozen horizon. We give recommendations on the choice of these parameters to ensure a good tradeoff between service level, inventory, and planning stability. Finally, to improve the coordination between the customer plants and the supplier, two ways are in particular investigated: improving the accuracy of the forecasts sent to supplier and lengthening the time allowed to fulfill the demand. The value of implementing these proposals is evaluated by simulation.

Cette étude porte sur la réduction de l’émission de gaz à effet de serre dans une région où le gouvernement cherche à établir des politiques de régulation des industriels locaux. La définition de politiques de régulation pour le gouvernement et la planification de la production pour les industriels sont étudiées à l’aide des méthodes issues de la recherche opérationnelle et de la science de management (OR/MS). Nous considérons deux types de politiques de régulation : la politique de quotas et la politique de droits d’émission échangeables sur le marché. Nous considérons d’abord le problème stratégique d’un industriel soumis à un quota d’émission. Afin de maximiser son profit, nous construisons des modèles de jeux de Stackelberg pour optimiser l’empreinte carbone du produit, le prix de gros et la sélection de détaillants. Le problème est démontré NP-difficile et un algorithme hybride est développé pour le résoudre. Nous étudions ensuite la planification de la production en moyen terme pour minimiser le coût total de production et de stockage, en prenant en compte les contraintes liées à la réduction d’émission à travers une sélection de technologies dont certaines sont vertes. Nous démontrons que ces problèmes peuvent être résolus en temps polynomial. A partir de ces résultats, nous étudions la définition de politiques de réduction d’émission par le gouvernement afin de maximiser le bien-être sociétal de la région. Des modèles de jeux de Stackelberg sont formulés pour optimiser les paramètres de ces politiques, en anticipant les décisions opérationnelles des industriels locaux en réaction à ces politiques. Des algorithmes hybrides sont proposés pour résoudre le problème. Pour chaque problème étudié, nous menons des expériences numériques pour évaluer les algorithmes développés. Les résultats expérimentaux montrent l’efficacité de ces algorithmes. Ils permettent aussi, grâce à des analyses de sensibilité, de tirer des renseignements managériaux intéressants. / This research focuses on carbon emission-reduction issues in an area where the government imposes emission-reduction policies on local manufacturers. Policymaking problems for the government and production planning problems for the manufacturers are investigated with Operations Research/Management Science (OR/MS) approaches. Two types of emission-reduction policies, including emission-cap regulation policy and emission cap-and-trade scheme, are addressed. We first discuss manufacturers’ long-term strategic decision problem under the government-imposed emission-cap regulation policy. With the objective of maximizing the manufacturers’ profits, Stackelberg game model is formulated to optimize their decisions on carbon footprint, wholesale price and retailer selection. The problem is proven to be NP hard and a hybrid algorithm is developed to solve the model. We then investigate manufacturers’ medium-term production planning to minimize the total production and inventory holding cost, by considering emission-reduction constraints through technology selection, some of the technologies being green. The problems are shown to be polynomially solvable. Based on these results, we study the government’s policymaking problems to maximize the social welfare of the area. Stackelberg game models are formulated to optimize the emission-reduction policies by anticipating manufacturers’ operational decisions in response to the governmental policies. Hybrid algorithms are developed to solve the problems. For each studied problem, numerical analyses are conducted to evaluate the algorithms. The computation results show that the algorithms developed in this research are effective. Some interesting and valuable managerial insights are drawn from computational results and sensitivity analyses.

Chargée d'organiser la fabrication, la gestion de la production est une tâche complexe qui tend à jouer un rôle de plus en plus déterminant pour le bon fonctionnement des entreprises. Afin de faciliter l'établissement du plan de production, cette étude s'intéresse à la mise en oeuvre de structures décisionnelles multi-niveaux. Les niveaux décisionnels sont définis à partir d'une agrégation de données, d'une désagrégation des décisions et d'horizon temporels adaptés. A chaque niveau, l'élaboration de la décision est réalisée par affinements successifs avec une dynamique appropriée. Cependant, l'ignorance des interactions entre niveaux conduit souvent à des dysfonctionnements importants dans le processus décisionnel. Pour cette raison, ce travail est centré sur la formalisation et l'analyse des interactions entre niveaux afin d'aboutir à la coordination globale des décisions au sein de la structure. Les concepts génériques de robustesse des décisions agrégées et de cohérence des décisions détaillées sont introduits et caractérisés. La mise en ¿uvre de ces deux concepts est réalisée par l'établissement de conditions analytiques destinées à être introduites sous forme de contraintes au sein des modèles mathématiques de chaque niveau. La détermination de conditions d'existence de solution dans un modèle d'étude traduisant les interactions entre entités détaillées et agrégées, l'exploitation des outils de programmation linéaire et de théorie des graphes permettent de construire de manière systématique les conditions recherchées. Cette méthodologie est mise en oeuvre dans le cadre d'un problème de production multi-produits, muti-étapes, multi-ressources. La structure élémentaire considérée comporte deux niveaux de décision basés sur l'agrégation du temps. Ce type d'agrégation, associé à un processus dynamique de désagrégation, offre des avantages importants au plan de la réactivité comme au plan de l'a utonomie décisionnelle. Les développements d'abord théoriques sont poursuivis par des approches prenant en considération un souci de mise en oeuvre. Dans ce cadre, la notion d'arriérés de fabrication est introduite ainsi que la prise en compte explicite de l'incertitude des données.

L'industrie des semi-conducteurs est caractérisée par une production de forte variabilité et de faible volume, des flux de production ré-entrants ainsi que d'un processus de fabrication complexe. Au sein de ce contexte industriel complexe, a été considéré un problème de planification à capacité finie. C'est le problème de projection des encours de production et des commandes clients à capacité finie. Il s'agit d’estimerles dates de début, les temps d'attente et les dates de fin de chacun des steps des différents lots ainsi que la charge accumulée sur les équipements. Cette projection doit tenir compte des contraintes de capacité et qualifications des équipements et des dates d'échéance de livraison des lots. La contrainte de qualification définit l'éligibilité d'un équipement à traiter un produit. Ainsi, l'objectif de cette étude consiste à établir un plan de production réalisable à moyen terme. Afin de réaliser cet objectif, des méthodes exactes et approchées sont proposées. Des résultats en termes de complexité, et d'algorithmes de résolution, ont permis une application industrielle, dans la mesure où un logiciel de planification de la production à capacité finie a été développé. / In this study, we consider the problem of production planning in the semiconductor industry characterized by high mix low volume production, reentrant flows and complex manufacturing process.The aim of this work is to establish a feasible production schedule that takes into account the limited capacity of the manufacturing system, equipment qualifications constraints and delivery due dates. In this context, we have formulated the objective and constraints in a mixed linear program (MIP). The objective of the MIP is to minimize delivery delays to guarantee on-time delivery. While executing different tests of the MIP, we have reached a limit of resolution in a reasonable time. Thus, we use an approximate method to solve the problem. The results show the effectiveness of the heuristic established as solution quality and time resolution.The obtained results led to an industrial application and a software that provides feasible schedules in reduced execution time in a specific fab.

Dans le secteur électrique et chez EDF, l'optimisation mathématique est utilisée pour modéliser et résoudre des problèmes de gestion de la production d'électricité.Citons quelques applications : la modélisation des problèmes d'équilibre des marchés, la gestion des risques d'épuisement des barrages, la programmation des arrêts de tranches nucléaires.Plus particulièrement l'hydroélectricté est une énergie renouvelable, peu chère, flexible mais limitée.Exploiter l'hydraulique constitue donc un enjeu important.Nous nous intéressons à des problèmes d'optimisation de Programmation Non Linéaire en Nombres Entiers (PNLNE) dont les variables de décision sont continues ou discrètes et dont les fonctions exprimant l'objectif et les contraintes sont linéaires ou non.Les non-linéarités et la combinatoire induite par les variables entières rendent les PNLNE difficiles à résoudre.En effet les méthodes existantes n'arrivent pas toujours à résoudre les grands PNLNE à l'optimalité avec des temps de calcul limités.En amont des performances de résolution, la faisabilité est une question préliminaire à aborder puisqu'il faut s'assurer que les PNLNE à résoudre admettent des solutions.Lorsqu'il y a des infaisabilités dans des modèles complexes, il est très utile mais très difficile de les analyser.Par ailleurs la résolution de PNLNE est plus difficile si l'on requiert une certification de la précision exacte des résultats.En effet les méthodes résolutions sont en général mises en oeuvre en arithmétique flottante, ce qui peut donner lieu à une précision approchée.Nous abordons deux problèmes d'optimisation liés à la planification de la production hydraulique, Hydro Unit-Commitment (HUC) en Anglais.Etant données des ressources d'eau finies dans les barrages l'objet du HUC est de prescrire des programmes de production les plus rentables qui soient compatibles avec les spécifications techniques des usines hydrauliques.Le volume, le débit et la puissance sont représentés par des variables continues tandis que l'activation des turbines est communément formulée avec des variables binaires.Les non-linéarités proviennent en général des fonctions qui expriment la puissance générée en fonction du volume et du débit.Nous distinguons deux problèmes : un PLNE avec des caractéristiques linéaires et discrètes et un PNL avec des caractéristiques non linéaires et continues.Dans le 2ème chapitre, nous traitons de la faisabilité d'un HUC réel en PLNE.Comparé à un HUC standard le modèle inclut deux spécifications supplémentaires : des points de fonctionnements discrets sur la courbe puissance-débit ainsi que des niveaux cibles pour le volume des réservoirs.Les complications liées aux données réelles et au calcul numérique, associées aux spécifications du modèle rendent notre problème difficile à résoudre et souvent infaisable.Nous procédons par étape pour identifier et traiter les sources d'infaisabilité, à savoir les erreurs numériques et les infaisabilités de modélisation, pour rendre le problème faisable.Des résultats numériques étayent l'efficacité de notre méthode sur un ensemble de test de 66 instances réelles qui contient de nombreuses infaisabilités.Le 3ème chapitre porte sur l'adaptation de l'algorithme Multiplicative Weights Update (MWU) à la PNLNE.Cette adaptation est fondée sur une reformulation paramétrée spécifique dénommée pointwise.Nous définissons des propriétés souhaitables pour obtenir de bonnes reformulations pointwise et nous fournissons des règles pour adapter l'algorithme étape par étape.Nous démontrons que notre matheuristique du MWU conserve une garantie d'approximation relative contrairement à la plupart des heuristiques.Le MWU est comparée à la méthode Multi-Start pour résoudre un HUC en PNL et les résultats numériques penchent en faveur du MWU. / In the electricity industry, and more specifically at the French utility company EDF, mathematical optimization is used to model and solve problems related to electricity production management.To name a few applications: planning for capacity investments, managing depletion risks of hydro-reservoirs, scheduling outages and refueling for nuclear plants.More specifically, hydroelectricity is a renewable, cheap, flexible but limited source of energy.Harnessing hydroelectricity is thus critical for electricity production management.We are interested in Mixed-Integer Non-Linear Programming (MINLP) optimization problems.They are optimization problems whose decision variables can be continuous or discrete and the functions to express the objective and constraints can be linear or non-linear.The non-linearities and the combinatorial aspect induced by the integer variables make these problems particularly difficult to solve.Indeed existing methods cannot always solve large MINLP problems to the optimum within limited computational timeframes.Prior to solution performance, feasibility is preliminary challenge to tackle since we want to ensure the MINLP problems to solve admit feasible solutions.When infeasibilities occur in complex models, it is useful but not trivial to analyze their causes.Also, certifying the exactness of the results compounds the difficulty of solving MINLP problems as solution methods are generally implemented in floating-point arithmetic, which may lead to approximate precision.In this thesis, we work on two optimization problems - a Mixed-Integer Linear Program (MILP) and a Non-Linear Program (NLP) - related to Short-Term Hydropower production Scheduling (STHS).Given finite resources of water in reservoirs, the purpose of STHS is to prescribe production schedules with largest payoffs that are compatible with technical specifications of the hydroelectric plants.While water volumes, water flows, and electric powers can be represented with continuous variables, commitment statuses of turbine units usually have to be formulated with binary variables.Non-linearities commonly originate from the Input/Output functions that model generated power according to water volume and water flow.We decide to focus on two distinguished problems: a MILP with linear discrete features and a NLP with non-linear continuous features.In the second chapter, we deal with feasibility issues of a real-world MILP STHS.Compared with a standard STHS problem, the model features two additional specifications:discrete operational points of the power-flow curve and mid-horizon and final strict targets for reservoir levels.Issues affecting real-world data and numerical computing, together with specific model features, make our problem harder to solve and often infeasible.Given real-world instances, we reformulate the model to make the problem feasible.We follow a step-by-step approach to exhibit and cope with one source of infeasility at a time, namely numerical errors and model infeasibilities.Computational results show the effectiveness of the approach on an original test set of 66 real-world instances that demonstrated a high occurrence of infeasibilities.The third chapter is about the transposition of the Multiplicative Weights Update algorithm to the (nonconvex) nonlinear and mixed integer nonlinear programming setting, based on a particular parametrized reformulation of the problem - denoted pointwise.We define desirable properties for deriving pointwise reformulation and provide generic guidelines to transpose the algorithm step-by-step.Unlike most metaheuristics, we show that our MWU metaheuristic still retains a relative approximation guarantee in the NLP and MINLP settings.We benchmark it computationally to solve a hard NLP STHS.We find it compares favorably to the well-known Multi-Start method, which, on the other hand, offers no approximation guarantee.

Nous abordons le problème de la gestion des chaînes logistiques dans le cadre d’une démarche RSE (Responsabilité Sociale des Entreprises). Nous proposons une approche intégrée qui permet d’opérationnaliser l’évaluation de la performance suivant les dimensions économique, environnementale et sociale aux niveaux de décisions stratégique, tactique et opérationnel. Nous déclinons notre approche aux niveaux stratégique et tactique, pour le problème d’internalisation/externalisation « durable » des activités de la chaîne de valeur d’une part (décision stratégique), et pour le problème de la planification stratégique-tactique durable de la chaîne logistique, d’autre part. Nous réalisons dans le premier cas une analyse de la valeur que nous couplons à l’évaluation de la performance en utilisant une méthode d’aide à la décision multicritères agrégative : l’AHP (Analytical Hierarchy Process). Dans le second cas, nous formulons le problème comme un programme mathématique multi-objectifs que nous résolvons sur la base d’un cas réaliste issu de l’industrie canadienne du bois d’œuvre. Nous obtenons, à l’issue de la résolution mathématique, plusieurs solutions de compromis (optimums de Pareto) présentant différents niveaux de performances économique, environnementale et sociale, permettant au décideur de choisir la solution qui correspond le mieux à sa stratégie RSE. Cette application illustre la méthode proposée et met en avant la valeur pratique de notre approche. / We address the problem of supply chain management in the context of CSR (Corporate Social Responsibility). We propose an integrated approach allowing the operationalization of the economic, environmental and social performances at the strategic, tactical and operational decision levels of the supply chain. In particular, we apply our approach to the strategic and tactical levels, for the problem of sustainable insourcing/outsourcing of the activities of the value chain on the one hand (strategic decision), and for the problem of the strategic-tactical planning of a sustainable supply chain on the other hand. In the former case, we combine value analysis with performance measurement using AHP method (Analytical Hierarchy Process), an aggregative multi-criteria technique. In the latter, we develop a multi-objective mathematical program that we apply to a realistic case inspired by the Canadian lumber industry. After solving the problem, we obtain a multitude of compromise solutions (Pareto optimums) presenting different performance levels following the economic, environmental and social dimensions, allowing the decision maker to choose the solution that reflects best his/her CSR strategy. This application illustrates the proposed method and allows us to assess the practical value of our approach.