Scatter Search and Graph Heuristics for the Examination Timetabling Problem

Drifa Hadjidj1 and Habiba Drias2
1Département d’Informatique, Université M’hamed Bouguerra, Algérie
2Institut National d’Informatique-INI-, Algérie

Abstract: Examination timetabling problem is an optimization problem which consists in assigning a set of exams to a set of contiguous time slot, satisfying a set of constraints. The problem falls in the category of  the NP-Complete problems  and is usually tackled using heuristic methods. In this paper we describe a solution algorithm and its implementation based on the graph heuristics and the evolutionary meta-heuristic called scatter search which operates on a set of solutions by combining two or more elements. New solutions are improved before replacing others according to their quality and diversity. The implementation of the algorithm has been experimented on the popular carter’s benchmarks and compared with the best recent results. 

Keywords: Examination timetabling, scatter search, evolutionary, meta-heuristic, graph heuristics.

Received December 4, 2006; accepted May 3, 2007