Impact of dynamic soft constraints on generation of timetables for UCSC postgraduate courses

Abstract

Course timetabling in general is considered a complex, and time-consuming task to be performed manually due to its NP-hard nature. The problem domain can be defined as assignment of events conducted by a set of lecturers into timeslots and rooms subject to a given set of hard and soft constraints. A timetable that satisfies all hard constraints is known as a feasible schedule. Even though the feasibility of a timetable depends on hard constraints, quality relies on soft constraints the system needs to satisfy. Minimizing the number of soft constraint violations increase the quality of the solution as it would satisfy user requirements to a greater extent. This implies that the quality of a timetable can be predicted with the unmet amount of soft constraints and the total number of soft constraints the system includes. But time is not a factor as such that can be foreseen. The amount of time that a system requires to generate a timetable may increase with the number of soft constraints to be met, for there are more conditions to check. Yet in contrast, it might even lead to a lesser time consumption with more constraints because there can be fixed/known allocations as well. Thus in this research an attempt was made to explore the impact of applying soft constraints on generation of timetables. The research involves an implementation of a software solution that incorporates a genetic algorithm. The genetic algorithm was selected for the implementation due to its evolving and global optimization nature. According to results generated by the system, there was no direct impact found on performance when trying to satisfy soft constraints, and the executions depended solely on hard constraints. Furthermore it was found that the size of initial population can make a great impact on the performance of genetic algorithm. Results showed that setting a higher amount of chromosomes as the initial population could minimize the number of generations to be evolved to find a solution, and also it could prevent premature convergence up to some extent.