This paper develops a new VNS approach to Permutational Flow shop Scheduling Problem with Total Flow time criterion. There are many hybrid approaches inthe problem’s literature, that make use of VNS internally, usually applying job insert neighbourhood followed by job interchange neighbourhood. In this study different ways to combine both neighbourhoods were examined. All tests use the benchmark data set from . The results indicates, that there is a more profitable way to combine both neighbourhoods than the one frequently used in literature. The new VNS produces results comparable with state-of-art methods, and obtained 25 novel solutions.
The paper has been accepted. It is online on http://dx.doi.org/10.1016/j.eswa.2012.01.152