Constructive hyper-heuristics in class timetabling

Evolutionary and stochastic problem solving techniques are often regarded with caution by end users because of their apparent fragility and slowness. Typically each problem is solved in isolation, and results are sensitive to parameters. Users may thus prefer easily understood but worse performing heuristic methods. Hyper-heuristics represents a way around this; the idea is to use evolutionary methods to discover a novel non-evolutionary deterministic algorithm, based on simple and familiar heuristics that has good worst-case performance across a range of problems. We apply this idea to a set of non-trivial class timetabling problems, formerly used in an international timetabling technology competition. The learnt algorithm is fast, greedy, and does not involve additional search or backtracking. Although we use a messy GA to search for the algorithm, it also scales very well; the typical chromosome size is not directly related to the size of the problems to be solved.