Mixed-integer linear programming approaches for deterministic and stochastic lot-sizing problems

Autor: Gicquel, Céline
Přispěvatelé: Réseaux & Optimisation Combinatoire et Stochastique (ROCS), Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Science des Données (SDD), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Université Paris Saclay, Alain Denise, Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Science des Données (SDD), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)
Jazyk: angličtina
Rok vydání: 2021
Předmět:
Zdroj: Operations Research [cs.RO]. Université Paris Saclay, 2021
Popis: This thesis, presented in view of obtaining an accreditation to supervise research, describes the research work I carried out as an assistant professor at the Université Paris Saclay during the last ten years. This work deals with the development of mixed-integer linear programming approaches for difficult deterministic and stochastic combinatorial optimization problems, mainly coming from applications in manufacturing, supply chain management and telecommunication.Part I is devoted to the work carried out on lot-sizing problems. We first study an extension of the discrete lot-sizing and scheduling problem in which the setup costs are sequencedependent and propose a new family of multi-item multi-period valid inequalities to strengthen the mathematical formulation of this problem. We then consider an important aspect of production planning, namely the fact that it is based on input data which are relative to the near futureand, as a consequence, are not always perfectly known at the time when the production plan has to be built. We thus study several stochastic programming approaches for lot-sizing. The first proposed approach assumes a rather simplified setting for the decision process. It namely considers a single-stage decision process in which the whole production plan is built before any additional information on the stochastic demand realization becomes available and cannot be updated afterward as the demand unfolds over time. We formulate this stochastic problemas a joint chance-constrained program and propose a new approximate solution approach for this problem called the partial sample approximation approach. Then, in order to further improve the modeling of the actual decision process, we investigate a multi-stage stochastic programming approach which explicitly takes into account the fact that production decisions are usually not made once and for all but rather adjusted over time according to the actual realizations of the uncertain parameters. Our main contribution consists in the development of a new algorithm capable of providing good-quality solutions for large-size instances of the stochastic single-item uncapacitated lot-sizing problem. This algorithm combines a nested decomposition algorithm called the Stochastic Dual Dynamic integer Programming (SDDiP) algorithm with a cutting-plane generation approach based on known valid inequalities. Finally, in order to extend the previous work which focuses on single-item single-echelon single-resource production systems, we consider a multi-item multi-echelon multi-resource production system linked to the remanufacturing of used products and study a multi-stage stochastic programming model for this problem. We thus present a customized branch-and-cut algorithm basedon a new family of valid inequalities for this problem.In parallel to the above-mentioned work on lot-sizing, I studied among others two applied facility location problems through industrial collaborations. The corresponding work is reported in Part II of the manuscript. We first discuss a facility location problem linked to the design of the outbound logistics network of Renault. The main contribution of this work is related to the development of a tractable heuristic solution approach for this complex large-size location-routing problem. We also investigate the placement of virtual network functions in a telecommunication network to secure it against a distributed denial-of-service attack. The main novelty here consists in the development of a new robust optimization model and adversarial algorithm for this problem.
Databáze: OpenAIRE
Externí odkaz: