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 |