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, 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anily S, Glass CA and Hassin R (1998). The scheduling of maintenance service. Discrete Appl Math 82: 27–42.
Balinski ML and Young HP (1982). Fair Representation. Yale University Press: New Haven.
Bollapragada S, Bussieck MR and Mallik S (2004). Scheduling commercial videotapes in broadcast television. Opns Res 52: 679–689.
Brusco MJ (2008). Scheduling advertising slots for television. J Opl Res Soc 59: 1363–1372.
Corominas A, Kubiak W and Moreno N (2007). Response time variability. Journal of Sched 10: 97–110.
Corominas A, Kubiak W and Pastor R (2009). Heuristic algorithms for solving the response time variability problem. Technical report IOC-DT-P-2009-03, Universitat Politècnica de Catalunya, Spain.
Corominas A, Kubiak W and Pastor R (2010). Mathematical programming modeling of the response time variability problem. Eur J Opl Res 200: 347–357.
Dong L, Melhem R and Mosse D (1998). Time slot allocation for real-time messages with negotiable distance constrains requirements. Fourth IEEE Real-Time Technology and Applications Symposium (RTAS’98), Denver, CO, 131–136.
García-Villoria A and Pastor R (2010a). Solving the response time variability problem by means of the electromagnetism-like mechanism. Int J Prod Res 48: 6701–6714.
García-Villoria A and Pastor R (2010b). Solving the response time variability problem by means of a psychoclonal approach. J Heuristics 16: 337–351.
García-Villoria A and Pastor R (2010c). Solving the response time variability problem by means of a genetic algorithm. Eur J Opl Res 202: 320–327.
García-Villoria A, Corominas A, Delorme X, Dolgui A, Kubiak W and Pastor R (2009). A branch and bound approach for the response time variability problem. Technical report IOC-DT-P-2009-05, Universitat Politècnica de Catalunya, Spain.
Herrmann JW (2007). Generating cyclic fair sequences using aggregation and stride scheduling. Technical Report TR 2007-12, University of Maryland, USA, http://hdl.handle.net/1903/7082.
Kubiak W (1993). Minimizing variation of production rates in just-in-time systems: A survey. Eur J Opl Res 66: 259–271.
Kubiak W (2004). Fair sequences. Chapter 19. In: Leung JY-T (ed). Handbook of Scheduling: Algorithms, Models and Performance Analysis. Boca Raton, FL: Chapman and Hall/CRC Press.
Miltenburg J (1989). Level schedules for mixed-model assembly lines in just-in-time production systems. Mngt Sci 35: 192–207.
Salhi S (2006). Heuristic search: the science of tomorrow. In: Salhi S (ed) OR48 Key Note Papers. Bath: ORS, pp 39–58.
Waldspurger CA and Weihl WE (1994). Lottery scheduling: Flexible proportional-share resource management. First USENIX Symposium on Operating System Design and Implementation, Monterey, California.
Waldspurger CA and Weihl WE (1995). Stride scheduling: Deterministic proportional-share resource management. Technical Report MIT/LCS/TM-528, Massachusetts Institute of Technology, MIT Laboratory for Computer Science, https://eprints.kfupm.edu.sa/67117.
Wei WD and Liu CL (1983). On a periodic maintenance problem. Opns Res Lett 2: 90–93.
Acknowledgements
The authors thank both referees for their time and effort in improving the presentation as well as the content of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the Spanish Ministry of Education and Science under project DPI2007-61905; co-funded by the ERDF, also supported by the Department of Innovationm, Universities and Enterprise of Generalitat de Catalunya under grant BE-DGR-2008. The research was conducted while visiting CLHO at Kent.
Rights and permissions
About this article
Cite this article
Salhi, S., García-Villoria, A. An adaptive search for the response time variability problem. J Oper Res Soc 63, 597–605 (2012). https://doi.org/10.1057/jors.2011.46
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2011.46