Parallel scatter search algorithms for exam timetabling. (c2009)

Abstract

University exam timetabling is an important activity for scheduling exams into predefined days, time periods and rooms. Given a set of constraints, exam timetabling is an NP-Hard problem that requires heuristic techniques to be solved adequately within reasonable execution time. For large numbers of exams and students, sequential algorithms are likely to be very time consuming. The purpose of this work is to design and implement a parallel scatter search meta-heuristic algorithm for producing good sub-optimal exam timetables in a reasonable time. Scatter search is a population-based approach that generates solutions over a number of iterations and aims to combine diversification and search intensification. We propose a parallel scatter search that is based distributing the population of candidate solutions over a number of processors in a cluster environment. The main components of scatter search are computed in parallel and an efficient communication technique is employed. Empirical results show that our proposed parallel scatter search algorithm yields good speed-up. Also, they show that the parallel scatter search algorithm improves solution quality since the algorithm explores larger parts of the search space within reasonable time.