A Tabu-Search Hyperheuristic for Timetabling and Rostering

Citation

Burke E, Kendall G & Soubeiga E (2003) A Tabu-Search Hyperheuristic for Timetabling and Rostering. Journal of Heuristics, 9 (6), pp. 451-470. https://doi.org/10.1023/B%3AHEUR.0000012446.94732.b6

Abstract
Hyperheuristics can be defined to be heuristics which choose between heuristics in order to solve a given optimisation problem. The main motivation behind the development of such approaches is the goal of developing automated scheduling methods which are not restricted to one problem. In this paper we report the investigation of a hyperheuristic approach and evaluate it on various instances of two distinct timetabling and rostering problems. In the framework of our hyperheuristic approach, heuristics compete using rules based on the principles of reinforcement learning. A tabu list of heuristics is also maintained which prevents certain heuristics from being chosen at certain times during the search. We demonstrate that this tabu-search hyperheuristic is an easily re-usable method which can produce solutions of at least acceptable quality across a variety of problems and instances. In effect the proposed method is capable of producing solutions that are competitive with those obtained using state-of-the-art problem-specific techniques for the problems studied here, but is fundamentally more general than those techniques.

Keywords
hyperheuristic; tabu search; heuristic; scheduling; rostering; timetabling; local search

Journal
Journal of Heuristics: Volume 9, Issue 6