A Comparative Study between Genetic Algorithm, Simulated Annealing and a Hybrid Algorithm for solving a University Course Timetabling Problem

Sammanfattning: Every year, universities are faced with the problem of having to schedule events to various resources such as lecturers, classrooms and time slots while considering different constraints. The University Course Timetabling Problem is a NP-complete combinatorial optimization problem that, if solved manually, requires great investment in time and money. Thus finding an algorithm that automates this process would prove beneficial for society. The aim of this thesis is to compare the performance of a Genetic Algorithm-Simulated Annealing hybrid implementation with the performance of each of the algorithms individually for solving the University Course Timetabling Problem. The data sets used were inspired by the Royal Institute of Technology in Stockholm. The results showed that Simulated Annealing performed better than the other two algorithms, with respect to time consumption. However, the hybrid algorithm showed great promise of actually producing a feasible solution before terminating as the complexity of the problem increased, for example in the biggest data set tested.