A GPU based genetic algorithm solution for the timetabling problem

Abstract

The university course timetabling problem (UCTP) is a combinatorial optimization problem of great importance for every university. This paper proposes the use of a parallel evolutionary algorithm to solve the problem and focuses on accelerating the process for specifically very large sized problems. The problem was solved using the genetic algorithm, and accelerated with the use of the Graphics Processing Units (GPUs) capabilities in order to use very large population sizes and explore the problem solution space in a much exhaustive manner. The genetic algorithm was also enhanced with the use of local search, and allowed to deal flexibly with the incremental changes of the problem's constraints while maintaining the resulting solution with minimal changes. The implementation of the proposed work was tested with the ITC2007 datasets as the benchmark set.