{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T16:02:22Z","timestamp":1783526542307,"version":"3.55.0"},"reference-count":43,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T00:00:00Z","timestamp":1741564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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\u2013Scrounger 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.<\/jats:p>","DOI":"10.3390\/a18030158","type":"journal-article","created":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T08:46:41Z","timestamp":1741596401000},"page":"158","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Gradual Optimization of University Course Scheduling Problem Using Genetic Algorithm and Dynamic Programming"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-1217-3530","authenticated-orcid":false,"given":"Xu","family":"Han","sequence":"first","affiliation":[{"name":"School of Technology, Beijing Forestry University, Beijing 100083, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4447-3822","authenticated-orcid":false,"given":"Dian","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Technology, Beijing Forestry University, Beijing 100083, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2025,3,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"107855","DOI":"10.1016\/j.cie.2021.107855","article-title":"A mathematical modeling approach to university course planning","volume":"168","author":"Khamechian","year":"2022","journal-title":"Comput. Ind. Eng."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1137\/1024022","article-title":"Computers and intractability: A guide to the theory of np-completeness (michael r. garey and david s. johnson)","volume":"24","author":"Hartmanis","year":"1982","journal-title":"Siam Rev."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0957-4174(03)00004-6","article-title":"Using genetic algorithm methods to solve course scheduling problems","volume":"25","author":"Wang","year":"2003","journal-title":"Expert Syst. Appl."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1016\/j.ejor.2023.11.024","article-title":"Exact and heuristic algorithms for minimizing the makespan on a single machine scheduling problem with sequence-dependent setup times and release dates","volume":"315","author":"Morais","year":"2024","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"101977","DOI":"10.1016\/j.aei.2023.101977","article-title":"Parallel hyper heuristic algorithm based on reinforcement learning for the corridor allocation problem and parallel row ordering problem","volume":"56","author":"Liu","year":"2023","journal-title":"Adv. Eng. Inform."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"105359","DOI":"10.1016\/j.autcon.2024.105359","article-title":"Customized particle swarm optimization for harmonizing multi-section construction projects","volume":"162","author":"Tomczak","year":"2024","journal-title":"Autom. Constr."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1140","DOI":"10.1016\/j.ejor.2022.09.006","article-title":"A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources","volume":"306","author":"Fontes","year":"2023","journal-title":"Eur. J. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1016\/j.asoc.2018.07.008","article-title":"Dynamic resource allocation for parking lot electric vehicle recharging using heuristic fuzzy particle swarm optimization algorithm","volume":"71","author":"Wu","year":"2018","journal-title":"Appl. Soft Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"106511","DOI":"10.1016\/j.cor.2023.106511","article-title":"Solving an Unrelated Parallel Machines Scheduling Problem with machine-and job-dependent setups and precedence constraints considering Support Machines","volume":"163","year":"2024","journal-title":"Comput. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.cor.2015.07.002","article-title":"Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem","volume":"65","author":"Bellio","year":"2016","journal-title":"Comput. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.ejor.2021.03.069","article-title":"Multiobjective optimization for complex flexible job-shop scheduling problems","volume":"296","author":"Tamssaouet","year":"2022","journal-title":"Eur. J. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"117251","DOI":"10.1016\/j.eswa.2022.117251","article-title":"A diversity preservation method for expensive multi-objective combinatorial optimization problems using Novel-First Tabu Search and MOEA\/D","volume":"202","author":"Coelho","year":"2022","journal-title":"Expert Syst. Appl."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"116953","DOI":"10.1016\/j.eswa.2022.116953","article-title":"A new tool for automated transformation of quadratic assignment problem instances to quadratic unconstrained binary optimisation models","volume":"201","author":"Tosun","year":"2022","journal-title":"Expert Syst. Appl."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/j.ejor.2008.12.007","article-title":"Adaptive tabu search for course timetabling","volume":"200","author":"Hao","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1219","DOI":"10.1016\/j.ejor.2022.08.001","article-title":"Modelling and heuristically solving many-to-many heterogeneous vehicle routing problem with cross-docking and two-dimensional loading constraints","volume":"306","author":"Ji","year":"2023","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.eswa.2019.02.026","article-title":"Optimization of university course scheduling problem using particle swarm optimization with selective search","volume":"127","author":"Hossain","year":"2019","journal-title":"Expert Syst. Appl."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/j.eswa.2010.06.051","article-title":"A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences","volume":"38","author":"Shiau","year":"2011","journal-title":"Expert Syst. Appl."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Ayob, M., and Jaradat, G. (2009, January 27\u201328). Hybrid ant colony systems for course timetabling problems. Proceedings of the 2009 2nd Conference on Data Mining and Optimization, Selangor, Malaysia.","DOI":"10.1109\/DMO.2009.5341898"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Hiryanto, L. (2013, January 25\u201328). Incorporating dynamic constraint matching into vertex-based graph coloring approach for university course timetabling problem. Proceedings of the 2013 International Conference on QiR, Yogyakarta, Indonesia.","DOI":"10.1109\/QiR.2013.6632539"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"110263","DOI":"10.1016\/j.cie.2024.110263","article-title":"An improved genetic algorithm based on reinforcement learning for aircraft assembly scheduling problem","volume":"193","author":"Wen","year":"2024","journal-title":"Comput. Ind. Eng."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"116464","DOI":"10.1016\/j.eswa.2021.116464","article-title":"A novel genetic algorithm based system for the scheduling of medical treatments","volume":"195","author":"Squires","year":"2022","journal-title":"Expert Syst. Appl."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"123383","DOI":"10.1016\/j.eswa.2024.123383","article-title":"Exact and heuristic methods for a university course scheduling problem","volume":"248","author":"Xiang","year":"2024","journal-title":"Expert Syst. Appl."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1153","DOI":"10.1016\/j.ejor.2015.08.057","article-title":"A MILP model for the teacher assignment problem considering teachers\u2019 preferences","volume":"249","author":"Domenech","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1016\/j.ejor.2021.10.014","article-title":"The multiphase course timetabling problem","volume":"300","author":"Esmaeilbeigi","year":"2022","journal-title":"Eur. J. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"109916","DOI":"10.1016\/j.cie.2024.109916","article-title":"Network configuration distributed production scheduling problem: A constraint programming approach","volume":"188","author":"Ziadlou","year":"2024","journal-title":"Comput. Ind. Eng."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"106347","DOI":"10.1016\/j.cie.2020.106347","article-title":"Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem","volume":"142","author":"Meng","year":"2020","journal-title":"Comput. Ind. Eng."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"884","DOI":"10.1016\/j.ejor.2020.02.021","article-title":"Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel","volume":"285","author":"Qin","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"103561","DOI":"10.1016\/j.artint.2021.103561","article-title":"The complexity landscape of decompositional parameters for ILP: Programs with few global variables and constraints","volume":"300","author":"Eiben","year":"2021","journal-title":"Artif. Intell."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.ejor.2024.06.036","article-title":"Mixed-integer linear programming for project scheduling under various resource constraints","volume":"319","author":"Klein","year":"2024","journal-title":"Eur. J. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"115967","DOI":"10.1016\/j.eswa.2021.115967","article-title":"Integer linear programming for the tutor allocation problem: A practical case in a British university","volume":"187","author":"Caselli","year":"2022","journal-title":"Expert Syst. Appl."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"109561","DOI":"10.1016\/j.cie.2023.109561","article-title":"The university coursework timetabling problem: An optimization approach to synchronizing course calendars","volume":"184","author":"Mallari","year":"2023","journal-title":"Comput. Ind. Eng."},{"key":"ref_32","first-page":"29","article-title":"Producer-Scrounger Method to Solve Traveling Salesman Problem","volume":"7","author":"Akhand","year":"2015","journal-title":"Int. J. Intell. Syst. Appl."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0377-2217(03)00103-6","article-title":"An integer programming formulation for a case study in university timetabling","volume":"153","author":"Daskalaki","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"113732","DOI":"10.1016\/j.eswa.2020.113732","article-title":"Performance improvement strategies on Cuckoo Search algorithms for solving the university course timetabling problem","volume":"161","author":"Thepphakorn","year":"2020","journal-title":"Expert Syst. Appl."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.cor.2017.09.007","article-title":"A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem","volume":"90","author":"Akkan","year":"2018","journal-title":"Comput. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.jom.2004.07.006","article-title":"Using information on unconstrained student demand to improve university course schedules","volume":"23","author":"Thompson","year":"2005","journal-title":"J. Oper. Manag."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/j.ins.2020.06.036","article-title":"A hybrid method integrating an elite genetic algorithm with tabu search for the quadratic assignment problem","volume":"539","author":"Zhang","year":"2020","journal-title":"Inf. Sci."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"118068","DOI":"10.1016\/j.eswa.2022.118068","article-title":"Adaptive genetic algorithm for two-stage hybrid flow-shop scheduling with sequence-independent setup time and no-interruption requirement","volume":"208","author":"Qiao","year":"2022","journal-title":"Expert Syst. Appl."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"114198","DOI":"10.1016\/j.eswa.2020.114198","article-title":"New hybrid genetic algorithms to solve dynamic berth allocation problem","volume":"167","author":"Bacalhau","year":"2021","journal-title":"Expert Syst. Appl."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/j.ins.2020.03.032","article-title":"Multi-objective feature selection using hybridization of a genetic algorithm and direct multisearch for key quality characteristic selection","volume":"523","author":"Li","year":"2020","journal-title":"Inf. Sci."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1016\/j.ejor.2017.07.027","article-title":"An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case","volume":"265","author":"Kadri","year":"2018","journal-title":"Eur. J. Oper. Res."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/ICA-170546","article-title":"Hybrid firefly-linde-buzo-gray algorithm for Channel-Optimized Vector Quantization codebook design","volume":"24","author":"Ferreira","year":"2017","journal-title":"Integr. Comput. Aided Eng."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"385","DOI":"10.3233\/ICA-170550","article-title":"Multilayer embedded bat algorithm for B-spline curve reconstruction","volume":"24","author":"Iglesias","year":"2017","journal-title":"Integr. Comput.-Aided Eng."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/3\/158\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:50:05Z","timestamp":1760028605000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/3\/158"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,10]]},"references-count":43,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2025,3]]}},"alternative-id":["a18030158"],"URL":"https:\/\/doi.org\/10.3390\/a18030158","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,10]]}}}