An adaptive search for the response time variability problem

作者：Salhi S; Garcia Villoria A^*

来源：Journal of the Operational Research Society, 2012, 63(5): 597-605.

DOI：10.1057/jors.2011.46

• response time variability
• heuristics
• adaptive search
• scheduling
• fair sequences

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. Journal of the Operational Research Society (2012) 63, 597-605. doi:10.1057/jors.2011.46 Published online 13 July 2011

• 出版日期2012-5