Peter Eze MSc Dissertation 2014/15

Constructive and Unconstructive  Initialisation of a Genetic Algorithm for Solving a University Timetabling Problem

Supervised by D.Walker

Abstract

The University Timetabling Problem(UTP) is one of the scheduling problems ridden with numerous constraints. Each of these constraints has complex effect on the ideal solution and thus the combined effect makes the problem hard to solve. This is a case for the inadequacies with the current electronic timetabling system in the Department of Computer Science. Thus, it is required that an automated electronic system that could resolve the complex constraints while scheduling course modules be designed and developed.

In order to solve this problem and also develop insight into other timetabling problems, the method of genetic algorithm (GA) was developed and adapted in the forms of constructive and unconstructive initialisation methods. Eight hard constraints and four soft constraints existing in the Department of Computer Science were used in developing the GA. Software was designed and experiments run using 29 lecturers, 33 modules from autumn semester for all taught programmes, 6 laboratory rooms and 19 lecture rooms. The resources and constraints were divided into five levels of difficulty to test the developed algorithm.

The result of the research shows that the constructive method can satisfy all the hard constraints, achieve up to 75% optimisation of the soft constraints and converge within 500 generations or average of 2.74 minutes. The unconstructive method showed good evolutionary tendencies but did not produce a feasible solution within reasonable time. Further results show that the length of time taken to run the GA depends on the fitness function used: reward-based or penalty-based; and thus, on how good the genes in the chromosomes are.

In conclusion, constructively initialised GA is efficient in solving specific UTP while the unconstructively initialised GA could not but can be used to get insight into different timetabling problems before a constructive GA is designed.