Comparing Two-Phase Hybrid Metaheuristics for the University Course Timetabling Problem (UCTP)

Sammanfattning: Timetabling is a time consuming and difficult task for large organizations. One popular research field is the university course timetabling problem (UCTP). UCTP is the NP-hard combinatorial problem of scheduling courses at a university while satisfying some constraints. In most definitions of the UCTP, there are hard constraints that defines what a valid timetable is and there are soft constraints that are only desired features of the timetable. In this research, a few different hybrid methods for solving the UCTP are tested and compared. The hybrids tested are combinations of the metaheuristics simulated annealing, tabu search and iterated local search. The approach is to first use one of these methods to find a valid timetable that is not breaking any hard constraint. Then, a second phase begins that is attempting to minimize the soft constraint violations. The results showed that simulated annealing was the fastest method for removing all hard constraint violations. Given a partial solution solved by simulated annealing, iterated local search was found to minimize soft constraint violations most successfully within the time limit for all tested sizes of problem instances. It was found that this hybrid in two phases could give better solutions than only using simulated annealing.