Optimization Online


Multiechelon Lot Sizing: New Complexities and Inequalities

Ming Zhao(mzhao***at***bauer.uh.edu)
Minjiao Zhang(mzhang16***at***kennesaw.edu)

Abstract: We study a multiechelon supply chain model that consists of a production level and several transportation levels, where the demands can exist in the production echelon as well as any transportation echelons. With the presence of stationary production capacity and general cost functions, our model integrates production, inventory and transportation decisions and generalizes existing literature on many multiechelon lot-sizing models. We first prove that the multiechelon lot sizing with intermediate demands (MLS) is NP-hard, which can also be seen as a single source network flow problem in a two-dimensional grid. For uncapacitated cases, we propose an algorithm to solve the MLS with general concave costs. The algorithm is of polynomial time when the number of echelons with demands is fixed, regardless of at which echelon the demands occur. With fixed-charge costs, an innovative algorithm is developed, which outperforms known algorithms for different variants of MLS and gives a tight, compact extended formulation with much less variables and constraints. For cases with stationary production capacity, we propose efficient dynamic programming based algorithms to solve the problem with general concave costs as well as the fixed-charge transportation costs without speculative motives. More importantly, our algorithms improve the computational complexities of many lot-sizing models with demand occurring at final echelon only, which are the special cases of our MLS model. We also develop a family of valid inequalities for MLS.

Keywords: lot sizing; dynamic programming

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

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 01/20/2017
Entry Accepted: 01/20/2017
Entry Last Modified: 01/20/2017

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