Abstract
Hyperheuristics give us the appealing possibility of abstracting the solution method from the problem, since our hyperheuristic, at each decision point, chooses between different low level heuristics rather than different solutions as is usually the case for metaheuristics. By assembling low level heuristics from parameterised components we may create hundreds or thousands of low level heuristics, and there is increasing evidence that this is effective in dealing with every eventuality that may arise when solving different combinatorial optimisation problem instances since at each iteration the solution landscape is amenable to at least one of the low level heuristics. However, the large number of low level heuristics means that the hyperheuristic has to intelligently select the correct low level heuristic to use, to make best use of available CPU time. This paper empirically investigates several hyperheuristics designed for large collections of low level heuristics and adapts other hyperheuristics from the literature to cope with these large sets of low level heuristics on a difficult real-world workforce scheduling problem. In the process we empirically investigate a wide range of approaches for setting tabu tenure in hyperheuristic methods, for a complex real-world problem. The results show that the hyperheuristic methods described provide a good way to trade off CPU time and solution quality.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bai R and Kendall G (2005). An investigation of automated planograms using a simulated annealing based hyperheuristics. In: Ibaraki T, Nonobe K and Yagiura M (eds). Meta-heuristics: Progress as Real Problem Solvers, Selected Papers from the 5th Metaheuristics International Conference (MIC 2003). Springer: New York, pp 87–108.
Baptiste P, Le Pape C and Nuijten W (2001). Constraint Based Scheduling. Kluwer Academic Publishers: London.
Burke E, Hyde M, Kendall G, Ochoa G, Özcan E and Woodward J (2010). A classification of hyperheuristic approaches. In: Gendreau M and Potvin J-Y (eds). Handbook of Metaheuristics. Springer: New York, pp 449–468.
Burke E, Kendall G and Soubeiga E (2003). A tabu-search hyperheuristic for timetabling and rostering. J Heuristics 9 (6): 451–470.
Chakhlevitch K and Cowling P (2005). Choosing the fittest subset of low level heuristics in a hyperheuristic framework. In: Raidl G and Gottlieb J (eds). Proceedings of Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, Vol. 3448. Springer: New York, pp 23–33.
Chakhlevitch K and Cowling P (2008). Hyperheuristics: Recent developments. In: Cotta C, Sevaux M and Sorensen K (eds). Adaptive and Multilevel Metaheuristics, Studies in Computational Intelligence. Vol. 136. Springer: New York, pp 3–29.
Colledge N (2009). Evolutionary approaches to dynamic mobile workforce scheduling. PhD thesis, University of Bradford, UK.
Cowling P and Chakhlevitch K (2003). Hyperheuristic for managing a large collection of low level heuristics to schedule personnel. In: Proceedings of the 2003 IEEE Congress on Evolutionary Computation (CEC2003). IEEE Press: New York, pp 1214–1221.
Cowling P, Colledge N, Dahal K and Remde S (2006). The trade off between diversity and quality for multi-objective workforce scheduling. In: Jens G and Günther R (eds). Proceedings of Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, Vol. 3906. Springer: New York, pp 13–24.
Cowling P, Kendall G and Soubeiga E (2001). A hyperheuristic approach to scheduling a sales summit. In: Proceedings of Selected Papers from the 3rd International Conference on the Practice and Theory of Automated Timetabling (PATAT 2000). Lecture Notes in Computer Science, Vol. 2079. Springer: New York, pp 176–190.
Fang H, Ross P and Corne D (1994). A promising hybrid GA/heuristic approach for open-shop scheduling problems. In: Cohn, A. (ed). Proceedings of the 11th European Conference on Artificial Intelligence. Wiley: New York, pp 590–594.
Glover F and Laguna M (1997). Tabu Search. Springer: New York.
Kaelbling L, Littman M and Moore A (1996). Reinforcement learning: A survey. J Artif Intell Res 4: 237–285.
Kendall G and Hussin N (2005a). A tabu search hyperheuristic approach to the examination timetabling problem at the MARA university of technology. In: Burke E and Trick M (eds). Proceedings of Selected Papers from the 5th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2004). Lecture Notes in Computer Science, Vol. 3616. Springer: New York, pp 270–293.
Kendall G and Hussin N (2005b). An investigation of a Tabu search based hyperheuristic for examination timetabling. In: Kendall G, Burke E and Petrovic S (eds). Proceedings of the Multidisciplinary Scheduling: Theory and Applications Conference. Springer: New York, pp 309–328.
Kendall G, Han L and Cowling P (2002). An investigation of a hyperheuristic genetic algorithm applied to a trainer scheduling problem. In: Fogel D, El-Sharkawi M, Yao X, Greenwood G, Iba H, Marrow P and Shackleton M (eds). Proceedings of Congress on Evolutionary Computation 2002. IEEE Press: New York, pp 1185–1190.
Kolisch R and Hartmann S (2006). Experimental investigation of heuristics for resource-constrained project scheduling: An update. Eur J Opl Res 174 (1): 23–37.
Kwak B, Song N and Miller L (2005). Performance analysis of exponential backoff. IEE-ACM Trans Networking 13 (2): 343–355.
Laguna M, Marti R and Campos V (1999). Intensification and diversification with elite tabu search solutions for the linear ordering problem. Comput Opns Res 26 (12): 1217–1230.
Mladenović N and Hansen P (1997). Variable neighborhood search. Comput Opns Res 24 (11): 1097–1100.
Miller R (1997). Beyond ANOVA: Basics of Applied Statistics. Text in Statistical Science Series. Chapman Hall: London.
Nareyek A (2004). Choosing search heuristics by non-stationary reinforcement learning. In: Resende M and de Sousa J (eds). Metaheuristics: Computer Decision-Making, Vol. 86. Kluwer Academic Publishers: Dordrecht, The Netherlands, pp 523–544.
Pinedo M and Chao X (1999). Operations Scheduling with Applications in Manufacturing and Services. McGraw-Hill: New York.
Remde S, Cowling P, Dahal K and Colledge N (2007). Exact/heuristic hybrids using rVNS and hyperheuristics for workforce scheduling. In: Cotta C and van Hemert J (eds). Proceedings of Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, Vol. 4464. Springer: New York, pp 188–197.
Remde S, Cowling P, Dahal K and Colledge N (2009). Binary exponential back off for tabu tenure in hyperheuristics. In: Cotta C and Cowling P (eds). Proceedings of Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, Vol. 5482. Springer: New York, pp 109–120.
Rolland E, Schilling D and Current J (1996). An efficient tabu search procedure for the p-median problem. Eur J Opl Res 96: 329–342.
Toth P and Vigo D (2001). The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, USA.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Remde, S., Cowling, P., Dahal, K. et al. An empirical study of hyperheuristics for managing very large sets of low level heuristics. J Oper Res Soc 63, 392–405 (2012). https://doi.org/10.1057/jors.2011.48
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2011.48