Elite-Refined Genetic Algorithm with Hill Climbing Local Search for University Course Scheduling
Abstract
Abstract— This paper proposes a hybrid optimization approach combining Genetic Algorithm (GA) and Hill Climbing (HC) to address the university course scheduling problem in the Informatics Study Program at Universitas Islam Negeri Siber Syekh Nurjati Cirebon. The hybrid GA-HC model integrates GA’s global exploration capability with HC's local refinement strategy to minimize hard and soft constraint violations while achieving balanced timetables. The dataset includes 56 course classes, 18 lecturers, and three rooms, with scheduling over five working days and 11 time slots per day. Experimental results demonstrate that GA-HC outperforms pure GA and pure HC in convergence speed, average fitness, and stability of feasible solutions. Parameter tuning analysis further shows that moderate mutation rates and limited HC iterations yield optimal trade-offs between runtime and solution quality. The proposed hybrid framework effectively enhances convergence, reduces conflicts, and improves overall timetable quality, confirming its robustness for large-scale academic scheduling problems.
Downloads
References
L. R. Lattuca and J. S. Stark, Shaping the college curriculum: Academic plans in context. John Wiley & Sons, 2009.
J. S. Tan, S. L. Goh, G. Kendall, and N. R. Sabar, “A survey of the state-of-the-art of optimisation methodologies in school timetabling problems,” Expert Syst Appl, vol. 165, p. 113943, 2021, doi: https://doi.org/10.1016/j.eswa.2020.113943.
K. Song, S. Kim, M. Park, and H.-S. Lee, “Energy efficiency-based course timetabling for university buildings,” Energy, vol. 139, pp. 394–405, 2017, doi: https://doi.org/10.1016/j.energy.2017.07.176.
B. A. Jhonlawi, “Optimizing Educational Scheduling: ACO-Based Lecture Schedule Preparation Application,” International Journal of Enterprise Modelling, vol. 18, no. 2, pp. 52–62, 2024.
M. Lindahl, A. J. Mason, T. Stidsen, and M. Sørensen, “A strategic view of University timetabling,” Eur J Oper Res, vol. 266, no. 1, pp. 35–45, 2018, doi: https://doi.org/10.1016/j.ejor.2017.09.022.
A. Muluk, H. Akpolat, and J. Xu, “Scheduling problems—an overview,” J Syst Sci Syst Eng, vol. 12, no. 4, pp. 481–492, 2003.
M. C. Chen, S. N. Sze, S. L. Goh, N. R. Sabar, and G. Kendall, “A Survey of University Course Timetabling Problem: Perspectives, Trends and Opportunities,” IEEE Access, vol. 9, pp. 106515–106529, 2021, doi: 10.1109/ACCESS.2021.3100613.
A. Gülcü and C. Akkan, “Robust university course timetabling problem subject to single and multiple disruptions,” Eur J Oper Res, vol. 283, no. 2, pp. 630–646, 2020, doi: https://doi.org/10.1016/j.ejor.2019.11.024.
S. and B. A. and E. H. and H. P. and M. K. Aschinger M. and Applebee, “New Constraints and Features for the University Course Timetabling Problem,” in Operations Research Proceedings 2016, A. and G. M. J. Fink Andreas and Fügenschuh, Ed., Cham: Springer International Publishing, 2018, pp. 95–101.
H. Babaei, J. Karimpour, and A. Hadidi, “A survey of approaches for university course timetabling problem,” Comput Ind Eng, vol. 86, pp. 43–59, 2015, doi: https://doi.org/10.1016/j.cie.2014.11.010.
N. and V. J. and L. O. and M. J. and V. M. Silva Jose and Varela, “Comparison of Bioinspired Algorithms Applied to the Timetabling Problem,” in Computational Methods and Data Engineering, V. K. and K. S. and P. R. B. Singh Vijendra and Asari, Ed., Singapore: Springer Singapore, 2021, pp. 427–437.
T. Song, M. Chen, Y. Xu, D. Wang, X. Song, and X. Tang, “Competition-guided multi-neighborhood local search algorithm for the university course timetabling problem,” Appl Soft Comput, vol. 110, p. 107624, 2021, doi: https://doi.org/10.1016/j.asoc.2021.107624.
A. A. Lazarev, “Solution of the NP-hard total tardiness minimization problem in scheduling theory,” Computational Mathematics and Mathematical Physics, vol. 47, no. 6, pp. 1039–1049, 2007.
A. I. Diveev, O. V Bobr, D. E. Kazaryan, and O. Hussein, “Some methods of solving the NP-difficult problem of optimal schedule for the university,” Procedia Comput Sci, vol. 150, pp. 410–415, 2019.
B. Alhijawi and A. Awajan, “Genetic algorithms: Theory, genetic operators, solutions, and applications,” Evol Intell, vol. 17, no. 3, pp. 1245–1256, 2024.
M. A. Albadr, S. Tiun, M. Ayob, and F. Al-Dhief, “Genetic algorithm based on natural selection theory for optimization problems,” Symmetry (Basel), vol. 12, no. 11, p. 1758, 2020.
D. Kristiadi and R. Hartanto, “Genetic Algorithm for lecturing schedule optimization,” IJCCS (Indonesian Journal of Computing and Cybernetics Systems), vol. 13, no. 1, pp. 83–94, 2019.
A. K. Nugroho, I. Permadi, A. R. Yasifa, and others, “Optimizing course scheduling faculty of engineering unsoed using genetic algorithms,” JITK (Jurnal Ilmu Pengetahuan dan Teknologi Komputer), vol. 7, no. 2, pp. 91–98, 2022.
E. A. Abdelhalim and G. A. El Khayat, “A utilization-based genetic algorithm for solving the university timetabling problem (uga),” Alexandria Engineering Journal, vol. 55, no. 2, pp. 1395–1409, 2016.
Y. G. Xu, G. R. Li, and Z. P. Wu, “A novel hybrid genetic algorithm using local optimizer based on heuristic pattern move,” Applied Artificial Intelligence, vol. 15, no. 7, pp. 601–631, 2001.
F. Sabry, Hill Climbing: Fundamentals and Applications, vol. 80. One Billion Knowledgeable, 2023.
K. Sarode and S. R. Javaji, “Hybrid Genetic Algorithm and Hill Climbing Optimization for the Neural Network,” arXiv preprint arXiv:2308.13099, 2023.
J. Almeida, J. R. Figueira, A. P. Francisco, and D. Santos, “A hybrid meta-heuristic for the generation of feasible large-scale course timetables using instance decomposition,” arXiv preprint arXiv:2310.20334, 2023.
A. Rezaeipanah, S. S. Matoori, and G. Ahmadi, “A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search,” Applied Intelligence, vol. 51, no. 1, pp. 467–492, 2021.
A. Hussain, H. Ashas, A. Shahid, S. Qureshi, and S. Karrila, “Hybrid approach involving genetic algorithm and hill climbing to resolve the timetable scheduling for a university,” in Future of Information and Communication Conference, 2024, pp. 72–83.
E. Mirsadeghi and S. Khodayifar, “Hybridizing particle swarm optimization with simulated annealing and differential evolution,” Cluster Comput, vol. 24, no. 2, pp. 1135–1163, 2021, doi: 10.1007/s10586-020-03179-y.
K. Sun et al., “Hybrid genetic algorithm with variable neighborhood search for flexible job shop scheduling problem in a machining system,” Expert Syst Appl, vol. 215, p. 119359, 2023, doi: https://doi.org/10.1016/j.eswa.2022.119359.
F. H. Awad, A. Al-Kubaisi, and M. Mahmood, “Large-scale timetabling problems with adaptive tabu search,” Journal of Intelligent Systems, vol. 31, no. 1, pp. 168–176, Jan. 2022, doi: 10.1515/jisys-2022-0003.
T. A. El-Mihoub, A. A. Hopgood, and L. Nolle, “Self-adaptive learning for hybrid genetic algorithms,” Evol Intell, vol. 14, no. 4, pp. 1565–1579, 2021, doi: 10.1007/s12065-020-00425-5.
Z. Sharifi, K. Soltanian, and A. Amiri, “Developing Convolutional Neural Networks using a Novel Lamarckian Co-Evolutionary Algorithm,” in 2023 13th International Conference on Computer and Knowledge Engineering (ICCKE), 2023, pp. 399–408. doi: 10.1109/ICCKE60553.2023.10326238.
B. J. Ross, “A Lamarckian evolution strategy for genetic algorithms,” in Practical handbook of genetic algorithms, CRC Press, 2019, pp. 1–16.
H. Zhang and M. Ishikawa, “An extended hybrid genetic algorithm for exploring a large search space,” in Proceedings of the 2nd International Conference on Autonomous Robots and Agents, Dec. 2004, pp. 244–248.
A. Rjoub, “Courses timetabling based on hill climbing algorithm,” International Journal of Electrical and Computer Engineering (IJECE), vol. 10, 2020, doi: 10.11591/ijece.v10i6.pp6558-6573.
H. Alghamdi, T. Alsubait, H. Alhakami, and A. Baz, “A review of optimization algorithms for university timetable scheduling,” Engineering, Technology & Applied Science Research, vol. 10, 2020, doi: 10.48084/etasr.3832.
R. Bellio, S. Ceschia, L. Di Gaspero, A. Schaerf, and T. Urli, “Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem,” Comput Oper Res, vol. 65, pp. 83–92, 2016.
