Heuristics for Multilevel Lot-Sizing with a Bottleneck

Peter J. Billington, John O. McClain and L. Joseph Thomas
Additional contact information
Peter J. Billington: Graduate School of Business, Northeastern University, Boston, Massachusetts
John O. McClain: Johnson Graduate School of Management, Cornell University, Ithaca, New York 14853
L. Joseph Thomas: Johnson Graduate School of Management, Cornell University, Ithaca, New York 14853

Management Science, 1986, vol. 32, issue 8, 989-1006

Abstract: In this paper we present a heuristic method, based on Lagrangian relaxation, for multilevel lot-sizing when there is a single bottleneck facility. A series of Lagrangian relaxations (one for each item in the product structure) is imbedded in a branch and bound procedure. The objective is to find a production schedule that fits within available capacity at minimum cost. The method has two solution phases, dual and primal. In the dual phase of the procedure, implied costs of setups and production are determined based on a tentative schedule. The primal phase is repeated with these new prices and we iterate to reach a good solution. The solution procedure is first tested on two special cases: uncapacitated multilevel lot-sizing and the capacitated, single-level multi-item lot sizing problem. The results show that the solution procedure can provide better solutions than some heuristics designed especially for those problems. Test results on the bottleneck problem indicate that good feasible solutions are found for problems too difficult to solve with exact methods.

Keywords: inventory/production: deterministic models; heuristics; programming: integer algorithms; branch and bound (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.32.8.989 (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:ormnsc:v:32:y:1986:i:8:p:989-1006

Access Statistics for this article

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