Examination Seating Optimization Using Graph Coloring and Combinatorial Design
No Thumbnail Available
Date
2026
Authors
Kibona, Isack E.
January, Jeremiah
Matimbwa, Hadija
Nchia, Edwin
Matungwa, William
Vuai, Said A.H.
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 research article was published by ELSEVIER in 2026
Keywords
Exam scheduling Seat optimization Academic integrity Exam management