Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics

Publication year: 2011
Source: Computers & Operations Research, Volume 38, Issue 12, December 2011, Pages 1816-1825

Ross J.W., James , Bernardo, Almada-Lobo

We propose a general-purpose heuristic approach combining metaheuristics and mixed integer programming to find high quality solutions to the challenging single- and parallel-machine capacitated lotsizing and scheduling problem with sequence-dependent setup times and costs. Commercial solvers fail to solve even medium-sized instances of this NP-hard problem; therefore, heuristics are required to find competitive solutions. We develop construction, improvement and search heuristics all based on MIP formulations. We then compare the performance of these heuristics with those of two metaheuristics and other MIP-based heuristics that have been proposed in the literature, and to a state-of-the-art commercial solver. A comprehensive set of…