Title: Grasp and Guided Local Search for the examination timetabling problem

Authors: Drifa Hadjidj, Habiba Drias

Addresses: Faculte des Sciences, Departement d'Informatique, Universite M'hamed Bougara, Boumerdes, Avenue de l'independance 35000, Boumerdes, Algerie. ' Faculte Genie Electrique et Informatique, Departement d'Informatique, Universite des Sciences et de la Technologie Houari Boumediene, BP 32, El-AAlia 16111, Babezzouar, Alger, Algerie

Abstract: Examination timetabling is an optimisation problem, which regards the scheduling of a set of exams to a set of contiguous time slots, satisfying a set of constraints. The problem belongs to the class of NP-Complete problems and is usually tackled using heuristic methods. In this paper, we describe a solution algorithm and its implementation which makes use of the good features of a Greedy Randomised Adaptive Search Procedure (GRASP) and the Guided Local Search (GLS) meta-heuristic. The implementation of the algorithm has been experimented on the popular Carter|s benchmarks and compared with the best recent results.

Keywords: examination timetabling; GRASP; GLS; guided local search; metaheuristics; graph heuristics; optimisation; scheduling; greedy randomised adaptive search procedure; exam timetables.

DOI: 10.1504/IJAISC.2010.032515

International Journal of Artificial Intelligence and Soft Computing, 2010 Vol.2 No.1/2, pp.103 - 114

Published online: 04 Apr 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article