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

Laurent Flindt Muller, Simon Spoorendonk, David Pisinger

    Research output: Contribution to journalJournal articleResearchpeer-review

    680 Downloads (Pure)

    Abstract

    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
    Volume218
    Issue number3
    Pages (from-to)614-623
    ISSN0377-2217
    DOIs
    Publication statusPublished - 2012

    Keywords

    • Heuristics
    • Large scale optimization
    • Production
    • Manufacturing

    Fingerprint Dive into the research topics of 'A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times'. Together they form a unique fingerprint.

    Cite this