Gradual Optimization of University Course Scheduling Problem Using Genetic Algorithm and Dynamic Programming
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-03-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/3/158 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850204891333525504 |
|---|---|
| author | Xu Han Dian Wang |
| author_facet | Xu Han Dian Wang |
| author_sort | Xu Han |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-c88ec94fc72b4de8b038cf6669f054d5 |
| institution | OA Journals |
| issn | 1999-4893 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj-art-c88ec94fc72b4de8b038cf6669f054d52025-08-20T02:11:12ZengMDPI AGAlgorithms1999-48932025-03-0118315810.3390/a18030158Gradual Optimization of University Course Scheduling Problem Using Genetic Algorithm and Dynamic ProgrammingXu Han0Dian Wang1School of Technology, Beijing Forestry University, Beijing 100083, ChinaSchool of Technology, Beijing Forestry University, Beijing 100083, ChinaThe 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.https://www.mdpi.com/1999-4893/18/3/158genetic algorithmsuniversity course scheduling problemdynamic programmingjudgment mechanismforced mutation operation |
| spellingShingle | Xu Han Dian Wang Gradual Optimization of University Course Scheduling Problem Using Genetic Algorithm and Dynamic Programming Algorithms genetic algorithms university course scheduling problem dynamic programming judgment mechanism forced mutation operation |
| title | Gradual Optimization of University Course Scheduling Problem Using Genetic Algorithm and Dynamic Programming |
| title_full | Gradual Optimization of University Course Scheduling Problem Using Genetic Algorithm and Dynamic Programming |
| title_fullStr | Gradual Optimization of University Course Scheduling Problem Using Genetic Algorithm and Dynamic Programming |
| title_full_unstemmed | Gradual Optimization of University Course Scheduling Problem Using Genetic Algorithm and Dynamic Programming |
| title_short | Gradual Optimization of University Course Scheduling Problem Using Genetic Algorithm and Dynamic Programming |
| title_sort | gradual optimization of university course scheduling problem using genetic algorithm and dynamic programming |
| topic | genetic algorithms university course scheduling problem dynamic programming judgment mechanism forced mutation operation |
| url | https://www.mdpi.com/1999-4893/18/3/158 |
| work_keys_str_mv | AT xuhan gradualoptimizationofuniversitycourseschedulingproblemusinggeneticalgorithmanddynamicprogramming AT dianwang gradualoptimizationofuniversitycourseschedulingproblemusinggeneticalgorithmanddynamicprogramming |