New VNS heuristic for total flowtime flowshop scheduling problem

This paper presents a new Variable Neighborhood Search (VNS) approach to the permutational flowshop scheduling with total flowtime criterion, which produced 29 novel solutions for benchmark instances of the investigated problem. Although many hybrid approaches that use VNS do exist in the problems literature, no experimental study was made examining distinct VNS alternatives or their calibration. In this study six different ways to combine the two most used neighborhoods in the literature of the problem, named job interchange and job insert, are examined. Computational experiments were carried on instances of a known dataset and the results indicate that one of the six tested VNS methods, named VNS4, is quite effective. It was compared to a state-of-the-art evolutionary approach and statistical tests applied on the computational results indicate that VNS4 outperforms its competitor on most benchmark instances.

► In this study we model a novel VNS approach for the total flowtime flowshop problem. ► The new method is compared with state-of-art methods using a known instance dataset. ► A hybrid using state-of-art evolutionary algorithm and the new VNS is also proposed. ► Statistical analysis is used to compare the performance of the methods. ► 34 new minimum solutions were found during the tests, 29 of them by the new VNS.