Developing novel meta-heuristic, hyper-heuristic and cooperative search for course timetabling problems - Henry Obit, Joe (2010)
The research presented in this PhD thesis focuses on the problem of university course timetabling, and examines the various ways in which metaheuristics, hyperheuristics and cooperative heuristic search techniques might be applied to this sort of problem. The university course timetabling problem is an NP-hard and also highly constrained combinatorial problem. Various techniques have been developed in the literature to tackle this problem. The research work presented in this thesis approaches this problem in two stages. For the first stage, the construction of initial solutions or timetables, we propose four hybrid heuristics that combine graph colouring techniques with a well-known local search method, tabu search, to generate initial feasible solutions. Then, in the second stage of the solution process, we explore different methods to improve upon the initial solutions. We investigate techniques such as single-solution metaheuristics, evolutionary algorithms, hyper-heuristics with reinforcement learning, cooperative low-level heuristics and cooperative hyper-heuristics. In the experiments throughout this thesis, we mainly use a popular set of benchmark instances of the university course timetabling problem, proposed by Socha et al. [152], to assess the performance of the methods proposed in this thesis. Then, this research work proposes algorithms for each of the two stages, construction of initial solutions and solution improvement, and analyses the proposed methods in detail.