title   
  

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

Denizel, Meltem and Altekin, F. Tevhide and Süral, Haldun and Stadtler, Hartmut (2008) Equivalence of the LP relaxations of two strong formulations for the capacitated lot-sizing problem with setup times. Operations Research Spektrum, 30 (4). pp. 773-785. ISSN 0171-6468 (Print) 1436-6304 (Online)

This is the latest version of this item.

[img]PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
95Kb

Official URL: http://dx.doi.org/10.1007/s00291-007-0094-3

Abstract

The multi-item capacitated lot-sizing problem (CLSP) has been widely studied in the literature due to its eminent relevance to practice such as constructing a master production schedule. The incorporation of setups crafts CLSP with a realistic feature demanded by practice. In this paper we present a complete proof for the linear equivalence of the shortest path formulation (SP) and the transportation formulation (TP) formulations for the CLSP with setups. Our proof is based on the linear transformation from TP (SP) to SP (TP). We explicitly consider the zero demand case in our proof since it is frequently observed in the real world and test problem instances used in the literature.

Item Type:Article
Uncontrolled Keywords:Production; Capacitated Lot-Sizing; Strong Formulation; Linear Relaxation.
Subjects:Q Science > Q Science (General)
ID Code:9212
Deposited By:Meltem Denizel
Deposited On:30 Oct 2008 15:25
Last Modified:25 May 2011 14:13

Available Versions of this Item

Repository Staff Only: item control page