Documentation

Constraints The names of the constraints have been made more uniform in Version 9: all constraint start with a verb, and describe how the constraint is not violated. From Version 10 all events of duration 2 and longer can be split in sub-events. The SplitEventConstraint describes the basic properties of splitting.

Common properties

All constraints have the following properties:

  • An Id for referencing.

  • A Name for displaying.

  • Required, a boolean. If "true" the constraint is considered a hard constraint. The cost will contribute to the infeasibilty value. If "false" the constraint is soft, and the cost will contribute to the objective value. Instances should be encoded on the understanding that violations of hard constraints are serious defects, and that solvers aim to find solutions with very few hard constraint violations. Although the existence of such solutions is not guaranteed, realistic instances should have them. On the other hand, violations of soft constraints are normal and to be expected.

  • A Weight. This is a multiplicative factor for the cost calculation.

  • A CostFunction. This CostFunction describes how the Deviations of the constraint is treated for the cost calculation, by the formula: Cost = Weight * CostFunction( Deviations ). Here the Deviations are non-negative integers describing how much the constraint is violated. At present there are five possibilities for the cost function:

    • CostFunction = "SumSteps". The value is the number of strictly positive Deviations.

    • CostFunction = "StepSum". The value is 1 if one of the Deviations is strictly positive, and 0 otherwise.

    • CostFunction = "Sum". The value is the sum of the (positive) Deviations.

    • CostFunction = "SumSquares". The value is the sum of the squared (positive) Deviations.

    • CostFunction = "SquareSum". The value is the square of the summed (positive) Deviations.

  • AppliesTo. This describes the objects for which the constraint applies to; the generated cost is attributed to these objects. For most constraints the AppliesTo consists of resources, and the constraint applies to each of these resources. Some constraints apply to events, and some to a group of events.

We divide the constraints in three groups. The first group contains the scheduling constraints. These constraints describe how the scheduling must be done. The remaining constraints accept a schedule, and calculate the cost for it. These constraints are divided into 'event constraints' and 'resource constraints'. These names reflect where the cost is attributed.

Scheduling constraints

We have two types of scheduling, for which there is a corresponding constraint: the AssignResourceConstraint expresses that to certain roles in certain events a resource should be assigned. The AssignTimesConstraint expresses that certain events should have a time assigned. Moreover there is the constraint "SplitEventsConstraints", which describes how events can be split in sub-events.

AssignResourceConstraint

  • Description. For each selected event assign a resource to the selected role.

  • AppliesTo: Events or EventGroups. The constraint applies to each separate event.

  • Parameters:

    • Role. This fixes the resource to assign in the event.

  • Deviation. Check for each sub-event whether the resource in this role is assigned. If the resource is not assigned, the deviation is the duration of the sub-event.

  • Extra information. The constraint describes that a resource should be assigned in this role. If the selected role is not present in the event, the constraint skips this event. If the resource is already present in the event (the resource is preassigned) the constraint skips this event as well. Note that all assignments have to respect the resource type; if not the solution is invalid.

AssignTimeConstraint

  • Description. For each selected event assign a time.

  • AppliesTo: Events or EventGroups. The constraint applies to each separate event.

  • Deviation. For each sub-event check if the time is assigned. If the time is not assigned, the deviation for the sub-event is the duration.

  • Extra information. Note that this constraint is used to describe that a time should be scheduled to an event. If we have an event of duration 2, we the time will be the starting time of the event. The constraint skips all events in which the time is already present (the time is preassigned).

SplitEventsConstraint

  • Description. For each selected event the possibilities of splitting are given.

  • AppliesTo: Events or EventGroups. The constraint applies to each separate event.

  • Parameters:

    • MinimumDuration. The minimum duration of each of the sub-events.

    • MaximumDuration. The maximum duration of each of the sub-events.

    • MinimumAmount. The minimum number of sub-events.

    • MaximumAmount. Then maximum number of sub-events.

  • Deviations. The number of sub-events below minimum amount or above maximum amount, plus the number of sub-events whose duration is less than minimum duration or more than maximum duration.

  • Extra information. All events of duration 2 or more can (in principle) be split. This constraint describes the basic limitation on the splitting of events. A split event occupies consecutive times; this we call a sub-events. Hence: in the solution the event appears exactly once for each of its sub-events: if more than one sub-event exists, the duration must be added to each these sub-events. A solution can contain only one resource per role, implying that all times within a single sub-event the same resources are assigned to it. In contrast different sub-events of an event can have other resources.

Other event constraints

DistributeSplitEventsConstraint

  • Description. For each selected event prescribe in how many sub-events of a certain duration the event should be split.

  • AppliesTo: Events or EventGroups. The constraint applies to each separate event.

  • Parameters:

    • Duration. The duration of the sub-event.

    • Minimum. The minimum number of sub-events of the given duration.

    • Maximum: The maximum number of sub-events of the given duration.

  • Deviation. For each of the given events find the number of sub-events of the given duration. The deviation is the deviation of this amount from the given minimum and maximum.

  • Extra information. This constraint will use the sub-events as given in the solution. In principle several sub-events could be scheduled consecutively. This constraint will ignore that, i.e. will not consider such sub-events to be one sub-event of the summed duration.

PreferResourcesConstraint

  • Description. For each selected event assign one of the selected resources to the selected role.

  • AppliesTo: Events or EventGroups. The constraint applies to each separate event.

  • Parameters:

    • Role. This fixes the resource to assign in the event.

    • ResourceGroups or Resources. We can choose the resource for Role from the resources in the listed resource groups or resources.

  • Deviation. Check for each sub-event whether the resource in this role is in the selected resources. If this resource is assigned, but not among the selected resources, the deviation is the duration of the sub-event.

  • Extra information. Note that the constraint describes the resources that can be assigned in this role. If the selected role is not present in the event, or the resource is preassigned, the constraint skips this event.

  • Example. If there are preferences among the resources, we can use this constraint more than once. The PreferredResourcesConstraint will add cost for not selecting from one of the selected (preferred) resources.

  • Extra information. The deviation is 0 if the resource is not assigned.

PreferTimesConstraint

  • Description. For each selected event assign the time to one of the selected times.

  • AppliesTo: Events or EventGroups. The constraint applies to each separate event.

  • Parameters:

    • TimeGroups or Times: the preferred times.

    • Duration (optional): if the duration is given, the constraint is only checked if the sub-event is of the given duration.

  • Deviation. For each sub-event check if the time in the selected times. If the time is assigned to a time that was not selected in the constraint, the deviation is the duration of the sub-event.

  • Extra information. The deviation is 0 if the time is not assigned. The constraint skips all events in which the time is already present (the time is preassigned).

AvoidSplitAssignmentsConstraint

  • Description. For each selected event group schedule the role of the events of this event group to the same resource.

  • AppliesTo: EventGroups. The constraint applies to each of the selected event groups.

  • Parameters:

    • Role. The identification of the resource for which the constraint should be evaluated.

  • Extra information. Unassigned resources are ignored.

  • Deviation. For each selected event groups the evaluation considers the resources assigned to the selected role in the events of the group. The deviation is the number of distinct resources above 1.

SpreadEventsConstraint

  • Description. The number of times that events of a selected event group are scheduled in one of the selected time groups should lie between the minimum and maximum for this time group.

  • AppliesTo: EventGroups. The constraint applies to each of the selected event groups.

  • Parameters:

    • TimeGroups. The time groups that the events should be spread through, each accompanied by a Minimum and Maximum value.

      So for each of these time groups:
      • Minimum. The minimum number of events of the event group in this time group.

      • Maximum: The maximum number of events of the event group in this time group.

  • Example. It is common that lessons of one course should be on different days. In this case, the time groups will contain all times of one day, the minimum is always 0, and the maximum is always 1, and the event groups are the courses.

  • Deviations. For each event group check how many events of the event group have a starting time which lies in the time group. The deviation is the number below the minimum, or above the maximum of the time group.

LinkEventsConstraint

  • Description. For each selected event group schedule the events at the same times.

  • AppliesTo: EventGroups. The constraint applies to each of the selected event groups.

  • Deviation. The deviation is the number of distinct times that appear in at least one of the linked events but not in all of them.

  • Extra information. Linking event groups with different total durations will always lead to a deviation (if all times are assigned).

Resource constraints

AvoidClashesConstraint

  • Description. Schedule each of the selected resources without clashes.

  • AppliesTo: ResourceGroups or Resources.The constraint applies to each of the selected resources.

  • Deviations. For each time find the number of events, scheduled at this time, in which the resource is present in one of the resources or resource groups of the event . If this number of events exceeds 1, the excess is a deviation for this time.

AvoidUnavailableTimesConstraint

  • Description. For the selected resources avoid the use of each of the selected times.

  • AppliesTo: ResourceGroups or Resources.

  • Parameters:

    • TimeGroups or Times: The times that should be avoided.

  • Deviation. For each resource the number of assigned times among the selected ones.

LimitIdleTimesConstraint

  • Description. For each of the selected resources the total number of idle times summed over the selected time groups should lie between a minimum and a maximum. Typically the time groups are the days.

  • AppliesTo: ResourceGroups or Resources. The constraint applies to each of the selected resources.

  • Parameters:

    • TimeGroups. The groups of times that have to be checked for idle times. Within the time group, a resource has an idle time if the resource is idle (without event) at the time, while busy (with event) on an earlier and later time within the same time group. Earlier and later are determined by the sequence numbers of the times.

    • Minimum: The minimum number of idle times.

    • Maximum: The maximum number of idle times.

  • Deviation. For each resource count the total number of idle times (the sum of idle times in the separate groups). The Deviation is the total number of idle times, below the minimum, or above the maximum.

ClusterBusyTimesConstraint

  • Description. For each of the selected resources the number of time groups with at least one assigned time should lie between the minimum and the maximum. Typically the time groups are days, for example a teacher requiring at most 3 days with lessons.

  • AppliesTo: ResourceGroups or Resources. The constraint applies to each of the selected resources.

  • Parameters:

    • TimeGroups. The time groups that contribute to the count.

    • Minimum. The required minimum number of groups with at least one time assigned.

    • Maximum. The required maximum number of groups with at least one time assigned.

  • Deviation. For each of the selected resources the number of used time groups above the maximum, or below the minimum.

LimitBusyTimesConstraint

  • Description. For each of the selected resources the number of occupied times should lie between a minimum and a maximum in each of the selected time groups, OR the number of occupied times is 0 for this group. Typically the time groups are the days.

  • AppliesTo: ResourceGroups or Resources.The constraint applies to each of the selected resources.

  • Parameters:

    • TimeGroups. The time groups that should be checked for minimum or maximum number of assigned times.

    • Minimum. The required minimum number of times assigned in each of the time groups.

    • Maximum. The required maximum number of times assigned in each of the time groups.

  • Deviations. For each of the selected resources each time group with assigned times for this resource has a deviation, being the number of times assigned, below the minimum, or above the maximum.

LimitWorkloadConstraint

  • Description. For each of the selected resources schedule workload between a minimum and a maximum. Note that the workload is a property of a sub-event. If missing, we assume that the duration is the workload, otherwise the workload property will be used: if the event is split each sub-event will have the original workload. We find all events of the selected resources and check if the total workload is in the given range.

  • AppliesTo: ResourceGroups or Resources. The constraint applies to each of the selected resources.

  • Parameters:

    • Minimum. The required minimum workload.

    • Maximum. The required maximum workload.

  • Deviation. The amount (integer) by which the workload is above the maximum, or below the minimum.


Last modified: July 13, 2010

Valid HTML 4.0 Transitional