An Adaptive Search for the Response Time Variability Problem

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, multi-threaded 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.