Automatic Generation of University Course Timetabling Using Genetic Algorithm

University Course Timetabling Problem (UCTP) is a well-known Constraint Satisfaction Problem (CSP) problem that has exponential number of solutions based on course conflicts, teacher’s empty times and other parameters. This is a NP-Hard problem. Scheduling is a major debate on planning which can be used in trains scheduling, classroom scheduling, traffic even in schools and universities. The Scheduling leads to organizing tasks and removing tasks interference which is important. The goal of solving UCTP is setting times for courses and teachers in weekdays in order to reach minimum courses conflicts. It is also ideal for teachers to have joint days for teaching in the least weekdays. Of course, subject to the restrictions of classes and teachers program this scheduling is very difficult. Generally, Evolutionary Algorithms (EA) are efficient tools to solve this problem. The final timetabling must be optimum which means that there is no conflicts if possible and best scheduling generate for teachers. In this paper we solve this problem based on genetic algorithm and implement this algorithm with DEAP python based toolbox on random dataset. The implementation results show that genetic algorithm is efficient tools that can close to the global optimum point.

Keywords:

Constraint Satisfaction Problem , Genetic Algorithm , Optimization , University Course Timetabling Problem