How Mathematics Improves The World | Building an Exam Timetable Without Putting One Student in Two Rooms at Once
An exam timetable looks like a table.
Monday morning.
Monday afternoon.
Tuesday morning.
Subjects appear inside boxes.
The finished page looks calm.
The problem underneath it is not.
One student takes Mathematics and Physics.
Another takes Physics and Economics.
A third takes Economics and Literature.
A large hall seats 500.
A smaller room seats 80.
One paper needs computers.
Another needs extra time arrangements.
An invigilator cannot supervise two places at once.
Some papers should not be placed back-to-back because students need reasonable recovery.
A school can have thousands of candidates and hundreds of papers.
The timetable must satisfy all hard constraints and still be humane.
Mathematics turns this into a combinatorial optimisation problem.
Quick Read
Exam timetabling allocates examinations to time periods and rooms subject to hard constraints that must never be violated and soft constraints that should be minimised when possible. A student clash is a hard constraint: if any student takes two papers, those papers cannot occupy the same period. Room capacity, room suitability and institutional rules add further constraints.
The core conflict structure can be represented as a graph. Each exam is a vertex. Draw an edge between two exams whenever at least one student takes both. A feasible timetable assigns time slots so adjacent vertices receive different colours. That is graph colouring.
The simple graph-colouring model already explains why the problem is difficult. Graph colouring is computationally hard in general. Real exam timetabling adds room assignment, student spread, precedence, special facilities and fairness, creating a larger NP-hard optimisation problem. Recent research continues to use graph colouring to create feasible starting solutions, then improves them with hill climbing, hyper-heuristics and other metaheuristic techniques. A 2024 study, for example, generated an initial exam timetable using graph colouring and improved penalty scores using a steepest-ascent hill-climbing hyper-heuristic.
A separate 2026 open-access study shows how graph colouring and combinatorial design can also optimise examination seating, reducing room and invigilation requirements in a case involving 5,175 students. The lesson is broader than one algorithm: examination administration is a resource-allocation problem in which graph structure exposes conflicts and optimisation uses scarce time, rooms and staff more efficiently.
One-sentence answer: Mathematics improves the world by converting thousands of overlapping student enrolments into a conflict graph, then searching for a timetable that avoids impossible clashes while distributing rooms, staff and exam pressure as fairly and efficiently as possible.
The First Rule Is Absolute: One Student Cannot Sit Two Exams at Once
Let exams i and j share at least one student.
If ti and tj are their assigned periods, then:
ti ≠ tj.
This tiny inequality is the backbone of the timetable.
Do it for every conflicting pair.
Now the schedule becomes a system of pairwise incompatibilities.
Conflict Graphs: Turn Enrolment Data Into Geometry
Create one vertex per exam.
Connect two vertices if at least one candidate takes both.
A dense region of the graph means many subjects share students.
A highly connected exam is difficult to schedule because it cannot share a period with many others.
Graph degree becomes scheduling difficulty.
The calendar is hiding a network.
Graph Colouring: A Time Slot Is a Colour
Assign each vertex one colour.
Adjacent vertices cannot share colours.
If colour 1 means Monday morning and colour 2 Monday afternoon, a proper colouring is a clash-free exam schedule under the simplified model.
The minimum number of colours needed is the graph’s chromatic number.
In practice, schools usually have a fixed number of available periods and ask whether the graph can be coloured within them while also satisfying many additional rules.
Cliques Give a Lower Bound
Suppose five exams are pairwise connected.
Some student overlap exists between every pair.
These five vertices form a clique.
They require at least five distinct periods.
No algorithm can fit them into four without breaking a clash constraint.
Structural lower bounds are valuable because they distinguish “the timetable generator failed” from “the requested schedule is mathematically impossible”.
Why Greedy Colouring Often Works Surprisingly Well
Order exams.
Give each the first available period not used by already-coloured neighbours.
This greedy algorithm is fast.
Its quality depends strongly on order.
Colour high-degree or highly constrained exams early and performance improves.
Heuristics such as saturation degree choose next the vertex with the most distinct neighbour colours already present.
A good ordering turns a simple rule into a strong baseline.
Hard Constraints and Soft Constraints Are Different Species
Hard constraint:
a student cannot sit two exams simultaneously.
Soft constraint:
avoid giving the same student three exams on consecutive periods if possible.
Hard violations make a timetable invalid.
Soft violations make it less desirable.
Optimisation must preserve this hierarchy.
A prettier schedule does not justify one impossible clash.
Penalty Functions: Turn Soft Discomfort Into Numbers
Suppose exams for one student are one period apart.
High penalty.
Two periods apart.
Smaller penalty.
Several days apart.
No penalty.
A total objective can sum penalties across students:
minimise Σ student inconvenience.
The exact weights are a policy choice.
Mathematics makes that choice visible.
Room Capacity: A Time Slot Can Be Feasible and Still Have Nowhere to Put Everyone
Three non-conflicting exams can share Tuesday morning.
Candidate counts:
420 + 260 + 190 = 870.
Total available seats that morning: 700.
The graph colouring is valid.
The timetable is physically impossible.
Room capacity couples scheduling with packing and assignment.
Room Suitability: Seats Are Not Interchangeable
A computer-based exam needs machines.
A listening paper needs audio.
Some candidates need accessible seating.
Some papers require specialised equipment.
Define a compatibility matrix:
Cer=1 if exam e may use room r; 0 otherwise.
Assignment must occur only where C=1.
Capacity alone is not enough.
One Exam Can Span Several Rooms
A 600-student paper may need Hall A plus Rooms B and C.
This creates operational cost.
More invigilators.
More script movement.
Greater coordination risk.
A soft constraint may prefer keeping a large exam in as few rooms as possible.
Efficient seating and exam timetabling interact.
Seating Optimisation: Use Rooms Better Without Mixing Carelessly
A 2026 open-access study used graph colouring and combinatorial design for university exam seating.
In a case with 5,175 students, the proposed mixed-course allocation reduced the number of rooms used substantially and cut the minimum invigilation requirement while maintaining separation logic intended to support academic integrity.
The point is not that every institution should copy those exact numbers.
It is that seating is itself an optimisation layer beneath the timetable.
Invigilators Are Another Resource Constraint
Rooms require staff.
Staff have availability.
Some cannot invigilate certain papers.
One person cannot be assigned to two rooms simultaneously.
Invigilator assignment is another bipartite matching or integer-programming problem.
The complete exam system therefore contains multiple linked optimisation layers.
Special Arrangements: Equality of Time Is Not Always Fairness
Some students have approved extra-time or access arrangements.
The scheduling system may need:
- separate rooms;
- longer room occupation;
- special equipment;
- rest breaks;
- different start/end logistics.
A timetable that is clash-free for the standard duration can still conflict for extended-duration candidates.
Accessibility needs must exist inside the formal constraints, not be bolted on afterward.
Fairness: Avoid Concentrating the Pain
Suppose the average student has two exams in one week.
A small group has four exams in two days.
Average penalty can look acceptable while those students carry extreme burden.
Distributional objectives can penalise:
- maximum exams per day;
- consecutive exam runs;
- very short recovery windows;
- worst-student penalty.
A humane timetable should inspect tails, not only averages.
Morning and Afternoon Are Not Identical
Some institutions may have constraints on exam length, transport, meal breaks, religious observance or building availability.
A three-hour paper may fit in one period and not another.
Time slots have attributes.
The model should not assume colours are interchangeable when the real calendar is not.
Precedence: Some Exams Must Happen Before Others
A practical exam may need to precede a theory paper.
A common paper may need to be held simultaneously across campuses.
Security considerations may impose ordering.
Precedence becomes:
tA < tB.
Calendar logic adds directed constraints to the undirected conflict graph.
Multi-Campus Timetabling
A university operates several campuses.
Students may need travel time between them.
Two exams in consecutive periods can be individually legal and jointly impossible because transport takes an hour.
Travel-time separation becomes another soft or hard constraint depending on policy.
Geography enters the timetable.
Why the Problem Is NP-Hard
Even the simplified graph-colouring core is hard in general.
Add rooms, fairness and institutional rules and the search space grows combinatorially.
If 100 exams can each occupy 20 periods, naive assignment space contains 20100 possibilities before constraints remove most of them.
That is why exact brute force is hopeless.
Good algorithms exploit structure and improve solutions iteratively.
Integer Programming: Put Choices Into Binary Variables
Let xep=1 if exam e is assigned to period p.
Each exam occupies one period:
Σpxep=1.
For conflicting exams e and f:
xep+xfp≤1 for every p.
Add room and soft-penalty variables.
The timetable becomes a mixed-integer optimisation model.
Exact solvers can handle many practical instances, especially with decomposition and good formulations, but very large or richly constrained cases may still need heuristics.
Local Search: Improve One Move at a Time
Start from a feasible timetable.
Move one exam to another period.
Swap two exams.
Evaluate penalty change.
Keep improvements.
Repeat.
Simple hill climbing gets trapped when no single move improves the schedule even though a sequence of temporarily worse moves could reach a better region.
This motivates richer metaheuristics.
Simulated Annealing: Occasionally Accept a Worse Timetable
Early in search, accept some worse moves with probability depending on temperature and penalty increase.
This allows escape from local minima.
As temperature falls, the algorithm becomes more selective.
The mathematics borrows a metaphor from cooling materials: high temperature explores; low temperature settles.
Tabu Search: Remember Where You Just Came From
Local search can cycle.
Move Exam A to Tuesday.
Later move it back.
Tabu search temporarily forbids recent moves or attributes so the algorithm explores new regions.
Memory becomes a search mechanism.
Hyper-Heuristics: Choose the Search Method, Not Only the Timetable
A hyper-heuristic operates one level above ordinary heuristics.
Instead of directly deciding where every exam goes, it decides which low-level heuristic to apply next.
Move.
Swap.
Recolour a cluster.
The 2024 Procedia Computer Science study uses a graph-colouring initial solution and a steepest-ascent hill-climbing hyper-heuristic to reduce timetable penalty.
The ambition is generality: a strategy for choosing search moves across different instances.
Large Neighbourhood Search: Break Part of the Timetable Deliberately
Remove a cluster of exams from the timetable.
Reinsert them intelligently.
Destroy-and-repair methods can escape local minima because they modify many decisions at once.
Controlled destruction can improve global order.
Constraint Programming: Let Propagation Eliminate Impossible Choices
Exam A cannot be Monday because of room capacity.
Then Exam B, which conflicts with A’s remaining Tuesday option, loses Tuesday.
This forces B to Wednesday.
Constraint programming repeatedly propagates implications.
Instead of enumerating every schedule, it prunes impossible branches early.
Decomposition: Separate Period Assignment From Room Assignment
One strategy first assigns exams to periods using conflict and candidate-volume constraints.
Then assign rooms within each period.
If room assignment fails, feed information back and revise the period plan.
Breaking one giant problem into structured subproblems can make optimisation tractable.
Robustness: What If a Room Becomes Unavailable?
A pipe bursts.
A computer lab fails.
A hall loses air-conditioning.
A timetable using every room at 100% capacity has no resilience.
Reserve capacity and alternative rooms create operational slack.
Robust scheduling sacrifices a little nominal efficiency to survive disruption.
Change Management: One Late Enrolment Can Create a New Edge
A student changes subjects after the timetable is generated.
Two exams previously non-conflicting now share a candidate.
A new edge appears in the graph.
Rebuilding the whole timetable may be disruptive.
Incremental optimisation seeks a repair with minimal changes.
Stability of the published timetable becomes another objective.
Why Students Care About Stability
Once dates are published, families plan transport, work and revision.
A mathematically better timetable generated later can be socially worse if it moves half the examinations unnecessarily.
Optimisation should include change cost.
The best plan before publication and the best repair after publication are different problems.
Academic Integrity Can Become a Scheduling Variable
If different papers share a large room, seat mixing can reduce same-course adjacency.
The 2026 seating-optimisation study uses graph colouring and mixed-course design partly to improve efficient seating while reducing interaction opportunities.
The exact integrity policy belongs to institutions.
Mathematics can encode that policy into allocation constraints.
The Objective Function Is a Statement of Institutional Values
Minimise rooms.
Minimise student back-to-back exams.
Minimise invigilators.
Minimise timetable changes.
These goals can conflict.
Compressing exams into fewer days may save rooms and worsen student load.
Spreading everything widely may help students and extend the exam period.
The optimiser cannot decide which trade-off is morally correct.
It makes the trade-off explicit.
A Classroom Thought Experiment: Colour the Exams
Four exams:
- Math;
- Physics;
- Economics;
- Literature.
Students create conflicts:
- Math–Physics;
- Physics–Economics;
- Economics–Literature;
- Math–Literature.
Draw the graph.
How many colours are needed?
Now add Math–Economics.
The required colouring may change.
One new student combination can alter the timetable structure.
Primary Mathematics: Timetabling Begins With Logic
Primary students can understand:
- tables;
- sets;
- ordering;
- if–then rules;
- simple graphs;
- counting.
If Alice takes both Math and Science, those exams need different boxes.
The advanced problem begins with basic logical incompatibility.
Secondary Mathematics: The Calendar Becomes Graph Theory
Secondary students add:
- graphs;
- matrices;
- inequalities;
- optimisation;
- probability;
- algorithms.
Conflicts become adjacency.
Periods become colours.
Room capacity becomes inequalities.
Soft constraints become weighted penalties.
Advanced Mathematics: Exam Timetabling as Combinatorial Optimisation
Modern timetabling draws on:
- graph colouring;
- integer programming;
- constraint programming;
- metaheuristics;
- hyper-heuristics;
- multi-objective optimisation;
- robust optimisation.
The student sees an exam date.
The scheduler sees a high-dimensional conflict system compressed into a table.
Why This Improves the World
1. It prevents impossible clashes
Conflict graphs make every shared-student constraint explicit before publication.
2. It uses scarce rooms more efficiently
Capacity and suitability constraints let institutions combine papers intelligently without overbooking spaces.
3. It can reduce student overload
Soft constraints spread examinations and penalise harmful clusters instead of treating all feasible schedules as equally good.
4. It reduces administrative work
Automated search can examine far more alternatives than manual timetable construction.
5. It makes special arrangements part of the plan
Accessibility and extended-duration requirements can be represented from the start rather than patched after scheduling.
6. It explains impossibility honestly
Clique and capacity lower bounds can prove that some requested timetables cannot exist under the given constraints.
What Mathematics Does Not Do
A clash-free timetable is not automatically a humane timetable.
Minimum room use is not automatically the best student outcome.
An optimiser cannot invent rooms that do not exist.
Soft-constraint weights do not define fairness by themselves.
An algorithm cannot know institutional priorities unless they are encoded.
And a mathematically optimal timetable can still be operationally poor if administrators cannot execute it reliably.
Frequently Asked Questions
Why is exam timetabling a graph-colouring problem?
Each exam can be represented as a vertex and each shared-student conflict as an edge. Assigning periods so conflicting exams never share a period is equivalent to colouring adjacent vertices differently.
What is a hard constraint?
A rule that cannot be violated, such as one student being unable to sit two simultaneous exams or a room being unable to exceed capacity.
What is a soft constraint?
A preference whose violation is undesirable but may be permitted, such as avoiding consecutive exams or minimising the number of split rooms.
Why not just schedule the biggest exams first?
Size matters for rooms, but graph connectivity matters for time conflicts. A smaller exam sharing students with many other papers can be harder to place than a larger but isolated exam.
Sources and Further Reading
- Generic University Examination Timetabling System with Steepest-Ascent Hill Climbing Hyper-heuristic Algorithm, Procedia Computer Science, 2024.
- Examination Seating Optimization Using Graph Coloring and Combinatorial Design, 2026, open-access case study on room and invigilation efficiency.
- Operations-research literature on examination timetabling, graph colouring, benchmark instances, constraint programming and metaheuristic optimisation.
Continue Through eduKateSG
Continue with How Mathematics Works. Compare this article with Stopping One Late Train From Making the Whole Railway Late, where a timetable likewise allocates scarce time under conflict constraints, and with Dividing Something Fairly When Everyone Values It Differently, where feasibility and fairness are again separate mathematical questions.
Final Thought: The Best Exam Timetable Looks Boring
No student is double-booked.
No hall overflows.
No special arrangement is forgotten.
The worst exam clusters have been softened.
Rooms have staff.
The published dates stop moving.
Thousands of constraints disappear behind one clean calendar.
That is the success.
Mathematics improves the world here by doing something difficult enough that, when it works, nobody notices the difficulty at all.