Skip to main content
SpringerLink
Log in

Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

The response time variability problem (RTVP) is a scheduling problem with a wide range of real-world applications: mixed-model assembly lines, multi-threaded computer systems, network environments, broadcast of commercial videotapes and machine maintenance, among 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. Since the RTVP is NP-hard, several heuristic and metaheuristic techniques are needed to solve non-small instances. The published metaheuristic procedure that obtained the best solutions, on average, for non-small RTVP instances is an algorithm based on a variant of the variable neighbourhood search (VNS), called Reduced VNS (RVNS). We propose hybridising RVNS with three existing algorithms based on tabu search, multi-start and particle swarm optimisation. The aim is to combine the strengths of the metaheuristics. A computational experiment is carried out and it is shown that, on average, all proposed hybrid methods are able to improve the best published solutions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Adenso-Díaz B, Laguna M (2006) Fine-tuning of algorithms using fractional experimental designs and local search. Oper Res 54:99–114

    Article  Google Scholar 

  • Anghinolfi D, Paolucci M (2009) A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times. Eur J Oper Res 193:73–85

    Article  Google Scholar 

  • Anily S, Glass CA, Hassin R (1998) The scheduling of maintenance service. Discrete Appl Math 82:27–42

    Article  Google Scholar 

  • Balinski ML, Young HP (1982) Fair representation. Yale University Press, New Haven

    Google Scholar 

  • Bar-Noy A, Nisgav A, Patt-Shamir B (2002) Nearly optimal perfectly-periodic schedules. Distrib Comput 15:207–220

    Article  Google Scholar 

  • Boender CGE, Rinnooy AHG, Stougie L, Timmer GT (1982) A stochastic method for global optimization. Math Program 22:125–140

    Article  Google Scholar 

  • Bollapragada S, Bussieck MR, Mallik S (2004) Scheduling commercial videotapes in broadcast television. Oper Res 52:679–689

    Article  Google Scholar 

  • Brusco MJ (2008) Scheduling advertising slots for television. J Oper Res Soc 59:1363–1372

    Article  Google Scholar 

  • Corominas A, Kubiak W, Moreno N (2007) Response time variability. J Sched 10:97–110

    Article  Google Scholar 

  • Corominas A, García-Villoria A, Pastor R (2008) Solving the response time variability problem by means of multi-start and GRASP metaheuristics. Spec Issue Front Artif Intell Appl Artif Intell Res Dev 184:128–137

    Google Scholar 

  • Corominas A, García-Villoria A, Pastor R (2009a) Using tabu search for the response time variability problem. In: 3rd international conference on industrial engineering and industrial management (CIO 2009), Barcelona and Terrassa, Spain

    Google Scholar 

  • Corominas A, García-Villoria A, Pastor R (2009b) Resolución del response time variability problem mediante tabu search. In: VIII evento internacional de matemática y computación (COMAT’2009), Universidad de Matanzas, Cuba

    Google Scholar 

  • Corominas A, García-Villoria A, Pastor R (2009c) Solving the response time variable problem by means of a variable neighbourhood search algorithm. In: 13th IFAC symposium of information control problems in manufacturing (INCOM 2009), Moscow, Russia

    Google Scholar 

  • Corominas A, Kubiak W, Pastor R (2010) Mathematical programming modeling of the response time variability problem. Eur J Oper Res 200:347–357

    Article  Google Scholar 

  • Dong L, Melhem R, Mosse D (1998) Time slot allocation for real-time messages with negotiable distance constrains requirements. In: Fourth IEEE real-time technology and applications symposium (RTAS’98), Denver, CO, 131–136

    Google Scholar 

  • Ekşioğlu B, Ekşioğlu SD, Pramod J (2008) A tabu search algorithm for the flowshop scheduling problem with changing neighborhoods. Comput Ind Eng 54:1–11

    Article  Google Scholar 

  • Eiben AE, Hinterding R, Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Trans Evol Comput 3:124–141

    Article  Google Scholar 

  • García A, Pastor R, Corominas A (2006) Solving the response time variability problem by means of metaheuristics. Spec Issue Front Artif Intell Appl Artif Intell Res Dev 146:187–194

    Google Scholar 

  • García-Villoria A, Pastor R (2009) Introducing dynamic diversity into a discrete particle swarm optimization. Comput Oper Res 36:951–966

    Article  Google Scholar 

  • García-Villoria A, Pastor R (2010a) Solving the response time variability problem by means of a psychoclonal approach. J Heuristics 16:337–351

    Article  Google Scholar 

  • García-Villoria A, Pastor R (2010b) Solving the response time variability problem by means of the electromagnetism-like mechanism. Int J Prod Res 48:6701–6714

    Article  Google Scholar 

  • García-Villoria A, Pastor R (2010c) Solving the response time variability problem by means of a genetic algorithm. Eur J Oper Res 202:320–327

    Article  Google Scholar 

  • García-Villoria A, Pastor R, Corominas A (2010) Solving the response time variability problem by means of the cross-entropy method. Int J Manuf Technol Manag 20:316–330

    Google Scholar 

  • Gendreau M (2003) An introduction to tabu search. In: Handbook of metaheuristics. Kluwer Academic, Dordrecht. Chap 2

    Google Scholar 

  • Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 5:533–549

    Article  Google Scholar 

  • Han CC, Lin KJ, Hou CJ (1996) Distance-constrained scheduling and its applications in real-time systems. IEEE Trans Comput 45:814–826

    Article  Google Scholar 

  • Hansen P, Mladenovic N (1999) An introduction to variable neighborhood search. In: Meta-heuristics: advances and trends in local search paradigms for optimization. Kluwer Academic, Dordrecht, pp. 433–458

    Chapter  Google Scholar 

  • Hansen P, Mladenovic N (2003) Variable neighborhood search. In: Handbook of metaheuristics. Kluwer Academic, Dordrecht. Chap 6

    Google Scholar 

  • Herrmann JW (2007) Generating cyclic fair sequences using aggregation and stride scheduling. Technical report, University of Maryland, USA. Available at http://hdl.handle.net/1903/7082

  • Herrmann JW (2009) Using aggregation to reduce response time variability in cyclic fair sequences. J Sched. doi:10.1007/s10951-009-0127-7

    Google Scholar 

  • Hoos H, Stützle T (2005) Stochastic local research: foundations and applications. Morgan Kaufmann, San Francisco

    Google Scholar 

  • Kennedy J, Eberhart RC (1995) Particle swarm optimization. In IEEE international conference on neural networks, Australia, pp. 1942–1948

    Google Scholar 

  • Kubiak W (1993) Minimizing variation of production rates in just-in-time systems: a survey. Eur J Oper Res 66:259–271

    Article  Google Scholar 

  • Kubiak W (2004) Fair sequences. In: Handbook of scheduling: algorithms, models and performance analysis. Chapman and Hall, London. Chap 19

    Google Scholar 

  • Kubiak W (2009) Proportional optimization and fairness. International series in operations research & management science. Springer, Berlin

    Google Scholar 

  • Martí R (2003) Multi-start methods. In: Handbook of metaheuristics. Kluwer Academic, Dordrecht. Chap 12

    Google Scholar 

  • Miltenburg J (1989) Level schedules for mixed-model assembly lines in just-in-time production systems. Manag Sci 35:192–207

    Article  Google Scholar 

  • Mladenovic N, Hansen P (1997) Variable neighbourhood search. Comput Oper Res 24:1097–1100

    Article  Google Scholar 

  • Monden Y (1983) Toyota production systems. Industrial Engineering and Management Press, Norcross

    Google Scholar 

  • Tasgetiren MF, Liang YC, Sevkli M, Gencyuilmaz G (2007) A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. Eur J Oper Res 177:1930–1947

    Article  Google Scholar 

  • Tchomté SK, Gourgand M (2009) Particle swarm optimization: a study of particle displacement for solving continuous and combinatorial optimization problems. Int J Prod Econ 121:57–67

    Article  Google Scholar 

  • Waldspurger CA, Weihl WE (1994) Lottery scheduling: flexible proportional-share resource management. In: First USENIX symposium on operating system design and implementation, Monterey, California

    Google Scholar 

  • Waldspurger CA, 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. Available at https://eprints.kfupm.edu.sa/67117

  • Wei WD, Liu CL (1983) On a periodic maintenance problem. Oper Res Lett 2:90–93

    Article  Google Scholar 

  • Xu J, Sohoni M, McCleery M, Bailey TG (2006) A dynamic neighbourhood based tabu search algorithm for real-world flight instructor scheduling. Eur J Oper Res 169:978–993

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Industrial and Control Engineering (IOC), Universitat Politècnica de Catalunya (UPC), Av. Diagonal 647 (Edif. ETSEIB), 11th floor, 08028, Barcelona, Spain

    Albert Corominas, Alberto García-Villoria & Rafael Pastor

Authors
  1. Albert Corominas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alberto García-Villoria
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rafael Pastor
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alberto García-Villoria.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Corominas, A., García-Villoria, A. & Pastor, R. Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem. TOP 21, 296–312 (2013). https://doi.org/10.1007/s11750-011-0175-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-011-0175-y

Keywords

Mathematics Subject Classification (2000)

Search

Navigation