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.