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.
Dr. Zhao is an assistant professor of business analytics in the Department of Decision and Information Sciences at the University of Houston. Before joining the University of Houston, he was served as senior operations research specialist in Advanced Analytics and Optimization Services (AAOS) group at SAS from 2009 to 2015. He received a PhD degree in Industrial & System Engineering from University at Buffalo in 2008 and was a postdoctoral researcher at IBM T.J. Watson research center.