• Home
• Examination Timetabling
• Problem Model
• Evaluation Function
• Problem Instances
• Input Format
• Output Format
• Validation
• Upload Solutions

 

Contact Details

Barry McCollum
SARC Building
School of Electronics, Electrical Engineering & Computer Science
Queen's University Belfast

Phone: +44 (0) 2890974622
Fax: +44 (0) 2890975666

The Problem Model

Overview

The examination timetabling problem model presented here extends the current model of the problem commonly worked upon. The fundamental problem involves timetabling exams into a number of periods within a defined examination session while satisfying a number of hard constraints. Like other areas of timetabling, a feasible solution is one in which all hard constraints are satisfied. The quality of the solution is measures in terms of soft constraints satisfaction.

New and additional Information is provided on constraints (hard and soft), resources and the examination session. For example in terms of hard constraints, room numbers and sizes are provided. In addition, information on structure, length and number of individual periods is also provided. In terms of soft constraints, much more practical information is provided in terms of how an organisation measures the overall quality of a solution.

Before describing the formulation in detail, the organisers would like to make the following general points;

We do not consider minimising the number of periods as part of this formulation as, in our experiences, educational institutions manage the process by using set times for the examination session.  That is not to say of course that this is not a major issue in relation to planning examination sessions. It is acknowledged that a full investigation and explanation of ‘Distance of feasibility” is required if the formulation provided here is to be useful for such purposes.

From experience, we have found that, in general gaining feasibility is not as important an issue as in some cases of course timetabling.  That is not to say, of course, that competitors may have difficulty satisfying all the hard constraints within the competition time limit requirement. If this is the case, and competitors experience difficulty in finding feasibility, we will decide how to deal with ‘non feasible' solutions. It is pointed out here that a competition time limit is essential to allow comparison of the techniques used. In practice, it can be argued that the need for such a time limit is not required as organisations are often happy to allow for longer running times in search for 'better' solutions. That being said, it is often the case that due to many changes having to be made during solution construction [1], an individual within an institution requires the ability to generate many solutions quickly after making various amendments to the underlying data. This style of solution construction will be well served by the techniques developed as part of this track. Please also see the associated Curriculum CTT technical report for a discussion of this issue.

Although a ‘weighted sum' evaluation function is not ideal e.g. it may have adverse side effects for certain individual students, it is the chosen method here due to the ease of implementation for purposes of comparison. It is hoped that the interest generated by efforts here will lead to true multi-objective evaluation of potential solutions. In particular, we specifically decided to include the weights in the data format itself rather than solvers having to hard code them. This at least ought to easily allow variations of the weights so as to explore multi-objective properties. Also, it is unlikely that every institution would have the same weights, and so fixing them in the solver seems inappropriate.

Problem Description

The problem consists of the following:

1. An examination session is made of a number of periods over a specified length of time i.e. examination session. Period lengths are provided.
2. A set of exams that are to be scheduled into a periods. Exam codes are not provided. As with all entities, competitors should assume sequential numbering beginning with 0.
3. A set of students enrolled on individual exams. Each student is enrolled on a number of exams. Students enrolled on an exam are considered to ‘take' that examination. For each exam, student numbers are provided.
4. A set of rooms with individual capacities are provided.
5. A number of Hard Constraints which must be satisfied
6. A number of Soft Constraints which contribute to a penalty if they are violated.
7. Details including a ‘weighting' of particular soft constraints.

Feasibility

A feasible timetable is one in which all examinations have been assigned to a period and room so that the following hard constraints are satisfied:

Hard Constraints

• No student sits more than one examination at the same time;
• The capacity of individual rooms is not exceeded at any time throughout the examination session;
• Period Lengths are not violated;
• Satisfaction of period related hard constraints e.g. Exam_A After Exam_B;
• Satisfaction of room related hard constraints e.g. Exam_A must use Room 101.

Soft Constraints

A candidate timetable is penalised for each occurrence of the following soft constraints:

• Two exams in a row;
• Two exams in a day;
• Specified spread of examinations;
• Mixed duration of examinations within individual periods;
• Larger examinations appearing later in the timetable;
• Period related soft constraints;
• Room related soft constraints;

These can effectively be split into two groups i.e. those which are resource specific and those which can have a global setting.

Resource Specific Settings

The following constraints can be set for each period and each room:

• period related soft constraints;
• room related soft constraints;

This allows control of how resources would be used in constructing a solution. Values for these can be found after the introduction of periods and rooms in the datasets.

Global Settings

The following constraints can be set relative to each other:

• Two exams in a row;
• Two exams in a day;
• Specified spread of examinations;
• Mixed duration of examinations within individual periods;
• larger examinations appearing later in the timetable;

Institutions may weight these soft constraints differently relative to one another in an attempt to produce a solution which is appropriate for their particular needs.  This is known as building the ‘Institutional Model' and is defined here as the Institutional Model Index;

Institutional Model Index

A relative weighting of the soft constraints which effectively provides a quality measure of the solution to be built. Within the datasets provided a number of variables are given with values. More information can be found in the Input Format section.

Last Updated: Tuesday, August 14, 2007 12:30 PM