Graham Kendall: Timetabling Research

Introduction

According to Carter, Laporte and Lee (1996), examination timetabling is "to assign examinations to a limited number of time periods in such a way that there are no conflicts, i.e. no student can write more than one examination at a time, while ensuring a number of side constraints are satisfied." Schaerf (1999) defines examination timetabling as "The scheduling for the exams of a set of university courses, avoiding overlap of exams of courses having common students, and spreading the exams for the students as much as possible."

Course Timetabling (Schaerf, 1999) is defined as "The weekly scheduling for all the lectures of a set of university courses, minimizing the overlaps of lectures of courses having common students." Rossi-Doria et al. (2003) define course timetabling as "A general problem consists in assigning a set of events (classes, lectures, tutorials, etc.) into a limited number of timeslots so that a set of constraints are satisfied."

Schaerf (1999) further defines School Timetabling as "The weekly scheduling for all the classes of a school, avoiding teachers meeting two classes at the same time, and vice versa."

All the problem types above exhibit hard and soft constraints.

Hard constraints are those that have to be respected in order for the solution to be feasible. An often quoted hard constraint, from examination timetabling, is that no student can sit two (or more) exams at the same time. Actually, in practise, this constraint is often violated and universities will have to quarantine their students. However, for the scientific datasets, a hard constraint must be respected. Other hard constraints could include:

Ensure that exam(s) do not exceed the capacity of the room
A room might need certain equipment (e.g. computers)
Some exams may have to be scheduled at the same time as others (as they have common questions), and some exams may have to be scheduled before (or after) other examinations

Soft constraints do not have to be respected, but better quality solutions are those that violate the soft constraints the least. One of the common examples from the scientific literature is spreading examinations for students. That is, students should be given as much time as possible between examinations so that they have time to revise. In the often used Carter datasets this is actually the only soft constraint. However, there many other. For example:

Schedule large examinations first to give more time for marking
When exams share rooms try to schedule exams of the same length in the same room
Exams might be able to to share a room with another exam, but this should be avoided where possible
It might be possible to have an exam split across different rooms, but this should be avoided where possible
If an exam is held in two different rooms, then the rooms should be as close os possible to each other, in case questions arise and the lecturer can get from one room to another as quickly as possible

My Research Focus

The work that my students and I have done with regard to university timetabling has largely been concerned with attempting to model the real world problem, capturing all the hard and soft constraints, and then investigating suitable solution methodologies to solve those problems.

Naimah Hussin, for example, investigated a large examination timetabling problem from her host institution. You might want to take a look at her PhD thesis (as well as her publications, which can be accessed via my timetabling publications).

Another student, Mohd N Mohmad Kahar (Nizam), has also modelled a real world examination timetabling problem, from his host institution. Nizam has published both the model and a constructive heuristic in EJOR, which is able to produce better quality solutions when compared to the manual method the instituion currently uses.

I have also published some timetabling papers, that utilise hyper-heuristics. For example, A Monte Carlo hyper-heuristic for examination timetabling and A Tabu-Search Hyperheuristic for Timetabling and Rostering.

Publications

You can see my timetabling publications here.