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

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

0.00 Avg rating0 Votes
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: , , ,
Keywords: tabu search, lot sizing
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.

Reviews

Required fields are marked *. Your email address will not be published.