An adaptive Search for the Response Time Variability Problem1

Abstract. The Response Time Variability Problem (RTVP) is an NP-hard combinatorial

scheduling problem which has recently been reported and formalised in the literature. This

problem has a wide range of real-world applications in mixed-model assembly lines, multithreaded

computer systems, broadcast of commercial videotapes 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 minimised. We

propose a greedy but adaptive heuristic that avoids being trapped into a poor solution by

incorporating a look ahead strategy suitable for this particular scheduling problem. The

proposed heuristic outperforms the best existing methods, while being much faster and easier

to understand and to implement.