A tabu-search heuristic for the capacitated lot-sizing problem with set-upcarryover

This paper presents a tabu-search heuristic for the capacitated lot-sizing problem (CLSP) with set-up carryover. This production-planning problems all ows multiple items to be produced within a time period, and setups for item s to be carried over from one period to the next. Two interrelated decision s, sequencing and lot sizing, are present in this problem. Our tabu-search heuristic consists of five basic move types - three for the sequencing deci sions and two for the lot-sizing decisions. We allow infeasible solutions t o be generated at a penalty during the course of the search. We use several search strategies, such as dynamic tabu list, adaptive memory, and self-ad justing penalties, to strengthen our heuristic. We also propose a lower-bou nding procedure to estimate the quality of our heuristic solution. We have also modified our heuristic to produce good solutions for the CLSP without set-up carryover. The computational study, conducted on a set of 540 test p roblems, indicates that on average our heuristic solutions are within 12% o f a bound on optimality. In addition, for the set of test problems our resu lts indicate an 8% reduction in total cost through set-up carryover.