Journal
NAVAL RESEARCH LOGISTICS
Volume 60, Issue 2, Pages 87-101Publisher
WILEY
DOI: 10.1002/nav.21519
Keywords
Fixed-charge networks; lot sizing; service levels; extended formulation; shortest paths
Categories
Funding
- NSF-CMMI Grants [0917952, 1100383]
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [1100383] Funding Source: National Science Foundation
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [1055668, 0917952] Funding Source: National Science Foundation
Ask authors/readers for more resources
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 O(n(2)kappa) time, where n is the planning horizon and kappa = 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. (C) 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 87-101, 2013
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available