A New Local Search Algorithm for No-Wait Fowshops with Setup Time

A new local search algorithm called IVNS (iterated variable neighborhood search) is proposed for the no-wait flowshop scheduling problem with setup time to minimize the total completion time. Three key factors are taken into consideration when designing local search algorithms like IVNS: neighborhoods, neighboring solution evaluations and strategies for escaping local optima. Firstly, three new neighborhoods with larger sizes are introduced to enhance the chance of finding high quality solutions. The neighborhoods are based on job block exchange and have sizes of O(n/+3) or O(n/+4), larger than the commonly-used insertion and exchange neighborhoods. Secondly, an objective increment method is adopted to speed up the evaluation of neighboring solutions in the neighborhoods, leading to two neighboring solutions compared in constant time and the neighborhoods completely explored in times proportional to their sizes. The objective increment method also reduces the time complexity of the famous NEH algorithm by one order. Finally, IVNS tries to escape local optima by switching between different neighborhoods as well as restarting from perturbation of local optima. IVNS is compared with the best known algorithms for the considered problem on 5400 benchmark instances under identical CPU times. Statistic analysis of the experiment results verifies that IVNS remarkably outperforms the reference algorithms in average solution quality.