A Computational Comparison of Lower
Bounds for
Big Bucket Production Planning Problems
A.J. Miller and K. Akartunali
University of
We
review various methods for generating lower bounds for multi-level, multi-item
capacitated lot-sizing problems in which items compete for capacity on a number
of given machines. These methods include those using strong formulations (such
as extended formulations and valid inequalities), decomposition approaches such
as Lagrangian relaxation, and hybrids of these
approaches. This research suggests that simple MIP heuristics are, for most
problems, as effective as any other methods for generating strong lower bounds.
It also shows where research effort in the future needs to be focused if the
needed significant progress in generating stronger lower bounds for these
problems is to be made.