Multiechelon Lot Sizing: New Complexities and Inequalities

Ming Zhao () and Minjiao Zhang ()
Additional contact information
Ming Zhao: Lerner College of Business and Economics, University of Delaware, Newark, Delaware 19716
Minjiao Zhang: Department of Economics, Finance, and Quantitative Analysis, Michael J. Coles College of Business, Kennesaw State University, Kennesaw, Georgia 30144

Operations Research, 2020, vol. 68, issue 2, 534-551

Abstract: We study a multiechelon lot-sizing problem for a serial supply chain that consists of a production level and several transportation levels, where the demands can exist in the production echelon as well as in 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. First, we answer an open question in the literature by showing that multiechelon lot sizing with intermediate demands (MLS) is NP-hard. Second, we develop polynomial time algorithms for both uncapacitated and capacitated MLS with a fixed number of echelons. The run times of our algorithms improve on those of many known algorithms for different MLS models. Third, we present families of valid inequalities for MLS that generalize known inequalities. For the uncapacitated case, we develop a polynomial-time separation algorithm and efficient separation heuristics. Finally, we demonstrate the effectiveness of a branch-and-cut algorithm using proposed inequalities to solve large multi-item MLS problems.

Keywords: lot sizing; dynamic programming; network flow; polynomial-time algorithms; valid inequalities (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1867 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:2:p:534-551

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().