UWindsor Together: Student Mental Health and Remote Learning Services

MSc Thesis Defense Announcement of Rida Zaidi "Efficient Heuristic Solutions to Scheduling Online Courses "

Monday, May 10, 2021 - 13:00 to 15:00


The School of Computer Science is pleased to present… 

MSc Thesis Defense by: Rida Zaidi 

Date: Monday May 10th, 2021 
Time:  1:00 pm – 3:00 pm 
Passcode: If interested in attending this event, contact the Graduate Secretary at csgradinfo@uwindsor.ca


The demand for efficient algorithms to automate (near-)optimal timetables has motivated many well-studied scheduling problems in operational research. With most of the courses moving online during the recent pandemic, the delivery of quality education has raised many new technical issues, including online course scheduling. This thesis considers the problem of yielding a near-optimal schedule of the real-time courses in an educational institute, taking into account the conflict among courses, the constraint on the simultaneous consumption of the bandwidth at the hosting servers of the courses, and the maximum utilization of the prime time for the lectures. We propose three approaches for solving the online course scheduling problem; Integer Linear Programming technique, Construction Heuristic using Graph Coloring, and a Hybrid approach using Column Generation technique in combination with Dynamic Programming, and K-colouring. The column generation technique is adopted along with the ILP approach to handling the exponentially increasing number of decision variables in the set-covering problem formulation. This empirical study demonstrates the impact of the input parameters on each approach's efficiency, including internet bandwidth, number of conflicts, number of connected components. Our results prove the Hybrid approach's scalability with the change in input parameters and confirm its efficiency in producing near-optimal schedules in a reasonable time. 
Keywords: Integer Linear Programming, Column Generation, Decision Variables, Greedy Strategy. 

MSc Thesis Committee:  

Internal Reader: Dr. Dan Wu        
External Reader: Dr. Myron Hlynka 
Advisor: Dr. Jessica Chen 
Chair: Dr. Kalyani Selvarajah 

 MSc Thesis Defense Announcement      Vector Institute in Artificial Intelligence approved artificial intelligence topic logo


 5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716 csgradinfo@uwindsor.ca