- Formulations for Dynamic Lot Sizing with Service Levels Dinakar Gade (gade.6osu.edu) Simge Kucukyavuz (kucukyavuz.2osu.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. Download: [PDF]Entry Submitted: 12/09/2010Entry Accepted: 12/09/2010Entry Last Modified: 05/08/2012Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.