Date of Award

Summer 2021

Publication Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Column generation, Decision variables, Greedy strategy, Integer linear programming

Supervisor

J. Chen

Supervisor

D. Wu

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

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

Download

Share

COinS