The Response Time Variability Problem (RTVP) is an NP-hard scheduling optimization problem that has recently appeared in the literature. This problem has a wide range of real-life applications in, for example, manufacturing, hard real-time systems, operating systems and network environments. The RTVP occurs whenever models, clients or jobs need to be sequenced to minimize variability in the time between the instants at which they receive the necessary resources. The RTVP has been already solved in the literature with a multi-start and a GRASP algorithm. We propose an improved multi-start and an improved GRASP algorithm to solve the RTVP. The computational experiment shows that, on average, the results obtained with our proposed algorithms improve on the best obtained results to date.