What is the maths behind an exam timetable?



Sweaty-palmed and reciting facts over and over in their heads, the hordes of university and school students sitting down to exams this month will have precious little time to think about how their exam timetable was put together.

A typical university student – if there is such a thing – may sit five or six examinations over a two-week period. Each examination might be in a different room, or even in a different location. But every school, university, or college is different, with a different set of timetabling challenges.

There are hard constraints in timetable design: for example, students cannot sit two examinations at the same time, the size of the exam room must be big enough for the number of students, and some exams need certain facilities, such as computers.

Other constraints are a bit more flexible – so called “soft constraints”. These include spreading the exams out as much as possible to give each student more revision time, or scheduling larger examinations at the start of the exam period so that lecturers have more time to mark them.

Carter benchmarks

In 1996, Canadian engineering academic Michael Carter and his colleagues presented a paper that provided the scientific community with 13 examination timetabling problems. The benchmark problems had between 81 to 2,419 examinations and 611 to 30,032 students that have to be timetabled.

Almost 20 years on, there are still papers being published that tackle the Carter benchmarks – as they have become known (see the MISTA and PATAT conferences for examples) – demonstrating how challenging they are. But the problems presented in this 1996 paper are a simplified version of the timetabling problems – with an underlying simplified mathematical model – that are faced by most schools, colleges and universities.

Recently the International Timetabling Competition (ITC) data sets have been introduced. These – and underlying mathematical models – are more realistic – but are still far from capturing all the issues that need to be addressed by every school, college and university.

Balancing all the constraints to create a perfect timetable is usually impossible. This can lead to some (hopefully) isolated unfairness. As a student, you might be faced with one examination straight after another or you may have an evening exam, followed by one early the next morning. In some cases you may have to be quarantined as a paper being sat by other students has some common questions with a paper that you will sit in the future.

So, the challenge is to create an examination timetable that is as fair to as many students as possible but, in the knowledge that you can’t please all the people all of the time.

Millions of options

An obvious question is why not simply generate every possible timetable, compare them against each other and choose the one that would satisfy most students?

Unfortunately, this is not possible. Assume that we can generate 1,000 examination timetables every second. For an institution the size of the University of Nottingham (which has about 33,000 students in the UK), it would take millions of years to generate every possible timetable, such is the number of possible options.

For a school, university or college with a relatively small number of students, it is not a realistic proposition to do this, so we have to resort to other approaches.

Normally, the examinations office has a couple of months to generate the timetable. The timetable undergoes continual refinement as the underlying data changes to correct data errors, student requirements become clearer (for example, some students may require specialised support, additional time etc.), invigilation data becomes available and the exact number of students sitting an examination becomes certain.

Typical of the approaches, at least in recent years, that are being used to generate examination timetables is hyper-heuristics, which are computer models that can solve general problems. Many other methodologies have also been used in the last 20 years or so, but we are still a long way from always being able to arrive at a perfect solution.

The problem of timetabling exams is typical of many problems where you need some way of modelling potential solutions and comparing one against another to choose the best one. Problems such as how to schedule deliveries with a fleet of vehicles, taxi scheduling, or how to display goods on supermarket shelves, need similar approaches to generate solutions.

So, as students sit their examinations, give some thought to the work that has gone into creating the examination timetable. It may not be perfect, but a lot of time and effort has gone into producing it.