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.
