Equivalence of the LP relaxations of two strong formulations for the capacitated lot-sizing problem with setup times

The multi-item Capacitated Lot-Sizing Problem (CLSP) has been widely studied in the literature due to its relevance to practice, such as its application in constructing a master production schedule. The problem becomes more realistic with the incorporation of setup times since they may use up signif...

Full description

Saved in:
Bibliographic Details
Published in:OR Spectrum 2008-10, Vol.30 (4), p.773-785
Main Authors: Denizel, Meltem, Altekin, F. Tevhide, Süral, Haldun, Stadtler, Hartmut
Format: Article
Language:English
Subjects:
Business and Management
Calculus of Variations and Optimal Control
Optimization
Costs
Heuristic
Linear programming
Mathematical programming
Operations Research/Decision Theory
Regular Article
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The multi-item Capacitated Lot-Sizing Problem (CLSP) has been widely studied in the literature due to its relevance to practice, such as its application in constructing a master production schedule. The problem becomes more realistic with the incorporation of setup times since they may use up significant amounts of the available resource capacity. In this paper, we present a proof to show the linear equivalence of the Shortest Path (SP) formulation and the Transportation Problem (TP) formulation for CLSP with setup costs and times. Our proof is based on a linear transformation from TP to SP and vice versa. In our proof, we explicitly consider the case when there is no demand for an item in a period, a case that is frequently observed in the real world and in test problems in the literature. The equivalence result in this paper has an impact on the choice of model formulation and the development of solution procedures.
ISSN:0171-6468
1436-6304
DOI:10.1007/s00291-007-0094-3