HSEval Version 2.8 (March 2023)

High School Timetable Data Format Specification

This page contains the official specification of XHSTT, the format of the high school timetable files used by HSEval. (For employee scheduling, click here.) Each file contains one archive, specified in XML as defined below.

    Archives
        Instances
            Times
            Resources
            Events
            Constraints
        Solution Groups
            Solutions
                Reports
    Glossary

Instances

An instance is one occurrence of the high school timetable problem, for a particular school in a particular year (or semester, etc.). The syntax of instances is

Instance Id MetaData Times Resources Events Constraints

Many categories have an Id attribute. Wherever one appears, its value is always a string, called an identifier and used to refer to its category from elsewhere within the file. For more information about identifiers, consult the Identifier glossary entry.

The MetaData category holds information describing the provenance of the instance. Its syntax is

MetaData Name Contributor Date Country Description +Remarks

The child categories each hold text only. They give the name of the instance (which should identify the school and the year or semester), the name of the person who contributed it, the date it was contributed, the country in which its school is located, a description which will be printed when displaying the instance, and some optional remarks.

Times

The format supports only a simple model of time, in which time is broken into intervals called times which are assumed to not overlap. The Times child category of Instance defines these times. Its syntax is

Times +TimeGroups *Time

The optional TimeGroups category declares time groups, which are sets of times. Its syntax is

TimeGroups *Week *Day *TimeGroup

The syntax of TimeGroup is

TimeGroup Id Name

It declares a time group with the given Id and Name. For example,

<TimeGroup Id="BeforeLunch"> <Name>BeforeLunch</Name> </TimeGroup>

declares a time group which presumably will contain those times which are just before lunch. A time group's times are added to it later, as they are declared (see below).

Many categories contain Id and Name elements. In all cases, Id is an attribute whose value is a string used to refer to the category from elsewhere in the file, while Name is a child category containing just text, which names the category and is used when displaying it.

Categories Week and Day have the same syntax as TimeGroup and also define time groups. When present, they allow display software to determine how the times of an instance are grouped into weeks and days. They are optional, and solvers should not rely on their presence.

The Time child categories of Times define the times of the instance. Their order is significant: it reflects their ordering in time. An interval of real time has a starting moment and a duration, but these properties are not part of the time model used here. The syntax of times is

Time Id Name +Week +Day +TimeGroups

where the syntax of TimeGroups is

TimeGroups *TimeGroup

and the syntax of TimeGroup is

TimeGroup Reference

TimeGroup contains a Reference attribute only (no children or text). The value of this attribute must equal the Id of a time group declared earlier; the meaning is that the enclosing time is a member of that time group.

The syntax of the Week and Day child categories is the same as the syntax of TimeGroup. Their Reference attributes must contain the Ids of Week and Day time groups declared earlier. Overall, the syntax allows each time to lie in one week, one day, and any number of other time groups. For example,

<Time Id="Mon4"> <Name>Mon4</Name> <Day Reference="Monday"/> <TimeGroups> <TimeGroup Reference="BeforeLunch"/> </TimeGroups> </Time>

defines one time lying in the Monday and BeforeLunch time groups.

Resources

Resources are entities which attend events. They are typically teachers, rooms, and student groups or individual students, but any types of resources may be used. The Resources child category of Instance defines these resources. Its syntax is

Resources +ResourceTypes +ResourceGroups *Resource

The syntax of ResourceTypes is

ResourceTypes *ResourceType

where each ResourceType category defines one resource type, and has syntax

ResourceType Id Name

For example,

<ResourceTypes> <ResourceType Id="Teacher"> <Name>Teacher</Name> </ResourceType> <ResourceType Id="Room"> <Name>Room</Name> </ResourceType> <ResourceType Id="Class"> <Name>Class</Name> </ResourceType> </ResourceTypes>

defines three typical resource types. Although any identifiers and names may be used, it is recommended that Teacher, Room, Class, and Student be used whenever appropriate.

The optional ResourceGroups child category of Resources defines resource groups, which are sets of resources of the same type. Its syntax is

ResourceGroups *ResourceGroup

where the syntax of ResourceGroup is

ResourceGroup Id Name ResourceType

This contains the usual Id and Name elements, plus a compulsory ResourceType child category whose syntax is

ResourceType Reference

where the value of Reference is the identifier of a ResourceType category, and indicates that the elements of the resource group must all have that type. The resources themselves are added to the resource group later, as they are defined. For example,

<ResourceGroup Id="ScienceLab"> <Name>ScienceLab</Name> <ResourceType Reference="Room"/> </ResourceGroup>

defines a ScienceLab resource group whose elements are rooms.

Each Resource child category of Resources defines one resource, an entity that attends events. (Times are not considered to be resources.) Its syntax is

Resource Id Name ResourceType +ResourceGroups

where the syntax of ResourceGroups is

ResourceGroups *ResourceGroup

and the syntax of ResourceGroup is

ResourceGroup Reference

Altogether, this defines a resource with the given identifier, name, and type, and specifies which resource groups the resource lies in. For example,

<Resource Id="r03"> <Name>r03</Name> <ResourceType Reference="Room"/> <ResourceGroups> <ResourceGroup Reference="LargeRoom"/> <ResourceGroup Reference="ScienceLab"/> </ResourceGroups> </Resource>

defines a resource of type Room lying in resource groups LargeRoom and ScienceLab.

Events

An event (also called an instance event) is a meeting between resources. It specifies that the resources should meet together for a given number of times. This number is an integer called the duration of the event. The actual times and resources may be preassigned to the event, or they may be left open for a solver to assign, subject to constraints.

Events lie within the Events child category of Instance, whose syntax is

Events +EventGroups *Event

Similarly to the Times and Resources categories, this syntax first allows event groups (sets of events) to be defined, followed by the events themselves. The syntax of EventGroups is

EventGroups *Course *EventGroup

The syntax of EventGroup is

EventGroup Id Name

This declares an event group with the given identifier and name. As with other groups, the events themselves are added to the event group later, as they are declared.

In the same way as Week and Day are alternative forms for TimeGroup, Course is an alternative form for EventGroup. Presumably, events declared to lie in the same Course constitute a course of study in one subject for one group of students. Courses are optional, however, and solvers should not rely on their presence.

The syntax of Event is

Event Id +Color Name Duration +Workload +Course +Time +Resources +ResourceGroups +EventGroups

The Id and Name elements assign an identifier and name to the event in the usual way. The optional Color attribute specifies a colour to be used in the background of the event in printed timetables. Its value is as usual for Web colours, i.e. a colour name or #RRGGBB. The Duration child category defines the duration of the event. It has no attributes or child categories, and its body must consist entirely of an integer whose value is at least 1.

The optional Workload child category defines a workload for the event. If absent, the workload defaults to the duration. If present, Workload has no attributes or child categories, and its body consists entirely of an integer whose value is at least 0. A full explanation of workloads appears in the specification of the limit workload constraint.

The optional Course child category has syntax

Course Reference

and specifies that the event lies in the referenced course. Similarly, the optional EventGroups child category has syntax

EventGroups *EventGroup

where EventGroup has syntax

EventGroup Reference

and specifies that the event lies in the referenced event groups.

The optional Time child category is used only when the event has a preassigned time. Its syntax is

Time Reference

and it specifies that the starting time of the event is preassigned the referenced time.

Finally, the optional Resources and ResourceGroups child categories specify the resources that are to attend the event. The syntax of Resources is

Resources *Resource

Each Resource child category specifies a single resource that is to attend the event. A Resource child category is often referred to informally as a resource, but in this documentation it is always called an event resource, to distinguish it from a resource such as a teacher or room. Its syntax is

Resource +Reference +Role +ResourceType +Workload

Its meaning is determined by whether the Reference attribute is present or not.

When the Reference attribute is absent, the solver is expected to assign a resource to the event resource, and both the Role and ResourceType child categories are compulsory. Role has no attributes and no child categories; its body is used similarly to an identifier, to identify the event resource within the event. Two event resources of one event may not have the same value for Role, but it is normal for event resources within different events to have the same value for Role. The ResourceType child category determines the type of resource that must be assigned here. A solution that assigns a resource of some other type is illegal and will be rejected.

When the Reference attribute is present, it references a resource which is to be preassigned to the event. In that case, the Role and ResourceType child categories may be omitted; if present, they have the meaning just given, and the type of the preassigned resource must equal the resource type.

When the optional Workload child category is present, it defines a workload for the event resource. If absent, the workload defaults to the workload of the enclosing event. If present, Workload has no attributes or child categories, and its body consists entirely of an integer whose value is at least 0. A full explanation of workloads appears in the specification of the limit workload constraint.

The syntax of ResourceGroups is

ResourceGroups *ResourceGroup

and the syntax of ResourceGroup is

ResourceGroup Reference

It references a resource group. At present, the meaning is that every resource in the resource group is to be preassigned to the event, with workload equal to the workload of the event. However, the original plan was to use this category for student sectioning, so there may be a change to the specification here in the future.

Constraints

The Constraints child category of Instance lists the constraints that a solution to the instance should obey. For full details, click here.

Solution Groups

A solution group is a collection of solutions to the instances of the enclosing archive, constructed by the same version of the same solver. A solution group may contain any number of solutions (including none) to each instance.

The syntax of the SolutionGroups child category of HighSchoolTimetableArchive is

SolutionGroups *SolutionGroup

The syntax of SolutionGroup is

SolutionGroup Id MetaData *Solution

Id identifies the solution group as usual. MetaData holds information describing the provenance of the solution group. Its syntax is

MetaData Contributor Date Description +Publication +Remarks

The child categories each hold plain text only. They give the name of the person who contributed the solution group, the date it was contributed, a description that may be printed when displaying the solution group, an optional citation of a publication describing how the solution group was produced, and optional remarks.

Solutions

In addition to assigning times and resources to events, a solver is expected to split some of the events into smaller pieces. This allows courses to spread their lessons through the cycle, without forcing the durations of those lessons to be fixed in advance, as would be the case if each lesson was modelled as a distinct event. For example, a solver might split an event of duration 6 into fragments of durations 2, 2, 1, and 1.

It is possible to imagine a solver taking an initial instance and modifying it by splitting its events and assigning times and resources to the resulting fragments. However, this documentation takes a different view. It considers instances to be immutable. A solution is a separate entity, derived from an instance but distinct from it, and capable of representing how the instance events are split and which times and resources are assigned to them.

For each instance event, a solution contains some sub-events or solution events derived from that instance event. These are the fragments referred to above. A solution event has a duration, a workload, and a set of solution resources, one for each event resource in the instance event it is derived from. A solution event may be assigned a time, which is its starting time, and a solution resource may be assigned a resource.

The syntax of solutions is

Solution Reference +Description +RunningTime +Events +Report

The Reference here is to the instance that the solution solves.

The optional Description contains text recording how the solution was created. This is particularly useful when the enclosing solution group contains several solutions to one instance. Although the value of Description is formally arbitrary, a convention is emerging to use it to record the solver parameters which produced the solution, as in this example:

<Description>randseed=12345678</Description>

Multiple parameters may be separated by commas. The metadata of the enclosing solution group describes the solver which produced all the solutions of the solution group; the solution Description describes only what is distinctive about this particular solution.

The optional RunningTime contains the wall clock running time of the process which produced this solution, in seconds, to the nearest one-tenth of one second, as in this example:

<RunningTime>356.7</RunningTime>

The hardware and software platform is not specified, beyond an expectation that the hardware should be widely available and reasonably affordable. There is no fixed limit to the number of parallel processes.

The syntax of Events is

Events *Event

Each Event category defines one solution event and optionally assigns a starting time and resources to it, using syntax

Event Reference +Duration +Time +Resources

The Reference attribute identifies the instance event that this solution event is derived from. The optional Duration child category defines the duration of the solution event. It has no attributes and no child categories, and its body consists of a single integer whose value must be at least 1. If omitted, the duration is taken to be the duration of the corresponding instance event.

The Time child category, when present, assigns a starting time to the solution event, using syntax

Time Reference

to reference one of the times of the instance. Assigning a time is not compulsory, but omitting to do so always attracts a cost (a violation of an assign times constraint) in practice. If the instance event has a preassigned time, then any assigned time must be the same as the preassigned time.

The assigned time and duration may not cause the solution event to run past the last time of the instance. The entire solution will be rejected in that case.

The Resources child category, when present, assigns resources to the solution resources of the solution event using syntax

Resources *Resource

where Resource has syntax

Resource Reference Role

This specifies that the solution resource whose corresponding event resource has the given Role is to be assigned the referenced resource. (It does not define the solution resource; a solution event always contains one solution resource for each event resource of the corresponding instance event.) The assigned resource must have the same type as the event resource, and if the event resource has a preassigned resource, then the assigned resource must be the same as the preassigned resource. It is illegal to mention the same role twice within one solution event.

A resource may be preassigned or assigned more than once to a single solution event in different solution resources. However, that will yield a penalty if the resource in question is a point of application of an AvoidClashes constraint.

Here is an example of a solution event:

<Event Reference="x7C_English_1"> <Duration>2</Duration> <Time Reference="Wed5"/> <Resources> <Resource Reference="English05"> <Role>1</Role> </Resource> <Resource Reference="r42"> <Role>2</Role> </Resource> </Resources> </Event>

It is derived from the instance event with identifier x7C_English_1, its duration is 2, and its starting time is Wed5. It assigns resources English05 and r42 to two of the solution resources of the solution event.

When a solution is read from an XML file, some elements are added to it automatically, as follows:

For each instance event for which there are no corresponding solution events in the solution, one solution event corresponding to the instance event is added, whose duration is the duration of the instance event. Initially this solution event has no assigned times or resources, but that may be changed by later steps.
If now there is an instance event such that the total duration of the solution events derived from that instance event is not equal to the duration of the instance event, it is an error.
For each solution event, whether read from the file or inserted automatically by the first step, if the solution event has no assigned time and the corresponding instance event has a preassigned time, then assign that preassigned time to the solution event.
For each solution resource of each solution event, whether read from the file or inserted automatically by the first step, if the solution resource has no assigned resource and the corresponding event resource has a preassigned resource, then assign that preassigned resource to the solution resource.

What this mainly amounts to is that it is acceptable to omit preassigned times and resources from a solution, since they will be added automatically. It also guarantees that the total duration of the solution events derived from an instance event equals the duration of that instance event, avoiding the need for a constraint penalizing solutions where this is not the case.

Reports

The optional Report child category of Solution is a report containing the total infeasibility value and objective function value of the solution, plus a detailed list of all the constraint violations that contribute to these values. HSEval has a function that adds a report to each solution of the archive it is given, clearing away any existing reports. It is probably best to omit reports when generating solutions, leaving it to HSEval to add independent and trusted reports, but reports are not prohibited.

The syntax of reports is

Report InfeasibilityValue ObjectiveValue +Resources +Events +EventGroups

InfeasibilityValue has no attributes and no child categories. Its body consists entirely of a single non-negative integer whose value is the total cost of all violations of required (that is, hard) constraints. ObjectiveValue is similar, except that it contains the total cost of all violations of non-required (that is, soft) constraints.

The optional Resources child category of Report reports violations of constraints for which one point of application is one resource, grouped by resource. Its syntax is

Resources *Resource

Each Resource category reports constraint violations for one resource, using syntax

Resource Reference *Constraint

where Reference identifies the resource, and the syntax of Constraint is

Constraint Reference Cost +Description

The reference here is to the violated constraint, which must have the enclosing resource as one point of application. The Cost child category has no attributes or child categories, just a body whose value is an integer giving the cost of the violation of the referenced constraint at the enclosing resource. Since only violations are reported, this cost should have value at least 1. The optional Description child category contains a description of the violation which could be printed when displaying the report.

Here is an example of a report for one resource:

<Resource Reference="Languages03"> <Constraint Reference="LimitBusyTimes_3"> <Cost>2</Cost> <Description>Tuesday, Friday</Description> </Constraint> </Resource>

The timetable of teacher resource Languages03 violates a limit busy times constraint applicable to that resource.

The optional Events child category of Report reports violations of constraints for which one point of application is one event. Its syntax is

Events *Event

Each Event category reports constraint violations for one event, using syntax

Event Reference *Constraint

where Reference identifies the event, and Constraint is as before. For example,

reports that the timetable of event x8S_Science_1 violates several split events and distribute split events constraints, and that not all the solution resources of its solution events received resource assignments.

The optional EventGroups child category of Report reports violations of constraints for which one point of application is one event group. Its syntax is

EventGroups *EventGroup

Each EventGroup category reports constraint violations for one event group, using syntax

EventGroup Reference *Constraint

where Reference identifies the event group, and Constraint is as before. For example,

<EventGroup Reference="x9_English_4"> <Constraint Reference="SpreadEventsConstraint_1"> <Cost>1</Cost> </Constraint> <Constraint Reference="AvoidSplitAssignmentsConstraint_Soft_1"> <Cost>10</Cost> </Constraint> </EventGroup>

reports that the solution events of the events of event group x9_English_4 are imperfectly spread through the cycle, and also that there is a split assignment within the event group.

Return to the HSEval home page.