Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition

Gary D. Eppen and R. Kipp Martin
Additional contact information
Gary D. Eppen: University of Chicago, Chicago, Illinois
R. Kipp Martin: University of Chicago, Chicago, Illinois

Operations Research, 1987, vol. 35, issue 6, 832-848

Abstract: Mixed-integer programming models are typically not used to solve realistic-sized production scheduling problems because they require exorbitant solution times. We impose a useful taxonomy on production scheduling problems and develop alternative formulations for a wide variety of problems within the taxonomy. The linear programming relaxation of the new models is very effective in generating bounds. We show that these bounds are equal to those that could be generated using Lagrangian relaxation or column generation. The linear programming bounds increase in effectiveness as the problems become larger. Perhaps of greatest significance is that practitioners can obtain our results using only standard “off-the-shelf” codes such as LINDO or MPSX/370. We report computational experience in several computing environments (hardware and software) on problems with up to 200 products and 10 time periods (2000 0-1 variables).

Keywords: 591 formulations for capacitated lot sizing; 630 LP-based branch-and-bound; 639 theory of variable redefinition for integer programming (search for similar items in EconPapers)
Date: 1987
References: Add references at CitEc
Citations: View citations in EconPapers (86)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.35.6.832 (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:35:y:1987:i:6:p:832-848

Access Statistics for this article

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