Scalability of a Genetic Algorithm that solves a UniversityCourse Scheduling Problem Inspired by KTH

Abstract: Scheduling university courses is a combinatorial optimization problem where a set of events such as lectures, seminars and labs have to be scheduled into certain time slots while taking various constraints into account. The problem is considered dicult by conventional methods andthe amount of required computations usually increases exponentially with the size of the problem. However, for universities such as KTH, Royal Institute of Technology in Stockholm, this is a task that has to be dealt with regardless of its complexity. In this report, Genetic Algorithms (GAs) were applied to solve the course scheduling problem for multiple data samples inspired by KTH. The sizes of the input data were carefully designed to study the scalability of the GA. The results indicate on an exponential growth of the running time measured not in actual time but number of iterations. The scalability is highly dependent on the denition of a high quality solution as well as algorithm parameters but also      dierent methods being used in the GA.Keywords - Scheduling, Timetabling, KTH, Royal Institute of Technol-ogy, Scalability, Genetic Algorithm, GA, Constraints, Fitness, Selection,Crossover, Mutation, Repair, Extinction, Generation