A genetic algorithm selection perturbative hyper-heuristic for solving the school timetabling problem

Abstract

Research in the domain of school timetabling has essentially focused on applying various techniques such as integer programming, constraint satisfaction, simulated annealing, tabu search and genetic algorithms to calculate a solution to the problem. Optimization techniques like simulated annealing, tabu search and genetic algorithms generally explore a solution space. Hyper-heuristics, on the other hand, search a heuristic space with the aim of providing a more generalized solution to the particular optimisation problem. This is a fairly new technique that has proven to be successful in solving various combinatorial optimisation problems. There has not been much research into the use of hyper-heuristics to solve the
school timetabling problem. This study investigates the use of a genetic algorithm selection perturbative hyper-heuristic for solving the school timetabling problem. A two-phased approach is taken, with the rst phase focusing on hard constraints, and the second on soft constraints. The genetic algorithm uses tournament selection to choose parents, to which
the mutation and crossover operators are applied. The genetic algorithm selection perturbative hyper-heuristic (GASPHH) was applied to ve dierent school timetabling problems. The performance of the hyper-heuristic was compared to that of other methods applied to these problems, including a genetic algorithm that was applied directly to the solution space. GASPHH performed well over all ve dierent types of school timetabling problems.

Key words: Timetabling, hyper-heuristics, combinatorial optimisation, evolutionary algorithms.