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 ↗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).
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}
}
EUVIMED