A practical investigation of examination timetabling
LE3 .A278 2015
Bachelor of Computer Science
There exist problems for which there are no known polynomial time algorithms. These problems are of great interest to computer science researchers, yet they also occur in real world tasks. For example, the production of an optimum examination timetable for a university cannot be done in polynomial time with any known algorithm. The university, however, still requires a timetable to be produced. The production of a timetable can be modeled as an optimization problem for which there are many algorithms. These algorithms attempt to produce usable so- lutions in a practical amount of time. Due to the number of these algorithms, the di culty of the initial problem is compounded by the problem of choosing and im- plementing an algorithm. In this thesis, we build a system to produce examination timetables for a university by implementing and evaluating a number of previously published algorithms. From this experience, we compare the practicality of the algorithms. Additionally, we provide observations to aid others in the production of practical optimization systems. Finally, we present the results of our system compared to Acadia's current system as well as recommendations for future improvements.
The author grants permission to the University Librarian at Acadia University to reproduce, loan or distribute copies of my thesis in microform, paper or electronic formats on a non-profit basis. The author retains the copyright of the thesis.