High school timetabling using selection hyperheuristics - Nasir Ahmed, Leena Hassan (2014)
Educational timetabling is a hard, challenging real world optimization problem which has been interest to researchers in the fields of optimization and artificial intelligence. This problem has many variants including examination timetabling, university course timetabling, and high school timetabling. In this study we focus on high school timetabling problem which requires scheduling of resources and events in time slots under a set of constraints. Selection hyper-heuristic is a high level search methodology that operates on the space of a fixed set of low level heuristics that operates directly on the space of the solution. The selection hyper-heuristic has two main components: heuristic selection, and move acceptance. A heuristic selection selects a low level heuristic from a set of low level heuristics and applies it to generate a solution. The acceptance method decides to accept or reject the new solution. In this study we present a set of effective selection hyper-heuristics that mixes and controls a set of perturbative low level heuristics to present a solution to the high school timetabling problem. A set of selection methods combined with a set of move acceptance methods were tested and their performance was analysed using different statistical measures on a set of instances of the high school timetabling problem by the aim of comparing and determining the performance variations between the selection hyper-heuristics and choosing the best approach to solve the high school timetabling problem. The empirical results of the study proved the effectiveness of the approach in solving the high school problem achieving results that outperformed most of the best known approaches.