A Genetic Algorithm for University Timetabling

Abstract

Timetabling is the process of allocating time for planned activities orderly, to bring an optimum solution, without violating any hard constraints and with minimum soft constraint violations. It portrays a difficult optimization problem. There exist many commercial software with general features for this task. However, those cannot be adopted into The Open University of Sri Lanka (OUSL) due to its unique and complex requirements. This work presents the development of a genetic algorithm (GA) based MATLAB program, which automatically generates a semester-long, optimized timetable and eliminates the current, time consuming, manual process. The algorithm takes into account the number of levels in a degree program, credit hours, days and time slots in a semester, clash avoidance, fixed time slots, holidays, lecturer preferences, and workload distributions. The genetic algorithm consists of four main steps: initialization, validation, fitness calculation, and mutation. The solution space is represented by a four-dimensional matrix. Rows, columns, and planes represented slots per day, days in a semester, and levels (year 01,02 and 03 of degree program). The fourth dimension represents different solutions. To measure the performance of the algorithm, a point system was devised where violation of each constraint was penalized and vice versa. Based on this point system, a theoretical maximum was calculated without considering the feasibility of achieving all constraints simultaneously. In this study, the algorithm reached a maximum fitness value of 100 without violating any hard constraints, whereas the theoretical maximum was 126. Repair strategies were implemented to improve the performance resulting in reduction of execution time from 90 minutes to 14 minutes. The results show it is possible to generate an optimized timetable consistently using this method.