Gade, Dinakar; Küçükyavuz, Simge Formulations for dynamic lot sizing with service levels. (English) Zbl 1407.90016 Nav. Res. Logist. 60, No. 2, 87-101 (2013). Summary: In this article, we study deterministic dynamic lot-sizing problems with a service-level constraint on the total number of periods in which backlogs can occur over a 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 backlogged. 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.} Cited in 7 Documents MSC: 90B05 Inventory, storage, reservoirs 90B80 Discrete location and assignment Keywords:fixed-charge networks; lot sizing; service levels; extended formulation; shortest paths PDFBibTeX XMLCite \textit{D. Gade} and \textit{S. Küçükyavuz}, Nav. Res. Logist. 60, No. 2, 87--101 (2013; Zbl 1407.90016) Full Text: DOI