Formulations for Dynamic Lot Sizing with Service Levels
Dinakar Gade (gade.6osu.edu)
Abstract: In this paper, we study deterministic dynamic lot-sizing problems with service level constraints on the total number of periods in which backorders can occur over the finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS-SL-I) and study the structure of its solution. We show that an optimal solution to this problem can be found in $\mathcal O(n^2\kappa)$ time, where $n$ is the planning horizon and $\kappa=\mathcal O(n)$ is the maximum number of periods in which demand can be backordered. Using the proposed shortest path algorithms, we develop alternative tight extended formulations for LS-SL-I and one of its relaxations, which we refer to as uncapacitated lot sizing with setups for stocks and backlogs. We show that this relaxation also appears as a substructure in a lot-sizing problem which limits the total amount of a period's demand met from a later period, across all periods. We report computational results that compare the natural and extended formulations on multi-item service-level constrained instances.
Keywords: Fixed-charge networks, lot sizing, service levels, extended formulation, shortest paths
Category 1: Applications -- OR and Management Sciences
Category 2: Integer Programming ((Mixed) Integer Linear Programming )
Category 3: Combinatorial Optimization
Citation: Technical Report, Ohio State University.
Entry Submitted: 12/09/2010
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|