Evaluation Function
Generally, a timetable's quality is reflected by two values: the number of hard constraint violations (Distance to Feasibility), and the number of soft constraint violations. In order to compare two solutions, first we will look at the Distance to Feasibility, and the solution with the lowest value for this will be the winner.
For the competition datasets, all solutions which are deemed acceptable should have a zero valus for this measure. When 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.
The Distance to Feasibility is the total of the following;
Conflicts: Two conflicting exams in the same period.
RoomOccupancy: More seating required in any individual period than that available.
PeriodUtilisation: More time required in any individual period than that available.
PeriodRelated: Ordering requirements not obeyed.
RoomRelated: Room requirements not obeyed
Although, the nature of the practical problem described here usually leads to feasibility being found quite easily, this is not necessarily always the case in practice. It was felt essential that this information was included here to allow solution evaluation to be consistent across all tracks of the competition and in order to establish an evaluation method that can be built upon for the future.
After checking that all hard constraints are satisfied, the solution will be classified based on the satisfaction of the soft constraints. These are the following;
Two Exams in a Row
Two Exams in a Day
Period Spread
Mixed Durations
Larger Exams Constraints
Room Penalty
Period Penalty
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. The total penalty for the soft constraint violations is calculated as follows:
Two Exams in a Row
Count the number of occurrences where two examinations are taken by students straight after one another i.e. back to back. Once this has been established, the number of students involved in each occurance should be added and multiplied by the number provided in the 奏wo in a row' weighting within the 選nstitutional Model Index'. Note that two exams in a row are not counted overnight e.g. if a student has an exam the last period of one day and another the first period the next day, this does not count as two in a row.
Example
An Examination session is two weeks long. Each day has three periods. Exam_A is in the first period of the first day and Exam_B is in the second period of the same day. 10 students take both Exam_A and Exam_B. Therefor, Between Exam_A and Exam_B there is a violation of the 'Two Exams in a Row' constraint. When constructing the Timetable model, the Institution place a weighting of 7 on this TWOINAROW constraint within the 選ntuitional Model Index'.
Two Exams in a Row Penalty = 10 * 7
Overall Penalty = 70
This should be calculated for each occurence where a student or students have two exams in a row within the same day. If for example, the same 10 students where taking a further exam, Exam_C, in the last period of the day then this is regarded as a seperate occurance and the penalty for this further violation would be calculated as above, thus doubling the overall penalty.
Two Exams in a Day
In the case where there are three periods or more in a day, count the number of occurrences of students having two exams in a day which are not directly adjacent, i.e. not back to back, and multiply this by the ' two in a day' weighting provided within the 'Institutional Model Index'. Therefore, two exams in a day are considered as those which are not adjacent i.e. they have a free period between them. This is done to ensure a particular exam placing within a solution does not contribute twice to the overall penalty. For example if Exam A and Exam B were in adjacent periods in the same day the penalty would be counted as part of the 'Two exams in a row penalty'.
Example
An Examination session is two weeks long. Each day has three periods. Exam_D is in the first period of the first day and Exam_E is in the third period of the same day. 20 students take both Exam_D and Exam_E. Therefor, Between Exam_D and Exam_E there is a violation of the 'Two Exams in a Day' constraint. When constructing the Timetable model, the Institution place a weighting of 5 on this TWOINADAY constraint within the 選ntuitional 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 = 170
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. When this is the case this portion of the penalty will always be equal to zero. It is also pointed out that with regards to the hypothetical situation described under the 'Two Exams in a Row' section above where the 10 students involved in the original constraint violation between Exam_A and Exam_B, also take Exam_C, the overall penalty would effectively be incremented twice due to the grouping of 10 students being involved in both the Two exams in a Row and Two exams in a Day constraints. It is obvious this is a very undesirable attribute of any solution.
Period Spread
This constraint allows an organisation to 'spread' an individual's examinations over a specified number of periods. This can be thought of an extension of the two constraints previously described. Within the 選nstitutional Model Index', a figure is provided relating to how many periods the solution should be 双ptimised' over. The higher this figure, potentially the better the spread of examinations for individual students. In many institutions constructing solutions while changing this setting has led to timetables which the Institution is much more satisfied with.
If for example PERIODSPREAD within the Institutional Model Index is set at 7, for each exam, we count all the occurrences of enrolled students who have to sit other exams afterwards but within 7 periods i.e. the desired period spread. This total is added to the overall penalty. It should be noted that the occurrences here will have contributed to the penalty calculated for the ‘two exams in a row' and 'two exams in a day' penalties. Although, a single occurrence within the solution is effectively penalised twice, it is often necessary due to, as indicated above, many institutions require certain spreads to be minimised as an indication of solution quality.
Example:
An Examination session is two weeks long. Each day has three periods. Exam_F is in the first period of the first day. Exam_G is in the first period of the second day and Exam_H is on the first period of the third day. 10 students take all three exams. The PERIOD_SPREAD value within the 選ntuitional Model Index' is set to 6.
The penalty caused by this instant of violation of the constraint is calculated as follows. Firstly 6 periods are counted from the starting period where Exam_F is timetabled. This period is counted as 0. As both Exam_G and Exam_H are within the timeframe described by this process, both be used in calculating the penalty. Both Exam_G and Exam_H contribute 10 to the penalty i.e. the number of students in common with Exam_F
Penalty = 10+10
= 20
Overall Penalty = 170+20 = 190
This should be calculated for each occurrence where a student or students takes exams within the number of periods specified by the PERIOD_SPREAD value within the 選ntuitional Model Index'.
Mixed Durations
This applies a penalty to a ROOM and PERIOD (not Exam) where there are mixed durations, such that:
For Each Period
For Each Room
Penalty = (number of different durations -1 ) * 'NONMIXEDDURATIONS' weighting
For example, if there were 6 exams of 120, 120, 180, 180, 180, 210 durations in Room A at period 0, then there are 3 different distinct durations, 120, 180, 210. The weighting within the 選ntuitional Model Index' is set to 10, therefore:
Penalty = (3-1) * 10 = 2 * 10 = 20, for that room at that period
*Note* Obviously if all the durations in the room in a period are the same, the number of distinct durations is 1, there penalty = (1-1) *10 = 0, which is correct
Overall Penalty = 190+20 = 210
Larger Exams towards the beginning of the examination session
It is desirable that examinations with the largest numbers of students are timetabled at the beginning of the examination session. In order to take account of this the FRONTLOAD expression is introduced. Within the
選ntuitional Model Index' the FRONTLOAD expression has three parameters e.g., 100, 30, 5
First parameter = number of largest exams. Largest exams are specified by class size
Second parameter= number of last periods to take into account
Third parameter= the penalty or weighting
In the example given, for each exam, if it is in the group of 100 largest AND it has been placed in a period which falls within the last 30 periods, then it incurs a penalty of 5.
Lets say within the example timetable scenario described as part of this description, 25 of the 100 largest exams are scheduled in the last 30 periods of the esamination session.
Penalty = 25*5 = 125
Overall Penalty = 210+125 = 335
Room Penalty
It is often the case that organisations want to keep certain room usage to a minimum. As with the 'Mixed Durations' component of the overall penalty, this part of the overall penalty should be calculated on a period by period basis. For each period, if a room used within the solution has an associated penalty, the penalty for that room for that period is calculated by multiplying the associated penalty by the number of times the room is used.
Example:
In a particular period, Exam_A and Exam_I are timetabled in a room in a particular period with an associated penalty of 60. The number of students is not important.
Room Penalty = 60*2 = 120
Overall Penalty = 335 + 120 = 455
Period Penalty
It is often the case that organisations want to keep certain period usage to a minimum. As with the 'Mixed Durations' and the 'Room Penalty' components of the overall penalty, this part of the overall penalty should be calculated on a period by period basis. For each period the penalty is calculated by multiplying the associated penalty by the number of times the exams timetabled within that period.
Example:
Exam_A and Exam_I are timetabled in a period with an associated penalty of 30. The number of students is not important.
Period Penalty = 30+30 = 60
Overall Penalty = 455 + 60= 515
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:43 PM