Gradual Optimization of University Course Scheduling Problem Using Genetic Algorithm and Dynamic Programming

Abstract

The university course scheduling problem (UCSP) is a challenging combinatorial optimization problem that requires optimization of the quality of the schedule and resource utilization while meeting multiple constraints involving courses, teachers, students, and classrooms. Although various algorithms have been applied to solve the UCSP, most of the existing methods are limited to scheduling independent courses, neglecting the impact of joint courses on the overall scheduling results. To address this limitation, this paper proposed an innovative mixed-integer linear programming model capable of handling the complex constraints of both joint and independent courses simultaneously. To improve the computational efficiency and solution quality, a hybrid method combining a genetic algorithm and dynamic programming, named POGA-DP, was designed. Compared to the traditional algorithms, POGA-DP introduced exchange operations based on a judgment mechanism and mutation operations with a forced repair mechanism to effectively avoid local optima. Additionally, by incorporating a greedy algorithm for classroom allocation, the utilization of classroom resources was further enhanced. To verify the performance of the new method, this study not only tested it on real UCSP instances at Beijing Forestry University but also conducted comparative experiments with several classic algorithms, including a traditional GA, Ant Colony Optimization (ACO), the Producer–Scrounger Method (PSM), and particle swarm optimization (PSO). The results showed that POGA-DP improved the scheduling quality by 46.99% compared to that of the traditional GA and reduced classroom usage by up to 29.27%. Furthermore, POGA-DP increased the classroom utilization by 0.989% compared to that with the traditional GA and demonstrated an outstanding performance in solving joint course scheduling problems. This study also analyzed the stability of the scheduling results, revealing that POGA-DP maintained a high level of consistency in scheduling across adjacent weeks, proving its feasibility and stability in practical applications. In conclusion, POGA-DP outperformed the existing algorithms in the UCSP, making it particularly suitable for efficient scheduling under complex constraints.