A Polyhedral Study of Multiechelon Lot Sizing with Intermediate Demands

Minjiao Zhang (), Simge Küçükyavuz () and Hande Yaman ()
Additional contact information
Minjiao Zhang: Department of Integrated Systems Engineering, The Ohio State University, Columbus, Ohio 43210
Simge Küçükyavuz: Department of Integrated Systems Engineering, The Ohio State University, Columbus, Ohio 43210
Hande Yaman: Department of Industrial Engineering, Bilkent University, Ankara, Turkey

Operations Research, 2012, vol. 60, issue 4, 918-935

Abstract: In this paper, we study a multiechelon uncapacitated lot-sizing problem in series ( m -ULS), where the output of the intermediate echelons has its own external demand and is also an input to the next echelon. We propose a polynomial-time dynamic programming algorithm, which gives a tight, compact extended formulation for the two-echelon case (2-ULS). Next, we present a family of valid inequalities for m -ULS, show its strength, and give a polynomial-time separation algorithm. We establish a hierarchy between the alternative formulations for 2-ULS. In particular, we show that our valid inequalities can be obtained from the projection of the multicommodity formulation. Our computational results show that this extended formulation is very effective in solving our uncapacitated multi-item two-echelon test problems. In addition, for capacitated multi-item, multiechelon problems, we demonstrate the effectiveness of a branch-and-cut algorithm using the proposed inequalities.

Keywords: lot sizing; multiechelon; facets; extended formulation; fixed-charge networks (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1058 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:4:p:918-935

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().