As a traditional model in the operations research and management science domain, lot-sizing problem is embedded in many application problems such as production and inventory planning and has been consistently drawing attentions from researchers. There is significant research progress on polynomial time algorithm developments for deterministic uncapacitated lot-sizing problems based on Wagner-and-Whitin property. However, in practice, problem parameters are seldom known in advance. For most cases, even the distribution of the problem parameters is not known. In this paper we consider basic versions of deterministic lot-sizing models in which problem parameters (e.g., demand) are stochastic and develop corresponding scenario tree based stochastic lot-sizing models. For these models, a backward dynamic programming recursion framework is developed based on production path properties. This framework allows us to show that the optimal value function is piecewise linear and continuous, which we can further use to define polynomial time algorithms for several different problems, including those with backlogging and varying capacities under certain scenario tree structure. Moreover, we develop polynomial time algorithms that run in O(n^2) and O(n^2T\log n) times respectively for stochastic uncapacitated and constant capacitated lot-sizing problems with backlogging, regardless of scenario tree structure.
Article
View Algorithms for stochastic lot-sizing problems with backlogging