Hybrid genetic algorithm with dsatur seeding for automated course timetabling: a three-stage comparative study

  • Ary Ramadhan 
    Universitas Negeri Padang
    Indonesia
  • Rifqi Aulia Zaim
    Universitas Negeri Padang
    Indonesia
  • Aditya Hanum Widarsa
    Universitas Negeri Padang
    Indonesia
  • Maltha Kharisma
    Universitas Negeri Padang
    Indonesia
  • Arif Budiman
    Universitas Negeri Padang
    Indonesia
  • Vivi Indriyani
    Universitas Negeri Padang
    Indonesia
  • Alrizka Hairi Dilfa
    Universitas Negeri Padang
    Indonesia

Abstract

This study aims to develop and evaluate a web-based university course timetabling system that hybridizes a Genetic Algorithm (GA) with DSATUR graph-coloring seeding, and to quantify the separate effects of room-type constraints and DSATUR seeding on hard-constraint satisfaction and convergence. The system was developed using the 4D model (Define, Design, Develop, Disseminate) and implemented in the CodeIgniter framework. Real data from the odd semester of the 2025/2026 academic year of the Visual Communication Design Study Program, Universitas Negeri Padang, were used, comprising 87 class sections, 26 courses, 16 lecturers, 12 theory rooms, and 6 practicum studios. A conflict was operationally defined as a lecturer or a room assigned to more than one class section in the same time slot, and a run was successful when it reached the maximum fitness of 87 with zero conflicts. Three stages were compared over ten independent runs each: a basic GA (Stage 1), a GA with room-type separation (Stage 2), and a GA with room-type separation and a 10% DSATUR-seeded initial population (Stage 3). Differences were tested using Fisher’s exact test and Welch’s t-test, with Cohen’s d as the effect size. Room-type separation increased the success rate from 10% to 100% (p < 0.001) and reduced the mean convergence generation from 405.9 to 174.4 (p < 0.001). DSATUR seeding further reduced the mean convergence generation by 15.5% (from 174.4 to 147.3) and the mean computation time by 9.8% (from 71.16 s to 64.22 s); however, these reductions were not statistically significant with ten runs (p = 0.372 and p = 0.132). The findings show that domain-specific constraint modeling is the decisive factor for feasibility, whereas heuristic seeding provides a moderate efficiency gain. The final system produced conflict-free timetables in every run and reduced a manual process of several days to about one minute of computation.

Keywords
  • Genetic algorithm,
  • DSATUR,
  • University course timetabling,
  • Room-type differentiation,
  • Hybrid algorithm
Lisensing Information
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite
Ramadhan, A., Aulia Zaim, R., Hanum Widarsa, A., Kharisma, M., Budiman, A., Indriyani, V., & Hairi Dilfa, A. (2026). Hybrid genetic algorithm with dsatur seeding for automated course timetabling: a three-stage comparative study . Lentera Negeri, 7(1), 2197–2210. https://doi.org/10.29210/994320
Endnote/Zotero/Mendeley (RIS) BibTeX
References
  1. S. Abdipoor, R. Yaakob, S. L. Goh, and S. Abdullah, “Meta-heuristic approaches for the University Course Timetabling Problem,” Intelligent Systems with Applications, vol. 19, p. 200253, Sep. 2023, doi: 10.1016/J.ISWA.2023.200253.
  2. S. Ceschia, L. Di Gaspero, and A. Schaerf, “Educational timetabling: Problems, benchmarks, and state-of-the-art results,” European Journal of Operational Research, vol. 308, no. 1, pp. 1–18, Jul. 2023, doi: 10.1016/j.ejor.2022.07.011.
  3. Y. Xiao, X. L. Li, L. Jiang, P. Wang, K. Wang, and N. Luo, “Towards Dynamic University Course Timetabling Problem: An Automated Approach Augmented via Reinforcement Learning,” Proceedings - IEEE International Conference on Data Mining, ICDM, pp. 520–529, 2024, doi: 10.1109/ICDM59182.2024.00059.
  4. 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.
  5. 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, no. 6, pp. 6410–6417, Dec. 2020, doi: 10.48084/ETASR.3832.
  6. M. Davison, A. Kheiri, and K. G. Zografos, “Modelling and solving the university course timetabling problem with hybrid teaching considerations,” Journal of Scheduling 2024 28:2, vol. 28, no. 2, pp. 195–215, Oct. 2024, doi: 10.1007/S10951-024-00817-W.
  7. G. Colajanni and P. Daniele, “A new model for curriculum-based university course timetabling,” Optimization Letters 2020 15:5, vol. 15, no. 5, pp. 1601–1616, May 2020, doi: 10.1007/S11590-020-01588-X.
  8. H. Babaei, J. Karimpour, and A. Hadidi, “A survey of approaches for university course timetabling problem,” Comput. Ind. Eng., vol. 86, pp. 43–59, Aug. 2015, doi: 10.1016/J.CIE.2014.11.010.
  9. M. Mokhtari, M. Vaziri Sarashk, M. Asadpour, N. Saeidi, and O. Boyer, “Developing a Model for the University Course Timetabling Problem: A Case Study,” Complexity, vol. 2021, no. 1, p. 9940866, Jan. 2021, doi: 10.1155/2021/9940866.
  10. A. M. Al-Fitouri, A. Agaal, M. M. Ali, and H. A. Bugrin, “A Genetic Algorithm Approach for University Course Timetabling: A Case Study at the Faculty of IT, Sebha University,” Sebha University Conference Proceedings, vol. 4, no. 3, pp. 173–179, Oct. 2025, doi: 10.51984/sucp.v4i3.4003.
  11. I. A. Abduljabbar, S. M. Abdullah, I. A. Abduljabbar, and S. M. Abdullah, “An Evolutionary Algorithm for Solving Academic Courses Timetable Scheduling Problem,” Baghdad Science Journal, vol. 19, no. 2, p. 11, Apr. 2022, doi: 10.21123/bsj.2022.19.2.0399.
  12. A. Ghaffar, I. U. Din, A. Tariq, and M. H. Zafar, “Hybridization and artificial intelligence in optimizing university examination timetabling problem: A systematic review,” Review of Education, vol. 13, no. 2, p. e70071, Aug. 2025, doi: 10.1002/REV3.70071.
  13. E. Sing et al., “A Survey of Solution Methodologies for Exam Timetabling Problems,” IEEE Access, vol. 12, pp. 41479–41498, 2024, doi: 10.1109/ACCESS.2024.3378054.
  14. S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimedia Tools and Applications 2020 80:5, vol. 80, no. 5, pp. 8091–8126, Oct. 2020, doi: 10.1007/S11042-020-10139-6.
  15. G. Alnowaini and A. A. Aljomai, “Genetic Algorithm for Solving University Course Timetabling Problem Using Dynamic Chromosomes,” 2021 International Conference of Technology, Science and Administration, ICTSA 2021, Mar. 2021, doi: 10.1109/ICTSA52017.2021.9406539.
  16. J. O. Agushaka and A. E. Ezugwu, “Initialisation Approaches for Population-Based Metaheuristic Algorithms: A Comprehensive Review,” Applied Sciences 2022, Vol. 12, Page 896, vol. 12, no. 2, p. 896, Jan. 2022, doi: 10.3390/APP12020896.
  17. 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 2020 51:1, vol. 51, no. 1, pp. 467–492, Aug. 2020, doi: 10.1007/S10489-020-01833-X.
  18. S. Biswas, S. A. Nusrat, N. Sharmin, and M. Rahman, “Graph Coloring in University Timetable Scheduling,” International Journal of Intelligent Systems and Applications, vol. 15, no. 3, pp. 16–32, Jun. 2023, doi: 10.5815/IJISA.2023.03.02.
  19. K. Xiang, X. Hu, M. Yu, and X. Wang, “Exact and heuristic methods for a university course scheduling problem,” Expert Syst. Appl., vol. 248, p. 123383, Aug. 2024, doi: 10.1016/J.ESWA.2024.123383.
  20. M. Farhan, “Pewarnaan Graf dalam Penjadwalan Mata Pelajaran SMP Menggunakan Algoritma DSATUR,” 2025, Accessed: Aug. 13, 2026. [Online]. Available: http://repository.ipb.ac.id/handle/123456789/160936
  21. R. N. Amalia and P. Affandi, “PENERAPAN PEWARNAAN GRAF UNTUK OPTIMALISASI PENJADWALAN KULIAH DI PROGRAM STUDI MATEMATIKA: Algoritma Welch-Powell,” Equiva Journal, vol. 3, no. 1, pp. 34–42, Jul. 2025, Accessed: Aug. 13, 2026. [Online]. Available: https://journal.itk.ac.id/index.php/equiva/article/view/1240
  22. D. Brélaz, “New methods to color the vertices of a graph,” Communications of the ACM, vol. 22, no. 4, pp. 251–256, Apr. 1979, doi: 10.1145/359094.359101.
  23. L. Cheng, Q. Tang, L. Zhang, and Z. Zhang, “Multi-objective Q-learning-based hyper-heuristic with Bi-criteria selection for energy-aware mixed shop scheduling,” Swarm Evol. Comput., vol. 69, p. 100985, Mar. 2022, doi: 10.1016/J.SWEVO.2021.100985.
  24. M. C. Yustina, I. N. Ichsan, and G. M. Suranegara, “Implementasi Algoritma Genetika Proses Mutasi Differential Evolution Pada Sistem Penjadwalan Mata Pelajaran,” KLIK: Kajian Ilmiah Informatika dan Komputer, vol. 5, no. 1, pp. 116–130, Aug. 2024, doi: 10.30865/KLIK.V5I1.2109.
  25. Y. Indarta, F. Ranuharja, S. Sukardi, A. D. S. Samala, and I. P. Dewi, “Web Application Development for Syari Online Shop Using 4D Model Development,” Sinkron : jurnal dan penelitian teknik informatika, vol. 6, no. 2, pp. 720–728, May 2022, doi: 10.33395/SINKRON.V7I2.11376.
  26. D. Romaguera, J. Plender-Nabas, J. Matias, and L. Austero, “Development of a Web-based Course Timetabling System based on an Enhanced Genetic Algorithm,” Procedia Comput. Sci., vol. 234, pp. 1714–1721, Jan. 2024, doi: 10.1016/J.PROCS.2024.03.177.
  27. A. Ghaffar, M. U. Sattar, M. Munir, and Z. Qureshi, “Multi-objective fuzzy-based adaptive memetic algorithm with hyper-heuristics to solve university course timetabling problem,” EAI Endorsed Transactions on Scalable Information Systems, vol. 9, no. 4, pp. e4–e4, Dec. 2021, doi: 10.4108/EAI.16-12-2021.172435.
  28. M. Herman, “Designing a Web-Based Thesis Title Submission System Using the Codeigniter 3 Framework,” Knowbase : International Journal of Knowledge in Database, vol. 1, no. 1, pp. 44–50, Jun. 2021, doi: 10.30983/IJOKID.V1I1.4960.
  29. M. Assi, B. Halawi, and R. A. Haraty, “Genetic algorithm analysis using the graph coloring method for solving the university timetable problem,” Procedia Computer Science, vol. 126, pp. 899–906, 2018, doi: 10.1016/j.procs.2018.08.024.
  30. C. Akkan and A. Gülcü, “A bi-criteria hybrid genetic algorithm with robustness objective for the course timetabling problem,” Computers & Operations Research, vol. 90, pp. 22–32, Feb. 2018, doi: 10.1016/j.cor.2017.09.007.
  31. S. L. Goh, G. Kendall, and N. R. Sabar, “Improved local search approaches to solve the post enrolment course timetabling problem,” European Journal of Operational Research, vol. 261, no. 1, pp. 17–29, Aug. 2017, doi: 10.1016/j.ejor.2017.01.040.
  32. E. Rappos, E. Thiémard, S. Robert, and J.-F. Hêche, “A mixed-integer programming approach for solving university course timetabling problems,” Journal of Scheduling, vol. 25, no. 4, pp. 391–404, Aug. 2022, doi: 10.1007/s10951-021-00715-5.
  33. 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 Systems with Applications, vol. 165, p. 113943, Mar. 2021, doi: 10.1016/j.eswa.2020.113943.
  34. R. Lewis, “A survey of metaheuristic-based techniques for university timetabling problems,” OR Spectrum, vol. 30, no. 1, pp. 167–190, 2008, doi: 10.1007/s00291-007-0097-0.
  35. R. Qu, E. K. Burke, and B. McCollum, “Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems,” European Journal of Operational Research, vol. 198, no. 2, pp. 392–404, 2009, doi: 10.1016/j.ejor.2008.10.001.

Similar Articles

1 2 3 4 > >> 

You may also start an advanced similarity search for this article.

Downloads

PDF

Statistic

Abstract Views
: 18 times
PDF
: 2 times