Multiechelon Lot Sizing: New Complexities and 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 (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.