Optimization Online


Algorithms for stochastic lot-sizing problems with backlogging

Yongpei Guan (yguan***at***ou.edu)

Abstract: 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.

Keywords: Integer programming, stochastic programming, lot-sizing

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 05/12/2008
Entry Accepted: 05/13/2008
Entry Last Modified: 06/04/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society