Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem

The response time variability problem (RTVP) is a scheduling problem with a wide range of real‐world applications: mixed‐model assembly lines, multi‐threaded computer systems, network environments, broadcast of commercial videotapes and machine maintenance, among 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 minimised. Since the RTVP is NP‐hard, several heuristic and metaheuristic techniques are needed to solve non‐small instances. The published metaheuristic procedure that obtained the best solutions, on average, for non‐small RTVP instances is an algorithm based on a variant of the variable neighbourhood search (VNS), called Reduced VNS (RVNS). We propose hybridising RVNS with three existing algorithms based on tabu search, multi‐start and particle swarm optimisation. The aim is to combine the strengths of the metaheuristics. A computational experiment is carried out and it is shown that, on average, all proposed hybrid methods are able to improve the best published solutions.