Summary: Variable neighbourhood search (VNS) is a modern metaheuristic based on systematic changes of the neighbourhood structure within a search to solve optimization problems. The aim of this paper is to propose and analyse a VNS algorithm to solve scheduling problems with parallel machines and sequence-dependent setup times, which are of great importance on the industrial context. Three versions of a greedy randomized adaptive search procedure algorithm are used to compare with the proposed VNS algorithm to highlight its advantages in terms of generality, quality and speed for large instances.