A modified evolutionary algorithm approach to course timetabling : a case study of JKUAT IT centre

Abstract

The timetabling problem is concerned with the allocation, subject to constraints, of given resources to objects in space and time in such way as to satisfy as nearly as possible a set of desirable objectives. This problem is known to be NP-complete and as such only combinatorial optimization methods can guarantee an optimal timetable. Of the many methods that have been applied to solving the problem automatically, evolutionary techniques have shown much promise due to their general purpose optimization capabilities. An evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based meta-heuristic optimization algorithm. However, it has also been found that modified evolutionary methods can yield even better results. This paper presents such a modified approach in the form of an evolutionary algorithm that does not use the normal mutator, crossover, inversion, migration operators but uses modified natural selection. The major purpose of this study was to investigate the use of modified evolutionary algorithms in solving the timetable problem at the JKUAT IT CENTRE. The study also aimed at finding out the need for an automated system within the JKUAT IT CENTRE and a few other control departments. A modified evolutionary algorithm was developed and successfully applied in a timetabling system that was used to timetable units within the JKUA T IT CENTRE and managed to schedule lectures without causing conflicts.