MIP-based local search for permutation flowshop scheduling with makespan objective

The permutation flowshop scheduling problem with makespan objective, or PFM for short, is a classic NP-hard scheduling problem. At present, the most promising heuristics for the PFM are based on variations of local search. This led us to consider five new neighbourhoods for the PFM. Each neighbourhood is of exponential size, but can be explored quite quickly by solving a small mixed-integer program. We propose a matheuristic framework that incorporates our proposed neighbourhoods to evaluate and compare their effectiveness. Extensive computational experiments show that integrating our best neighbourhood to the proposed matheuristic reduces the makespan by over 60% on average, compared to the variant without it, on both the classical Taillard benchmark instances and the more recent instances proposed by Vallada, Ruiz and Framinan. • Five neighbourhoods were developed for the permutation flowshop scheduling problem with makespan objective (PFM), each of exponential size but efficiently explored by solving small mixed-integer programs. • A matheuristic was proposed that integrates these neighbourhoods to improve initial solutions generated by the ‘NEH and shift’ heuristic. • Computational results demonstrate that incorporating our best neighbourhood leads to an average makespan reduction of over 60% compared to ‘NEH and shift’ solutions for benchmark instances from Taillard and Vallada et al..