Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

Taylor, Lisa Ann 2013. Local search methods for the post enrolment-based course timetabling problem. MPhil Thesis, Cardiff University.
Item availability restricted.

[thumbnail of 2013TaylorLAMPhil.pdf]
PDF - Accepted Post-Print Version
Download (1MB) | Preview
[thumbnail of TaylorLA.pdf] PDF - Supplemental Material
Restricted to Repository staff only

Download (81kB)


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.

Item Type: Thesis (MPhil)
Status: Unpublished
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Date of First Compliant Deposit: 30 March 2016
Last Modified: 19 Mar 2016 23:38

Citation Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics