Journal
OPERATIONS RESEARCH
Volume 60, Issue 4, Pages 918-935Publisher
INFORMS
DOI: 10.1287/opre.1120.1058
Keywords
-
Funding
- National Science Foundation [NSF-CMMI] [0917952]
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [0917952] Funding Source: National Science Foundation
Ask authors/readers for more resources
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.
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