This page specifies an extended version of the XHSTT format called XESTT, which is used for employee scheduling. It is very similar to XHSTT, the format for high school timetabling, so only the differences between the two are given here.
Employee scheduling archive files
Employee scheduling abbreviated event resources
Employee scheduling cluster busy times constraints
Employee scheduling limit busy times constraints
Employee scheduling limit workload constraints
Limit active intervals constraints
Limit resources constraints
Employee scheduling archive files have almost the same format as high school timetabling archive files. The outermost tag is EmployeeScheduleArchive instead of HighSchoolTimetableArchive. The overall syntax is otherwise the same:
EmployeeScheduleArchive +Id
+MetaData
+Instances
*Instance
+SolutionGroups
*SolutionGroup
with the same meaning as for high school timetabling, except that the extensions defined on this page are available in employee scheduling archives but not in high school timetabling archives. HSEval accepts both kinds of archives without having to be told which kind to expect.
Employee scheduling instances can be very large. Much of the length is owing to event resources. Accordingly, XESTT offers the option of abbreviating their syntax. Instead of XHSTT's
Resources
*Resource
and
Resource +Reference
+Role
+ResourceType
+Workload
XESTT offers
Resources
*Resource
*R
where R is an abbreviated form of Resource:
R +Reference
As shown above, a Resource has four attributes, all optional: a preassignment, referenced by Reference, a role, a resource type, and a workload. In the abbreviated R form, Reference is as before; Role occupies the text body of R; ResourceType is omitted and is taken to be the first of the resource types of the instance; and Workload is omitted and is taken to be the workload of the enclosing event.
The employee scheduling cluster busy times constraint has syntax
ClusterBusyTimesConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
+ResourceHistory
+AppliesToTimeGroup
TimeGroups
Minimum
Maximum
+AllowZero
This is the high school timetabling cluster busy times constraint with four extensions. First, an optional ResourceHistory category has been added, with syntax
ResourceHistory before after
*Resource
where the before and after attributes each contain a non-negative integer, and Resource has syntax
Resource Reference
with a body containing a non-negative integer not larger than the before attribute of ResourceHistory. The reference may be to any resource, but only references to resources that are points of application of the constraint have any effect. A resource may not appear more than once in the ResourceHistory part of one constraint.
The second extension is that an optional AppliesToTimeGroup category has been added, which references a time group:
AppliesToTimeGroup Reference
The third extension is that the TimeGroups category has syntax
TimeGroups
*TimeGroup
as before, but the syntax of TimeGroup has been extended to
TimeGroup Reference +Polarity
The new element is the optional Polarity attribute, which must have value positive or negative; its default value is positive. A time group is said to be positive or negative, depending on the value of this attribute.
The fourth extension is the addition of the optional AllowZero child category. This has no attributes and no child categories of its own, just a body which must contain the value true or false. Its default value is false.Deviation. When the optional ResourceHistory and AppliesToTimeGroup child categories are not present, the deviation at one point of application of this constraint (one resource) is the amount by which the number of active time groups falls short of Minimum or exceeds Maximum. A time group is active if it is a positive time group and the resource is busy during that time group, or it is a negative time group and the resource is not busy during that time group. A resource is busy during a time group if it is busy at one or more of the times of the time group. Exception: if AllowZero is present with value true and the number of active time groups is 0, then the deviation is 0.
When the optional ResourceHistory child category is present, an xi value is found for each resource, which is the value of the body of the resource's entry in ResourceHistory, or if none, 0. And ai and ci values are found, which are the values of the before and after attributes of ResourceHistory (the same for each resource). Then, when comparing with a maximum limit and, when AllowZero is true, with zero, xi is added to the number of active time groups; and when comparing with a minimum limit, both xi and ci are added to the number of active time groups. Furthermore, an adjustment, which depends on ai, ci, and xi, is made to any reported cost of violation, to remove any double counting. Full details appear in Jeff Kingston's paper on modelling history in nurse rostering. In the literature, xi and ci are usually called the counter start value and the counter remainder value.
When the optional AppliesToTimeGroup child category is present, for each time ti in the applies-to time group, the constraint applies as defined without the applies-to time group, except that each time t in the time groups of TimeGroups is changed to the time index(ti) - index(t1) places further along the cycle, where t1 is the first time in the applies-to time group. If any of these times don't exist, the constraint does not apply at ti. One point of application of the constraint then becomes a pair consisting of a resource from AppliesTo and an applicable time from AppliesToTimeGroup. It is possible to include all these clones of the constraint directly, and not use AppliesToTimeGroup, but that can become very verbose.
This definition is compatible with the high school timetabling definition: every high school timetabling cluster busy times constraint is also a legal employee scheduling cluster busy times constraint, and when considered as such, its meaning does not change.
The employee scheduling limit busy times constraint has syntax
LimitBusyTimesConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
+AppliesToTimeGroup
TimeGroups
Minimum
Maximum
+AllowZero
This is the same as the high school timetabling limit busy times constraint, with two extensions. First, an optional AppliesToTimeGroup category has been added, which references a time group:
AppliesToTimeGroup Reference
Deviation. When the optional AppliesToTimeGroup child category is not present, the deviation at one point of application of this constraint (one resource) is the sum, over all time groups, of the amount by which the number of times that the resource is busy during that time group falls short of Minimum or exceeds Maximum. Exception: if AllowZero is absent or present with value true, and the number of times that the resource is busy in some time group is 0, then the contribution of that time group to the deviation is 0.
When the optional AppliesToTimeGroup child category is present, for each time ti in the applies-to time group, the constraint applies as defined without the applies-to time group, except that each time t in the time groups of TimeGroups is changed to the time index(ti) - index(t1) places further along the cycle from t, where t1 is the first time in the applies-to time group. If any of these new times don't exist, the constraint does not apply at ti. One point of application of the constraint then becomes a pair consisting of a resource from AppliesTo and an applicable time ti from AppliesToTimeGroup. It is possible to include all these clones of the constraint directly, and not use AppliesToTimeGroup, but that can become very verbose.
This definition is compatible with the high school timetabling definition: every high school timetabling limit busy times constraint is also a legal employee scheduling limit busy times constraint, and when considered as such, its meaning does not change.
The employee scheduling limit workload constraint has syntax
LimitWorkloadConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
+AppliesToTimeGroup
+TimeGroups
Minimum
Maximum
+AllowZero
This is the same as the high school timetabling limit workload constraint, with three extensions. First, an optional AppliesToTimeGroup category has been added, which references a time group:
AppliesToTimeGroup Reference
The second change is the addition of the optional TimeGroups child category, with syntax
TimeGroups
*TimeGroup
where TimeGroup has syntax
TimeGroup Reference
and references a time group, which could be a Day or Week.
The third change is the addition of the optional AllowZero child category. This has no attributes and no child categories of its own, just a body which must contain the value true or false. Its default value is false.
Deviation. When the optional AppliesToTimeGroup child category is not present, the deviation at one point of application of this constraint (one resource) is the sum, over all time groups, of the amount by which the total workload of the solution resources assigned that resource during that time group falls short of Minimum or exceeds Maximum. Each amount is rounded up to the next integer before being added to the sum. If there are no time groups, a single time group containing all the times of the cycle is used instead. Exception: if AllowZero is present with value true, and the total workload of the resource during some time group is 0.0, then the contribution of that time group to the deviation is 0.
The contribution of one solution resource to the workload during one time group is calculated as follows. First, divide the workload of the solution resource's event resource by the duration of that event resource's event to obtain the workload per time (a floating-point number). Then the contribution is the workload per time multiplied by the number of times that the solution resource shares with the time group. When the workload per time is not an integer, the usual roundoff errors associated with floating-point numbers may occur, especially during solving when the total workload undergoes many incremental adjustments.
When the optional AppliesToTimeGroup child category is present, for each time ti in the applies-to time group, the constraint applies as defined without the applies-to time group, except that each time t in the time groups of TimeGroups is changed to the time index(ti) - index(t1) places further along the cycle from t, where t1 is the first time in the applies-to time group. If any of these new times don't exist, the constraint does not apply at ti. One point of application of the constraint then becomes a pair consisting of a resource from AppliesTo and an applicable time ti from AppliesToTimeGroup. It is possible to include all these clones of the constraint directly, and not use AppliesToTimeGroup, but that can become very verbose.
This definition is compatible with the high school timetabling definition: every high school timetabling limit workload constraint is also a legal employee scheduling limit workload constraint, and when considered as such, its meaning does not change. It is identical to the employee scheduling limit busy times constraint except that TimeGroups is optional, the default value of AllowZero is different, and workload is limited rather than the number of busy times.
For the limit busy times constraint and other resource constraints, a clash at some time only counts as one busy time. However, for the limit workload constraint, the contributions of all clashing solution resources are included. This is more or less unavoidable, since counting just one would raise the question of which one to choose. The choice matters when workloads per unit time differ.
The limit active intervals constraint is a whole new constraint, not present in the high school model. In the global list of all constraints, limit active intervals constraints come after limit workload constraints.
The limit active intervals constraint has almost the same syntax as the employee scheduling cluster busy times constraint:
LimitActiveIntervalsConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
+ResourceHistory
+AppliesToTimeGroup
TimeGroups
Minimum
Maximum
The only syntax differences are the change of name, from ClusterBusyTimesConstraint to LimitActiveIntervalsConstraint, and the absence of AllowZero. Each of the child categories shown has the same syntax and the same validity rules as it does for the employee scheduling cluster busy times constraint.
Deviation. When the optional ResourceHistory and AppliesToTimeGroup child categories are not present, the cost at one point of application of this constraint (one resource) is the sum, over all active intervals I, of the cost of the deviation of I. The deviation of I is the amount by which the length of I falls short of Minimum or exceeds Maximum. An active interval is a non-empty sequence of consecutive active time groups (consecutive with respect to the order that the time groups appear in the constraint) of maximal length. For the meaning of `active time group', consult the specification of the employee scheduling cluster busy times constraint.
When the optional ResourceHistory child category is present, ai, ci, and xi values are found for each resource, as described for the employee scheduling cluster busy times constraint. Then, if xi is non-zero, a virtual active interval of length xi is added just before the first time group. Its cost is included in the total cost, and it merges with the first real active interval when that interval includes the first time group. An active interval whose last time group is the constraint's last time group has its length increased by ci, although only when comparing with a minimum limit. Furthermore, an adjustment, which depends on ai, ci, and xi, is made to any reported cost of violation, to remove any double counting. Full details appear in Jeff Kingston's paper on modelling history in nurse rostering. In the literature, xi and ci are usually called the counter start value and the counter remainder value.
When the optional AppliesToTimeGroup child category is present, its effect is the same as for the employee scheduling cluster busy times constraint.
In summary, the limit active intervals constraint is the same as the cluster busy times constraint except that the limits apply to the lengths of the active intervals instead of to the total number of active time groups, and history only affects the lengths of active intervals at the ends of the monitored range. AllowZero is omitted because an active interval cannot have length 0.
The limit active intervals constraint is an exception to the rule that cost is calculated by first calculating one deviation and then applying the cost function to it. That interacts badly with history. Instead, as explained above, a deviation is calculated for each active interval, and the cost is the sum of the costs of those deviations.
The limit resources constraint is a whole new constraint, not present in the high school model. It generalizes the assign resource and prefer resources constraints. In the global list of all constraints, limit resources constraints come after limit active intervals constraints.
The limit resources constraint has syntax
LimitResourcesConstraint Id
Name
Required
Weight
CostFunction
AppliesTo
+ResourceGroups
+Resources
+Minimum
+Maximum
Roles
AppliesTo has syntax
AppliesTo
+EventGroups
+Events
EventGroups has syntax
EventGroups
*EventGroup
and EventGroup has syntax
EventGroup Reference
Events has syntax
Events
*Event
and Event has syntax
Event Reference
ResourceGroups and Resources are as for the prefer resources constraint. Maximum and Minimum each have a body only (no attributes or children), containing a non-negative integer. When both are present, the value of Minimum may not exceed the value of Maximum. Roles has syntax
Roles
*Role
Each Role has a body only.
Each Event is taken to specify an event group containing just that one event. Each event group is one point of application; the individual events of the event groups are not the points of application. The event groups referenced may be defined as Courses. Having event groups as points of application allows the constraint to coordinate resource assignments to a whole set of events.
Deviation. The deviation at one point of application of this constraint (one event group) is calculated as follows. Form the set of all solution event resources whose corresponding instance event resources lie in one of the events of the event group and have one of the given roles, and which are assigned a resource from ResourceGroups or Resources. The deviation is the amount by which the total duration of these solution event resources falls short of Minimum (if present) or exceeds Maximum (if present).An assign resource constraint can be expressed as a limit resources constraint, whose resources are all resources of the appropriate type, with minimum limit equal to the total duration of the event resources which are the points of application. A prefer resources constraint can also be expressed as a limit resources constraint, whose resources are all the resources of the appropriate type which are not preferred in the prefer resources constraint, with maximum limit 0. These conversions shed a useful light on the relationships between these constraints, but assign resource and prefer resources constraints are preferred in practice, because they treat the event resources they apply to independently, and so they are fundamentally simpler.
Return to the HSEval home page.