A multi-neighbourhood local search algorithm for the university course timetabling problem

Abstract

The University Course Timetabling Problem (UCTP) is an example of a real-world educational timetabling problem that deals with the allocation of a set of courses and lecturers to a set of rooms and timeslots subject to certain restrictions. The objective and constraints of the problem will vary according to the specific requirements of different institutions. The construction of course timetables is a challenging and time consuming task and, in fact, the UCTP is classified as an NP-Hard optimization problem. In this dissertation, we tackle a UCTP relating to real life data obtained from the Faculty of Science at the University of Malta. An original mathematical model is formulated specifically for this data and different problem instances are solved. Since the UCTP is an NP-Hard optimization problem, exact methods will take an exponentially longer time to converge to a globally optimal solution as the size of the problem increases. As a result, heuristic solution methods are a common alternative since they provide practical solutions in a timely manner. Both the Branch and Cut (B&C) exact method and a heuristic algorithm are applied to our problem and compared. The heuristic algorithm consists of two phases; an initial feasible solution construction phase, in which a greedy algorithm is used, and a solution quality improvement phase, in which Multi-Neighbourhood Local Search (MNLS) is performed. The results show that for small instances, the proposed MNLS algorithm can be considered a good alternative to B&C. For larger instances, it sill finds relatively good solutions but running time increases significantly.