A cellular memetic algorithm for the examination timetabling problem

The timetabling problem involves the scheduling of a set of entities (e.g., lectures, exams, vehicles, or people) to a given set of resources in a limited number of time slots, while satisfying a set of constraints. In this paper, a cellular memetic algorithm is proposed for solving the examination timetabling problem. Cellular evolutionary algorithms are population-based metaheuristics. They differ from non-cellular algorithms in that the population is organised in a cellular structure, providing for a smooth actualisation of the populations that contributes to improving the population diversity. The proposed cellular evolutionary algorithm is hybridised with the threshold acceptance local search metaheuristic. The implemented algorithm uses feasible genetic recombination and local search operators, thus limiting the exploration to the feasible solution space. The effect of the threshold acceptance used in the hybrid algorithm for the examination timetabling problem is studied. It is shown that a low threshold decreasing rate is needed in order to rearrange the most difficult exams in better periods, allowing for the easy set of exams to be placed in good periods as well. The approach was tested on the public Toronto and ITC 2007 benchmark sets. The proposed hybrid is able to attain four and three new upper bounds for the Toronto and ITC 2007 benchmark sets, respectively.