List of terms used in the benchmarks and its explanation
Assignment. If we decide to add a time or a resource to an event, we call this an assignment.
Clash. If a resource is used more than once at a certain time, we call it a clash (at that time). Here 'use' means that the resource occurs in a event (either as resource or in one of the resource groups) and the event is scheduled at the time of clash.
Class. A recommended resource type, representing a group of students that are not considered individually.
Compact. A schedule for a resource is called compact, if it contains no idle times. The idle times here are taken with respect to the days.
Constraint. The collection of hard and soft constraints of the instance, see the constraints document.
Cost. The cost is the abstract term for penalty calculated by one or more constraints. There are two types of costs around, corresponding the 'hard' constraints and 'soft' constraints, respectively. The first type leads to cost in the 'FeasibilityValue'. This is the cost calculated by all constraint for which 'Required' is "true". The second type of constraints attributes cost to the 'ObjectiveValue'. Both types of cost are determined by the 'Deviation', the 'CostFunction', and the 'Weight'. Our objective always is to minimize the 'FeasibilityValue' first, and secondly the 'ObjectiveValue'.
CostFunction. The 'CostFunction' describes how the deviation(s) of a violation translates to a cost, by the formula: Cost = Weight * CostFunction( Deviations ). We consider 5 cost functions:
CostFunction = 'SumSteps'.
CostFunction = 'StepSum'.
CostFunction = 'Sum'.
CostFunction = 'SumSquares'.
CostFunction = 'SquareSum'.
Course. A course is a specialized event group, introduced only for structuring (or displaying) the data. There is no functional difference between a course and any other event group: if a constraint has the possibility to set event groups, we can choose any of the courses as well. An event can have one preferred event group called 'Course'.
Day. A day is a specialized time group, introduced only for structuring (or displaying) the data. There is no functional difference between a day and any other time group: if a constraint has the possibility to set time groups, we can choose any of the days as well. A time can have one preferred time group called 'Day'.
Deviation. The amount by which a constraint is violated. Note that some constraints generate one number as deviation, while others generate a list of Deviations. A single deviation is treated as a list deviations of length 1. Throughout we assume that the deviation is always a non-negative integer, and that deviation = 0 means no violation, and hence cost = 0. An good example is the IdleTimesConstraint. Suppose a resource has 4 idle times, while the Maximum was set at 1: hence the deviation is 3. If the weight is 10, and the 'CostFunction' is 'SquareSum' or 'SumSquares', then the corresponding cost is 10 * 3^2 = 90.
Deviations. Some constraints naturally generate a vector of deviations, for example the TimeAmountConstraint, where we calculated per time group (day) the deviation above the maximum or below the minimum. The costfunction works on this vector of deviations, either by summing first the separate deviations (StepSum, Sum, SquareSum), or by summing separate contributions (SumSteps, Sum, SumSquares).
Duration. The number of times an event needs for scheduling. The event can be split in sub-event (solution events) with durations that add up to the (instance) event. If a time is assigned to a sub-event, the sub-event is automatically scheduled to this time, but also to the next times, as described by the duration. Usually it is assumed that these times belong to the same day.
Event. The basic object to schedule; generalisation of the 'lesson', to include other meetings, or 'linked' lessons. An event can have a duration 1 or higher. If the duration is 2 or more the event can be split to so-called sub-events. A sub-event is define by the solution: each time the Id of the original event appears in the solution, this is a sub-event. Except the duration ALL properties of the event are copied to the sub-events. In particular preassigned times and resources, as well as the workload are copied.
Feasible. We call a 'Solution' feasible if the 'InfeasibilityValue' is 0, i.e. the hard constraint generate no cost.
Id. The identification for an object; the Id should be unique within the entire document. The evaluator accepts any unique string (not verifying the specifications of xml id).
Idle time. We can speak of an idle time of a resource only with respect to a time group. An 'idle time' is a time that the resource is not schedule, while before and after this time the resource has a scheduled times within the given time group. Often the time group is a day, and we omit the reference to the time group, see also 'compact'.
InfeasibilityValue. The cost of all constraints that are 'Required' (Required = "true"), often called the hard constraints. The schedule is feasible, if and only if this value is 0.
Instance. An example of a timetabling problem in the format we describe here.
Lesson. An event for which a course is set. All event that contain a certain course, we call the lessons of this course.
Linked. We call two events linked, if there is a (required) constraint (of type LinkedEventsConstraint) expressing that they should start at the same time.
Name. Property of all object, only used for displaying the object; can be any string.
ObjectiveValue. The cost of all constraints that are not 'Required' (Required = "false").
Reference. Refers to the object with the corresponding Id.
Required. Boolean property of each constraint. If "true", the constraint is a hard constraint, if "false" a soft constraint. If the constraint is hard, the cost it generates contributes to the infeasibility value, otherwise to the objective value.
Resource. Typically objects for which the use is restricted in time, for example students, teachers or rooms. Normally a resource can be used once per time; violating this we call a clash. The corresponding constraint is NoResourceClashesConstraint. In the event there can be several Resources; if these are not preassigned, they require a role and a resource type.
ResourceType. The resource type is a division of all resources: it is obligatory to assign a type to each resource. (Note however that one could introduce just one type like 'General', and add this type to all resources). The reason for introducing resource types is structuring and displaying. The recommended use is to introduce at least two or three types: one for the teachers (type 'Teacher'), one for the students (type 'Student' or 'Class'), and, if rooms play a role, one for the rooms (type 'Room'). The resource in the event can specify a role: in this case the role has to be unique. The event resource always specifies the resource type. Instances or solutions with a resource of another resource type are considered invalid. It is required that all resource group are homogeneous with respect to the resource type, i.e. in a resource group there should be resources of exactly one type. For this reason the ResourceGroup has to specify the resource type.
Role. A qualification given to the resources in an event, to be able to distinguish them. Within an event, there can be at most one resource in the same role. If the resource in the event is preassigned, then the role is optional, otherwise it is compulsory. Constraints can ask to consider the resources in a given role, like the AssignResourcesConstraint. The resources the are member of a resource group are treated as resources of the event without role, of which there can be more than one.
Room. A recommended resource type.
Sub-event. See also 'event'. A sub-event is created in the solution. It copies all properties of the event, but the solution can assign a duration, a time (if it was not preassigned) and a resource in each of the existing roles (if it was not preassigned in the event). If the duration is not assigned to the sub-event, the duration is copied from the event (in this case there is only 1 sub-event). The durations of the sub-event of an event have to add up to the duration of the event; if the event doe not appear in the solution, then it is assumed that the event is not split. (Probably such event is fixed in time and resources, hence this assumption makes sense.)
Student. A recommended resource type.
Teacher. A recommended resource type.
Time. The basic unit of time, that we use, sometimes called a 'time slot'. Times are ordered by the order in the instance: this is needed for idle times calculation. To the time one can add two properties, namely 'Day' and 'Week', representing specialized time groups.
Violation. If a constraint has a non-zero deviation, we call this a violation of the constraint.
Week. A week is a specialized time group, introduced only for structuring (or displaying) the data. There is no functional difference between a week and any other time group: if a constraint has the possibility to set time groups, we can choose any of the weeks as well. A time can have one preferred time group called 'Week'.
Weight. Used to calculate the cost of a violation of a constraint as multiplicative factor.
Workload. Generalisation of the duration of an event to be able to divide events over resources in the WorkLoadAssignmentConstraint. If the workload attribute is missing, the duration is used instead. The workload is copied to all sub-events of an event (spreading of workload is only supported via the duration).
Last modified: July 13, 2010