Automated University Timetabling with Robustness
Sakal, J
Date: 3 June 2024
Thesis or dissertation
Publisher
University of Exeter
Degree Title
PhD in Computer Science
Abstract
Generating workable timetables for universities is a hard task. For many years, the process was conducted manually, but it has benefited in recent times from greater automation. From graph theoretical and mathematical programming to metaheuristic approximation methods, a multitude of computational approaches have been tried and tested. ...
Generating workable timetables for universities is a hard task. For many years, the process was conducted manually, but it has benefited in recent times from greater automation. From graph theoretical and mathematical programming to metaheuristic approximation methods, a multitude of computational approaches have been tried and tested. In parallel to this, benchmarks of artificial problems have arisen to aid the development of novel algorithms. In this thesis, we focus on nature-inspired search processes as applied to the International Timetabling Competition (ITC) 2007 track 3 benchmark. Firstly, we develop an ant colony optimiser based on the MAX-MIN ant system (MMAS). Consideration is given to the ordering of lecture assignments in the construction graph. We aim to discover how permuting lectures affects overall performance and what features of the problem are important. Through a machine learning phase, a permutation predictor is then devised for unseen instances, which is assessed both with and without local search enhancements. Other aspects of the MMAS as relate to performance and efficiency are also examined, such as dynamic constraint handling and partial function evaluations. Initial results are mixed but show promise for the smaller problems, suggesting that further expansion of the methodology could be worthwhile. Secondly, a many-objective approach to the same problem is explored. Noting that treatments of the ITC2007 are typically single-objective, we instead cast individual constraint violations as distinct objectives. Inspiration is taken from NSGA-III, which is discretised and otherwise adapted for the problem at hand. Working under the assumption that decision maker preferences are not known in advance, we attempt to generate good approximations to the Pareto set, relying on hypervolume as the key performance indicator. We show that feasible solutions can be attained quickly in a constructive phase, and that targeted objectives can be optimised to zero (where possible) in a second phase. Trade-offs between the different objectives are analysed. Scalarised results are compared with published single-objective approaches and found to be competitive on some problems. More importantly, our contribution represents a method of attaining an approximation set of unique non-dominated solutions that has been lacking thus far in the literature. In the final chapter, we build upon the many-objective solver by considering symmetry and redundancy in the search space. An encoding conversion is proposed to eliminate equivalent solutions. We also investigate and visualise the plateaus in the search landscape and propose a genotype diversity mechanism to facilitate the escape from these regions. This leads to a statistically significant improvement in results. Further operators are introduced and we examine the trade-offs between computation time and increased complexity within the perturbation and selection operators. Lastly, we explore the idea of robustness of solutions, developing a method to quantify this property, before adding it to the problem as an additional objective. Our solver copes well with the extra dimension of robustness, offering promising results for future research.
Doctoral Theses
Doctoral College
Item views 0
Full item downloads 0