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 benchmar instances