Incorporating great deluge approach with kempe chain neighbourhood structure for curriculum-based course timetabling problems

Constructing university course timetable is a very difficult task where a set of events has to be scheduled in timeslots and located in suitable rooms. The objective of course timetabling problem is to satisfy the hard constraints and minimize the violation of soft constraints. In this paper, a hybridization of great deluge algorithm with kempe chain neighbourhood structure is employed. The problem is solved in two steps: a graph-based heuristic is used to construct a feasible timetable in the first step, and the improvement is carried out by employing a hybrid approach in the second step. The approach is tested on the curriculum-based course timetabling problems as described in the 2^nd International Timetabling Competition (ITC2007). We present the result of our technique in relation to the competition results that show the proposed approach is able to produce promising results for the university course timetabling problem.