International Timetabling Competition

Timetable Evaluation

To check the value of a solution we do the following:

First, we consider the hard constraints. If any of these are being violated then the solution will be disqualified. However, you are allowed to leave certain events unplaced (i.e. not assigned to the timetable). This means that if you have chosen to use an algorithm that allows hard constraint violations during a run, then you will need to use a procedure at the end of your program that un-assigns some of the events, leaving you with a timetable that has no hard constraint violations.

If there are events that are not assigned to the timetable, we calculate the following Distance to Feasibility measure:

Identify the number of students that are required to attend each of the unplaced events.

The Distance to Feasibility is simply the total of these numbers.

For example, if your solution has left three events unplaced, and the number of students in each of these is 12, 8, and 5, then the

Distance to Feasibility of the solution is = (12 + 8 + 5 ) = 25.

The number of soft constraint violations is calculated as follows (note: this is the same as the previous competition):

Count the number of occurrences of a student having just one class on a day (e.g. count 2 if a student has two days with only one class).

Count the number of occurrences of a student having more than two classes consecutively (3 consecutively scores 1, 4 consecutively scores 2, 5 consecutively scores 3, etc). Classes at the end of the day followed by classes at the beginning of the next day do not count as consecutive.

Count the number of occurrences of a student having a class in the last timeslot of the day.

Sum the three counts to give the solution score.

A timetable's quality is therefore reflected by two values: the Distance to Feasibility, and the number of soft constraint violations. In order to compare two solutions, we will use the following procedure:

First, we will look at the solution's Distance to Feasibility. The solution with the lowest value for this will be the winner.

If the two solutions are tied, we will then look at the number of soft constraint violations. The winner will be the solution that has the lowest value here.

We advise you to make use of the solution checking program in order to make sure that you have understood the constraints.


Last Updated: Monday, July 30, 2007 10:50 PM