Genetic Algorithm Analysis using the Graph Coloring Method for Solving the University Timetable Problem

摘要

The Timetable Problem is one of the complex problems faced in any university in the world. It is a highly-constrained combinatorial problem that seeks to find a possible scheduling for the university course offerings. There are many algorithms and approaches adopted to solve this problem, but one of the effective approaches to solve it is the use of meta-heuristics. Genetic algorithms were successfully useful to solve many optimization problems including the university Timetable Problem. In this paper, we analyse the Genetic Algorithm approach for graph colouring corresponding to the timetable problem. The GA method is implemented in java, and the improvement of the initial solution is exhibited by the results of the experiments based on the specified constraints and requirements.