A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times

Publication: Research - peer-reviewJournal article – Annual report year: 2012



View graph of relations

This paper presents a hybrid of a general heuristic framework and a general purpose mixed-integer programming (MIP) solver. The framework is based on local search and an adaptive procedure which chooses between a set of large neighborhoods to be searched. A mixed integer programming solver and its built-in feasibility heuristics is used to search a neighborhood for improving solutions. The general reoptimization approach used for repairing solutions is specifically suited for combinatorial problems where it may be hard to otherwise design suitable repair neighborhoods. The hybrid heuristic framework is applied to the multi-item capacitated lot sizing problem with setup times, where experiments have been conducted on a series of instances from the literature and a newly generated extension of these. On average the presented heuristic outperforms the best heuristics from the literature, and the upper bounds found by the commercial MIP solver ILOG CPLEX using state-of-the-art MIP formulations. Furthermore, we improve the best known solutions on 60 out of 100 and improve the lower bound on all 100 instances from the literature
Original languageEnglish
JournalEuropean Journal of Operational Research
Issue number3
Pages (from-to)614-623
StatePublished - 2012
CitationsWeb of Science® Times Cited: 25


  • Heuristics, Large scale optimization, Production, Manufacturing
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

Download statistics

No data available

ID: 6442743