Multiechelon Lot Sizing: New Complexities and Inequalities

• 成果类型: Article
• 署名作者: Zhao, Ming; Zhang, Minjiao
• 署名单位: University of Delaware; University System of Georgia; Kennesaw State University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1867
• 发表日期: 2020
• 页码: 534-551
• 关键词: lot sizing; dynamic programming; network flow; polynomial-time algorithms; valid inequalities

摘要

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 (MIS) is NP-hard. Second, we develop polynomial time algorithms for both uncapacitated and capacitated MIS with a fixed number of echelons. The run times of our algorithms improve on those of many known algorithms for different MIS models. Third, we present families of valid inequalities for MIS 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 MIS problems.