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 JKUAT IT
CENTRE and managed to schedule lectures without causing conflicts.