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

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).