Applying genetic algorithms and heuristic search to automate course timetabling for The University of Dodoma
Loading...
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The University of Dodoma
Abstract
In this study, a Genetic Algorithm approach coupled with an internal Heuristic Search strategy is applied to attempt automation of course-teaching timetable generation for the University of Dodoma while trying to make the solution as general as possible. In designing the algorithm, course timetabling constraints of the institution are identified and a general encoding scheme is used to represent the problem. Then, a Genetic Algorithm is designed and implemented with a two-point crossover and mutation operators. A value based fitness function and linear ranking selection is used in the algorithm to evolve candidate schedules into a feasible one. To guide the Genetic Algorithm towards obtaining better individuals in the solution population, an internal
Heuristic Search strategy is used during mutation that increases the chance of admissibility of the resulting offspring. A test run of the application that resulted from this study using timetabling data from three colleges of the University of Dodoma showed promising results when compared to the semi-automated Celcat system in-use at the university. The application generated a feasible schedule in a few hours as compared to weeks spent when using Celcat. Also, the number of collisions reported on the Celcat output was dramatically reduced on the output of the developed tool. The model developed though suffers from inability to ensure satisfiability of all soft timetabling constraints. Since such constraints are not critical, all generated schedules from the run tests were considered admissible.
Description
Keywords
Algorithm approach, Internal Heuristic, Heuristic Search, Automation, Timetable generation, Celcat system, Two-point crossover, Mutation operators, Semi-automated
Citation
Baltazary, M. T. (2014). Applying genetic algorithms and heuristic search to automate course timetabling for The University of Dodoma. Dodoma: The University of Dodoma.