EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Ary Ramadhan, Rifqi Aulia Zaim, Aditya Hanum Widarsa, Maltha Kharisma, Arif Budiman, Vivi Indriyani, Alrizka Hairi Dilfa

Lentera Negeri · 29.10.2026 · 7 (1) · 2197-2210

DOI: 10.29210/994320 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Lentera Negeri, online erschienen am 29.10.2026. Verfasst von Ary Ramadhan und 6 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Ramadhan, A., Zaim, R. A., Widarsa, A. H., Kharisma, M., Budiman, A., Indriyani, V., & Dilfa, A. H. (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

Vancouver

Ramadhan A, Zaim RA, Widarsa AH, Kharisma M, Budiman A, Indriyani V, et al. Hybrid genetic algorithm with dsatur seeding for automated course timetabling: a three-stage comparative study. Lentera Negeri. 2026;7(1):2197-2210. doi:10.29210/994320

BibTeX
@article{Ramadhan2026,
  author = {Ramadhan, Ary and Zaim, Rifqi Aulia and Widarsa, Aditya Hanum and Kharisma, Maltha and Budiman, Arif and Indriyani, Vivi and Dilfa, Alrizka Hairi},
  title = {Hybrid genetic algorithm with dsatur seeding for automated course timetabling: a three-stage comparative study},
  journal = {Lentera Negeri},
  year = {2026},
  volume = {7},
  number = {1},
  pages = {2197--2210},
  doi = {10.29210/994320}
}
Kostenlos starten →