Optimization Online


A multi-stage stochastic integer programming approach for a multi-echelon lot-sizing problem with returns and lost sales

Franco Quezada(franco.quezada***at***lip6.fr)
CÚline Gicquel(gicquel***at***lri.fr)
Safia Kedad-Sidhoum(safia.kedad_sidhoum***at***cnam.fr)
Quan Dong(dongquan.math***at***gmail.com)

Abstract: We consider an uncapacitated multi-item multi-echelon lot-sizing problem within a remanufacturing system involving three production echelons: disassembly, refurbishing and reassembly. We seek to plan the production activities on this system over a multi-period horizon. We consider a stochastic environment, in which the input data of the optimization problem are subject to uncertainty. We propose a multi-stage stochastic integer programming approach relying on scenario trees to represent the uncertain information structure and develop a Branch-and-Cut algorithm in order to solve the resulting mixed-integer linear program to optimality. This algorithm relies on a new set of tree inequalities obtained by combining valid inequalities previously known for each individual scenario of the scenario tree. These inequalities are used within a cutting-plane generation procedure based on a heuristic resolution of the corresponding separation problem. Computational experiments carried out on randomly generated instances show that the proposed Branch-and-Cut algorithm performs well as compared to the use of a stand-alone mathematical solver. Finally, rolling horizon simulations are carried out to assess the practical performance of the stochastic planning model with respect to the deterministic model.

Keywords: Stochastic lot-sizing, remanufacturing system, lost sales, multi-stage stochastic integer programming, scenario tree, valid inequalities, branch-and-cut algorithm

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 08/31/2018
Entry Accepted: 08/31/2018
Entry Last Modified: 08/31/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society