An Evaluation of the Great Deluge Algorithm in Course Timetabling : As Applied to the KTH-Inspired University Course Timetabling Problem

Sammanfattning: The University Course Timetabling Problem (UCTP) can be loosely described as assigning events (e.g lectures) to rooms and timeslots in a way that results in a feasible timetable that is optimal according to some custom criteria. The problem has become increasingly relevant as more programs become available in universities. Due to the complexity of UCTP, the problem is usually solved approximately using heuristics. The KTH-inspired UCTP is a variant of the UCTP that is adapted to KTH Royal Institute of Technology. However, few heuristics have been implemented for this variant of UCTP. Therefore, this study introduces an implementation of The Great Deluge heuristic to the KTH-inspired UCTP, and compares it to a state-of-the-art solver for KTH-inspired UCTP. The Great Deluge implementation was compared against the state-of-the-art KTH-inspired UCTP solver for different time limits. For each time limit, the output timetable quality was recorded over several executions. The comparison was done on two problem instances of varying complexity. The results suggest a behavior that varies over time. For larger time limits, GD produced better timetables than the state-of-the-art and the overall quality of timetables was consistent over several executions. For smaller time limits, GD produced worse timetables than the state-of-the-art and the overall quality of timetables was inconsistent over several executions. A few potential causes for the improved performance during the later stages of execution were found through further analysis of the results. Perhaps the biggest potential cause was utilizing the greedy behavior obtained during the mid to late stages of execution.