University of Canterbury Examination Timetabling System
The University of Canterbury (UC), like many other academic institutions, faces the task of scheduling examinations at the end of each semester. The problem involves assigning each examination to a specific time-slot and room. Constructing a good timetable is not an easy task, with the scheduler having to take a large amount of data into account whilst trying to achieve good solutions against conflicting objectives. Typical objectives include minimising the number of students that have direct conflicts (more than one examination during the same time-slot), while achieving a good spread of examinations for each student over the examination period. Additional constraints, which may be specific to the UC, include allowing sufficient time for the marking of examination scripts and limiting the number of students sitting examinations during a given time-slot.
The UC examination timetabling problem consists of two sets of examinations that need to be scheduled every year. These are the mid-year examinations upon completion of the first semester, and the end-year examinations upon completion of the second semester. Typical values for the end-year examination timetabling problem include 480 examinations to be scheduled into 32 time-slots, at an average of approximately 15 examinations per time-slot. The mid-year examinations have a denser timetable structure with approximately 200 examinations to be scheduled into 10 time-slots at an average of 20 examinations per time-slot.
Prior to the year 2000, examination timetables at UC were produced entirely manually, whereby the previous years’ timetable is used with manual ‘fix-ups’ to reflect changes in student numbers and courses from year to year. With the increasing number of courses and course options available, a better method of scheduling was required to deal with the increasingly complex task. Therefore, the examination scheduler produced an algorithm that inserted examinations into time-slots in order to minimise direct examination clashes and place large courses early in the examination period. This method of scheduling is currently still in use, however it ignores the presence of additional objectives on the problem such as student examination spread, the lack of which has caused complaints from various students and lecturers.
Specific University Requirements
Two main factors make examination timetabling at the UC particularly difficult. Firstly, the two examination timetables for a particular year are set by November the previous year. This is to allow examination-time publishing in the student enrolment handbook for the year in question. Therefore, any student knows the spread of examinations and potential direct examination clashes before he/she enrols in courses for the year, and hence responsibility for obtaining good examination spread becomes the students. The second main difficulty is due to the very flexible degree system offered at UC. Students can take a range of seemingly unrelated course options, therefore leaving many students with examinations that do not fit common course programmes.
The assigning of examinations to specific time-slots has been treated independently of the assignment of examinations to rooms. This is mainly due to the relatively low number of students to the examination space available, which means that room allocation has a relatively low impact on the examination-time scheduling problem. In previous years, given an examination timetable, examinations have been allocated to rooms with minimal examination-time ‘fix-ups’ required.
Since examination scheduling has to be undertaken the year prior, a relevant forecast of student enrolments is required. To achieve this, the current year’s student enrolments are used as a forecast for the upcoming year’s enrolments. Additionally, new courses for the upcoming year need to be included in the timetable. In order to predict the likely conflict a new course may have in an upcoming year’s timetable, a currently existing course is mapped to the new course. This effectively adds students taking the mapped course to the new course. The mapped courses should therefore contain students who are likely to take the new course.
The authors wish to thank Ken Allot, the examination scheduler at the time of publication, for his help and effort with the project. We would also like to thank our project supervisors Dr John Giffin and Dr Terri Green, and also Dr Ross James of the Department of Management at the University of Canterbury.