Abstract
Running the exams of universities incurs significant expenses mainly because many rooms must be opened to conduct the exam at each session. Indeed, due to conservative policies and some other constraints associated with specific courses, many rooms often are not used efficiently. In contrast to previous studies on examination timetabling, which focus on joint optimization of time slots and room allocation, the current paper is dedicated to the post-examination timetabling problem of efficient room utilization. Specifically, we examine how one can minimize the number of rooms necessary for conducting the fixed examination sessions with consideration of some constraints like room capacities, campus limitations, and separation rules for courses. There are two different cases to be examined: (i) optimizing existing allocations through post-processing and (ii) allocating rooms for the exam sessions anew. We suggest a quick greedy algorithm based on a best-fit decreasing approach combined with the use of an ILP formulation to obtain optimal solutions for small-to-moderate instances. Numerical experiments performed on a real-world dataset from Ho Chi Minh City University of Technology (HCMUT), a multi-campus public university in Vietnam, show promising results, including substantial room savings and a clear scalability–optimality trade-off. Keywords: examination timetabling, room allocation, integer linear programming, greedy heuristic, room utilization optimization