Article ID: | iaor20031827 |
Country: | United States |
Volume: | 47 |
Issue: | 6 |
Start Page Number: | 851 |
End Page Number: | 863 |
Publication Date: | Jun 2001 |
Journal: | Management Science |
Authors: | Gopalakrishnan Mohan, Bourjolly Jean-Marie, Ding Ke, Mohan Srimathy |
Keywords: | tabu search, lot sizing |
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.