MSc Thesis Defense Announcement of Amanta Sunny:"Meta-Heuristic Approaches to Course Scheduling "

 

Date: Tuesday August 31st, 2021 

Time: 1:00PM – 3:00PM   

Meeting URL: https://us06web.zoom.us/j/88913205208?from=addon 

Passcode: If interested in attending this event, contact the Graduate Secretary at csgradinfo@uwindsor.ca with suffient notice before the event to obtain the passcode.

 

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, etc., to the various resources, including instructors, students, lecture time, classrooms, etc. Class scheduling is one of the biggest challenging problems of educational institutions. In this thesis, the aim is to have a near-optimal solution 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 neighboring solutions with a cooling and an energy function in order to avoid getting stuck at a local optimum. This criterion extends the same used in Simulated Annealing (SA) by giving infeasible neighbors 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 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 model take more execution time compared to the local search algorithm. 

 

Keywords: Meta-heuristic, Simulated annealing, Random walk, optimization  

 

Internal Reader: Dr. Dima Alhadidi            

External Reader: Dr. Xiaolei Guo                

Advisor: Dr. Jessica Chen 

Chair: Dr. Kalyani Selvarajah