Examination seating optimization using graph coloring and combinatorial design
No Thumbnail Available
Date
2026-05-12
Journal Title
Journal ISSN
Volume Title
Publisher
ELSEVIER
Abstract
This paper presents an optimization approach for exam seating in universities with limited infrastructure, based on a mixed-course allocation model. Students in different courses share rooms while maintaining spatial separation to improve academic integrity. The model incorporates a theoretical probability of interaction, which decreases as the number of mixed courses in a room increases.
Using real data with 5175 students, the proposed model significantly improves upon the traditional method. Although the traditional approach required 35 rooms with a total capacity of 7269, the proposed model utilized only 12 large rooms, leaving 23 rooms unused and saving about 2475 seats. The unused space within the occupied rooms was minimal (approximately 29 seats), indicating near-optimal utilization.
The invigilation requirement was reduced from at least 70 to 36, achieving nearly 50% savings. Small-enrollment and carryover courses are efficiently integrated and sorted. The model is formulated using graph coloring and combinatorial optimization, supported by a simple allocation algorithm.
Description
This journal article was published by Elsevier
Keywords
Exam scheduling Seat optimization Academic integrity Exam management