Non-linear great deluge with learning mechanism for solving the course timetabling problem

The course timetabling problem has been tackled using a wide range of exact methods, heuristics and meta-heuristics. In recent years, the term hyper-heuristic has emerged for referring to methods that use (meta-) heuristics to choose (meta-) heuristics [8]. Then, a hyper-heuristic is a process which, given a particular problem instance and a number of low-level heuristics, manages the selection and acceptance of the low-level heuristic to apply at any given time, until a stopping condition is met. Low-level heuristics are simple local search operators or domain dependent heuristics. Typically, a hyper-heuristic is meant to search in the space of heuristics instead of searching in the solution space directly. One of the main challenges in designing a hyper-heuristic method is to manage the low-level heuristics with minimum parameter tuning. Early research work on hyper-heuristics focused on the development of advanced strategies for choosing the heuristics to be applied at di�erent points of the search. For example, Soubeiga [24] used a choice function that incorporates principles from reinforcement learning. That choice function rewards or penalises the low-level heuristics according to their success in �nding a better solution. Another mechanism based on tabu search was proposed by Burke et al. [9] in which a tabu list is used to prevent (for a number of iterations) the acceptance of low-level heuristics with poor performance. Ross et al. [20] used a learning classifer system to learn which heuristics were more useful than others when tackling bin packing problems. Other hyper-heuristic approaches include the GA-based hyper-heuristic by Cowling et al. [14], the case-based hyper-heuristic approach by Burke et al. [11] and the ant-based hyper-heuristic by Burke et al. [12]. Also, researchers have proposed di�erent acceptance criteria to drive the selection of low-level heuristics within a hyper-heuristic framework. For example, Soubeiga [24] used a simulated annealing acceptance criterion, Ayob and Kendall [5] used a Monte Carlo acceptance criterion while Kendall and Mohamad [15] used the great deluge acceptance criterion. In this paper, we propose an approach that uses a learning mechanism and a non-linear great deluge acceptance criterion in order to choose which low-level heuristic to apply while solving course timetabling problem instances. Section 2 describes the course timetabling problem tackled in this work. Section 3 reviews previous meta-heuristic and hyper-heuristic methods used to tackle this problem. Section 4 presents the non-linear great deluge hyper-heuristic method proposed in this paper while Section 5 describes and discusses our experimental results. Finally, conclusions and future research are the subject of Section 6.