Meta-Heuristic Approach for Course Scheduling Problem

Nowadays, much research is being carried out to find efficient algorithms for optimal automated university course timetable problems (UCTP). UCTP allocates the university\u27s events like lectures, exams to the various resources, including instructors, students, lecture time and classrooms. Class scheduling is one of the biggest challenging problems of educational institutions. In this thesis, the aim is to improve the state-of-art for a class scheduling problem considering some hard and soft constraints. Hard constraints must be satisfied. Soft constraints need not be satisfied, but there is a penalty for each soft constraint violation. We also have a timing penalty for scheduling each class to a specific schedule. The goal is to allocate classes to their schedule so that the total penalty is minimized. The proposed method adopts the meta-heuristic strategy to improve existing solutions. An acceptance criterion is defined on neighbouring solutions with cooling and an energy function to avoid getting stuck at a local optimum. This criterion extends the same in Simulated Annealing (SA) by giving infeasible neighbours a chance to become candidates. We then compared our proposed models for the feasible and infeasible solution on two different datasets based on iteration vs. penalty with the local search algorithm. The results obtained based on our experiment show that the proposed model for a feasible solution outperformed the local search algorithm by about 20% in 20k iterations on average. While the model for the infeasible solution performed about 52% better than the local search algorithm for the 20k iterations on average. However, both of the proposed models take more execution time compared to the local search algorithm