Three-phase approach for curriculum-based course timetabling problem. (c2012)

Abstract

University course timetabling is an important problem for scheduling courses into predefined periods and rooms over a week with a given set of constraints. This problem is NP-complete and, thus, heuristics are required to produce good suboptimal timetables. This work considers the curriculum based course timetabling problem (CCTP) and proposes three-phase heuristics algorithm that fulfils the requirements of zero hard constraints values and minimal values for soft constraints. The three algorithms are simulated annealing (SA), scatter search (SS) and a tuning heuristic (THEU). We have run our algorithm on subject problems listed at the international timetabling competition in 2007 (ITC2007) and we have compared our results with those of the winner of ITC2007, which is Muller’s hybrid algorithm. Our results show that our approach produces better results than Muller’s for larger or more complex problems.