International Timetabling Competition

In order to explain the calculation of the penalty a simple example is used allowing individual components of the overall penalty to be explained. At each stage within the following discussion, the overall penalty is calculated based on the description provided.

 

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

 

Firstly, we consider the hard constraints. If any of these are being violated then the solution will be disqualified.

 

Secondly, we consider the soft constraints

 

The number of soft constraint violations is calculated as follows;

 

Two Exams in a Row

Count the number of occurrences of students having two exams in a row and multiply then by standard settings dependent on the nature of the occurrence. If they are on the same day this should be multiplied by 3.  If there is an overnight involved the number of students should be multiplied by 2. If there is a weekend involved, the number of students should be multiplied by 1. In addition, this overall value  is subsequently multiplied by the ‘avoid two in a row’ weighting within the ‘Intuitional Model Index’. 

 

Example

 

An Examination session is two weeks long. Each day has three periods. 10 students have 2 exams in a row.  Five of them are on the same day, 3 of them have exams in the last period of day 1 and the morning period of day 2.  A further 2 of the students take an exam on the last period of a Friday and the first period on the following Monday.  When constructing the model, the Institution place a weighting of 7 on this TWOINAROW constraint within the ‘Intuitional Model Index’.

 

Two Exams in a Row Penalty =  ((5*3)+(3*2)+(2*1)) * 7

 

 

Overall Penalty  =  161

 

 

Two Exams in a Day

Count the number of occurrences of students having two exams in a day. This is subsequently multiplied by the weighting provided within the ‘Intuitional Model Index’. It should be noted that the occurrences here could have contributed to the penalty calculated for ‘two exams in a row’ penalty.  Although, in such cases, a single occurrence within the solution may be effectively penalised twice, it is necessary as many institutions require this to be minimised as an indication of solution quality

 

Example

 

20 students have 2 exams in a day. When constructing the model, the Institution place a weighting of 5 on this TWOINADAY constraint within the ‘Intuitional Model Index’.

 

Two Exams in a Day Penalty = (20*5) = 100

 

Overall penalty = Two exams in a row +Two exams in a day

 

Overall penalty  = 261

 

 

It should be noted that where the examination session contains days with 2 periods, this component of the penalty, although present for continuity, becomes superfluous.

 

 

Period Spread

We are interested in knowing the spread of examinations over a given period.  Within the ‘Intuitional Model Index’, a figure is provided relating to how many periods we should attempt to ‘optimise’ the solution over. The higher this figure, potentially the better the spread of examinations for individual students. In the example given, if the PERIOD_SPREAD value is 15 and an exam is placed on a Monday morning, then we will search every period of the week until the last period on the following Friday is reached. Each occurrence will be multiplied by a factor which depreciates as each period is searched.

 

Example:

 

10 student sits an exam on Monday morning, another on Wednesday morning and a third on Friday Afternoon. The PERIOD_SPREAD value within the ‘Intuitional Model Index’ is set to 15.

 

Penalty =  10 * (15-6) + 10 * (15-14) = 100

 

Overall Penalty = 261+100 = 361

 

 

 

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

Evaluation Function