EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Examination timetabling with independent resource pools: A multi-stage genetic algorithm approach

Khalil Chebil, Mahdi Khemakhem, Abdallah Hammad, Mohammed Alanazi

Computer Science and Information Systems · 2026 · 23 (3) · 1027-1052

DOI: 10.2298/csis251220025c ↗

Kurz gefasst

Fachartikel in der Zeitschrift Computer Science and Information Systems, 2026. Verfasst von Khalil Chebil und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 33 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Examination Timetabling Problem (ETP) is an NP-hard combinatorial optimization problem that has been extensively studied over the past decades, with methodologies ranging from classical heuristics to contemporary machine learning approaches. This paper provides a comprehensive literature review and proposes a novel two-stage genetic algorithm based decomposition combined with a clear linear mathematical formulation. A unique contribution of this work is addressing the practical complexity of two-separated examination facilities at PSAU, where male and female students study in completely separate buildings with independent examination rooms, capacities, and supervisory staff, yet must follow a synchronized examination schedule. This creates a coupled dual-ETP problem where two independent resource allocation problems must share identical time slot assignments, significantly increasing model complexity and constraint interactions. The proposed algorithm decomposes the problem into two sequential stages, time slot assignment and room assignment to effectively reduce computational complexity while maintaining solution quality. Additionally, a systematic comparison with Mixed-Integer Programming (MIP) formulation is provided to establish the trade-offs between exact and metaheuristic approaches. The algorithm is further benchmarked against simulated annealing and tabu search baselines to provide broader methodological context, demonstrating its advantage on coupled dual-resource instances. The algorithm shows particular strength in scalability, successfully solving large instances where MIP becomes computationally intractable, while maintaining competitive solution quality.

Zitieren

APA

Chebil, K., Khemakhem, M., Hammad, A., & Alanazi, M. (2026). Examination timetabling with independent resource pools: A multi-stage genetic algorithm approach. Computer Science and Information Systems, 23(3), 1027-1052. https://doi.org/10.2298/csis251220025c

Vancouver

Chebil K, Khemakhem M, Hammad A, Alanazi M. Examination timetabling with independent resource pools: A multi-stage genetic algorithm approach. Computer Science and Information Systems. 2026;23(3):1027-1052. doi:10.2298/csis251220025c

BibTeX
@article{Chebil2026,
  author = {Chebil, Khalil and Khemakhem, Mahdi and Hammad, Abdallah and Alanazi, Mohammed},
  title = {Examination timetabling with independent resource pools: A multi-stage genetic algorithm approach},
  journal = {Computer Science and Information Systems},
  year = {2026},
  volume = {23},
  number = {3},
  pages = {1027--1052},
  doi = {10.2298/csis251220025c}
}
Kostenlos starten →