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.
