We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Formulations for dynamic lot sizing with service levels.
- Authors
Gade, Dinakar; Küçükyavuz, Simge
- Abstract
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 \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\mathcal O(n^2\kappa)\end{align*} \end{document} time, where n is the planning horizon and \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\kappa=\mathcal O(n)\end{align*} \end{document} 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. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013
- Subjects
ALGORITHMS; BACK orders; INTEGER programming; MATHEMATICAL programming; LOGISTICS; NAVAL research
- Publication
Naval Research Logistics, 2013, Vol 60, Issue 2, p87
- ISSN
0894-069X
- Publication type
Article
- DOI
10.1002/nav.21519