Local search methods for the post enrolment-based course timetabling problem

The work presented in this thesis concerns the problem of post enrolment-based course time-tabling. The motivation for this is the increasing importance of the automation of timetabling due to the growth in popularity of Higher Education in recent years. There were 464,910 accepted applicants to universities in the United Kingdom in 2012 which is a 12% rise in five years. This will inevitably lead to an expansion in the number of courses, modules and teachers. As a result, the ability to manually construct timetables has become increasingly impractical. A two-stage approach is investigated that aims to use heuristic and metaheuristic approaches to obtain a satisfactory timetable that suits the needs of the staff and students at educational institutions. The first stage consists of using selection heuristics to construct an initial solution. Two approaches that then attempt to find feasibility are presented. The first applies a tabu search algorithm with a number of neighbourhood operators that navigate the search space for feasible solutions. The second approach implements a PartialCol algorithm. The second stage aims to improve the solution quality by minimising the number of soft constraint violations. The feasibility ratio could be an indicator of the connectivity of the search space, so methods of increasing the feasibility ratio are presented. If the feasibility ratio can be increased then the number of soft constraint violations would be expected to decrease. These techniques were applied to the 24 instances provided for track two of the International Timetabling Competition 2007. The conclusions of the experimentation and investigative processes show that the PartialCol algorithm was more successful, in terms of finding feasible solutions, than the method that employs the neighbourhood operators. However, improvements to the soft constraint penalty were achieved using these neighbourhood operators