Date of Award

Fall 2021

Publication Type

Thesis

Degree Name

M.A.Sc.

Department

Computer Science

Keywords

Metaheuristic algorithm, Optimal automated university course timetable, Class scheduling, Timing penalty

Supervisor

J. Chen

Supervisor

D. Alhadidi

Rights

info:eu-repo/semantics/openAccess

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Abstract

Nowadays, much research is being carried out to find efficient algorithms for optimal automated university course timetable problems (UCTP). UCTP allocates the university's 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.

Download

Share

COinS