HSEval Version 2.1 (May 2018)

Employee Scheduling File Format Specification

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

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 abbreviated event resources

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.


Employee scheduling cluster busy times constraints

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.


Employee scheduling limit busy times constraints

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

The second 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 true. (For compatibility with the high school model, this default value is different from the default value of the AllowZero child category of the cluster busy times constraint. What is new here is not the ability to allow zero, but the ability to disallow it.)

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.


Employee scheduling limit workload constraints

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, rounded up to the next integer. 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.


Limit active intervals constraints

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 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.


Limit resources constraints

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. 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.


HSEval Software Copyright Jeffrey H. Kingston 2012