Benchmarking a standard genetic algorithm for real-world university class timetabling
TL;DR
It could be demonstrated that despite being extremely simple, classical SGA produces valid solutions for this problem but is quite sensitive to changes in population size.
Abstract
The university class timetabling is known to be a classic example of a problem in combinatorial optimization, where an allocation of classes to time periods, classrooms, and tutors is needed. Although modern works mostly concentrate on designing various hybrid or specialized algorithms and metaheuristics, one should also examine the performance of the original algorithm to obtain a baseline metric for future comparisons. This paper considers a simple application of the unaltered SGA on Dataset A that has 38 subjects, 8 tutors, 8 classrooms, five days of operation, and two types of classes (theoretical and practical). As far as scalability was concerned, we have tested several population sizes for the algorithm, namely 15, 30, 60, and 120. Performance metrics such as fitness and the rate of convergence were measured according to the value of the fitness function and runtime as well as memory usage. It could be demonstrated that despite being extremely simple, classical SGA produces valid solutions for this problem but is quite sensitive to changes in population size. To make the analysis more robust, the paper also includes a very basic comparison experiment involving Simulated Annealing as another basis of evaluation.