A Context-Aware Constructive Heuristic for Highly-Constrained Room Allocation Problem in Examination Timetabling

Ahmad Abba Datti, Abdulwahab Lawan, Ibrahim Said Ahmad
dx.doi.org/10.17576/apjitm-2025-1402-12

Abstract

Examination timetabling is a complex optimization problem with significant implications for student well-being and institutional efficiency. Traditional room allocation methods prioritize capacity but often ignore spatial constraints, leading to long-distance student movement?particularly problematic in multi-campus institutions. This paper introduces a context-aware constructive heuristic, termed Closest-Room-First (CRF), which assigns students to exam rooms based on proximity to their departmental buildings. The heuristic is used to generate an initial population of solutions that are subsequently evolved using a tailored implementation of the Non-Dominated Sorting Genetic Algorithm II (NSGA-II). Although this study focuses on minimizing student travel distance as a single objective, NSGA-II was chosen for its extensibility and proven utility in constraint-driven single-objective optimization. Experimental results on nine Purdue benchmarks and a real-world dataset obtained from Bayero University Kano show CRF achieves >80% travel cost reductions compared to Random, Largest Room First, and Best Fit heuristics. All results were statistically validated using the Mann-Whitney U test (p < 0.001). Despite higher runtimes, CRF's trade-off is justified in constrained settings. These findings underscore the educational and logistical value of embedding spatial sensitivity in exam timetabling.

keyword

Exam Timetabling, Room Allocation, Constructive Heuristics, Genetic Algorithms, Context-Aware Algorithms.

Area

Data Mining and Optimization