Time-Predefined and Trajectory-Based Search: Single and Multiobjective Approaches to Exam Timetabling


The research work presented in this thesis aims to provide effective methods for solving university exam timetabling problems. The goal is to automatically produce high quality timetables which are easy and practical to use. Several ideas are introduced, which could increase the overall performance of timetabling algorithms. The primary idea is to employ parameters which are clearly understandable for the user and which therefore make the timetabling procedure more transparent. The second idea is to consider the expected processing time as one such parameter, which allows the user to increase the quality of final solutions by the efficient management of computational resources. In addition to this, special attention is paid to the development of multiobjective approaches, which can help the user to manage a high variety of constraints (which are of different nature) and simultaneously, generate a solution, which mostly suits his/her preferences. The author also introduces the idea of a trajectory-based multiobjective approach which enables the search process to move along defined trajectories. A number of different strategies for the application of trajectory- based search are proposed, which can enable the easy expression of user preferences. In this thesis, five new exam timetabling algorithms are presented (2 single-objective and 3 multiobjective ones) which (in different ways) incorporate the ideas that are outlined above. A comprehensive series of experiments demonstrate the effectiveness of the proposed techniques. In most cases the presented approaches significantly outperform other techniques on established benchmark exam timetabling problems.