Date of Award
Column generation, Decision variables, Greedy strategy, Integer linear programming
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
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-coloring. 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
Zaidi, Rida, "Efficient Heuristic Solutions to Scheduling Online Courses" (2021). Electronic Theses and Dissertations. 8828.