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

TLDR

Mixed‑integer programming models are typically not used to solve realistic‑sized production scheduling problems because they require exorbitant solution times. The study imposes a taxonomy on production scheduling problems and develops alternative formulations for many problems within that taxonomy. They formulate alternative models and evaluate them computationally on up to 200 products and 10 periods using standard solvers such as LINDO and MPSX/370. The linear‑programming relaxation of the new models yields bounds as strong as those from Lagrangian relaxation or column generation, improves with problem size, and can be obtained with standard off‑the‑shelf solvers.

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