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.
Chebil et al. (Thu,) studied this question.