Abstract: The Response Time Variability Problem (RTVP) is a NP-hard combinatorial scheduling problem which has recently reported and formalised in the literature. This problem has a wide range of real-world applications in mixed-model assembly lines, multi-threaded computer systems, network environments and others. The RTVP arises whenever products, clients or jobs need to be sequenced in such a way that the variability in the time between the points at which they receive the necessary resources is minimized. The best results in the literature for the RTVP were obtained with a psychoclonal algorithm. We propose a Variable Neighbourhood Search (VNS) algorithm for solving the RTVP. The computational experiment shows that, on average, the results obtained with the proposed algorithm improve strongly on the best obtained results to date.