A Tabu-Search Heuristic for the Capacitated Lot-Sizing Problem with Set-up Carryover

Abstract

This paper presents a tabu-search heuristic for the capacitated lot-sizing problem (CLSP) with set-up carryover. This production-planning problems allows multiple items to be produced within a time period, and setups for items to be carried over from one period to the next. Two interrelated decisions, sequencing and lot sizing, are present in this problem. Our tabu-search heuristic consists of five basic move types—three for the sequencing decisions and two for the lot-sizing decisions. We allow infeasible solutions to 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-adjusting penalties, to strengthen our heuristic. We also propose a lower-bounding 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 problems, indicates that on average our heuristic solutions are within 12% of a bound on optimality. In addition, for the set of test problems our results indicate an 8% reduction in total cost through set-up carryover.