Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition
Operations Research · 1987 · Volume 35 · Issue 6
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
Enable JavaScript for citation tools and additional paper interactions.