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.
An archive is a collection of instances of the high school timetable problem, together with zero or more solution groups. Each solution group is a collection of zero or more solutions to the instances of its archive. The syntax of archives is
In this notation, placement on the same line indicates that one category is an attribute of another, indenting indicates that one category is a child of another, + indicates that the immediately following category is optional, and * indicates that the immediately following category may appear zero or more times. It is usual in XML to allow the children of a category to appear in any order, but throughout the high school timetable format the children are required to appear in the order given by the syntax specification.
For example, a file containing the following conforms to this syntax:
The optional MetaData category holds information describing the provenance of the archive. Its syntax is
The child categories each hold text only. They give the name of the archive, the name of the person who assembled it, the date it was assembled, a description which will be printed when displaying the archive, and some optional remarks.
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
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
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.
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
The optional TimeGroups category declares time groups, which are sets of times. Its syntax is
The syntax of TimeGroup is
It declares a time group with the given Id and Name. For example,
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
where the syntax of TimeGroups is
and the syntax of TimeGroup is
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,
defines one time lying in the Monday and BeforeLunch time groups.
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
The syntax of ResourceTypes is
where each ResourceType category defines one resource type, and has syntax
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
where the syntax of ResourceGroup is
This contains the usual Id and Name elements, plus a compulsory ResourceType child category whose syntax is
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,
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
where the syntax of ResourceGroups is
and the syntax of ResourceGroup is
Altogether, this defines a resource with the given identifier, name, and type, and specifies which resource groups the resource lies in. For example,
defines a resource of type Room lying in resource groups LargeRoom and ScienceLab.
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
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
The syntax of EventGroup is
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
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
and specifies that the event lies in the referenced course. Similarly, the optional EventGroups child category has syntax
where EventGroup has syntax
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
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
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
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
and the syntax of ResourceGroup is
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.
The Constraints child category of Instance lists the constraints that a solution to the instance should obey. For full details, click here.
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
The syntax of SolutionGroup is
Id identifies the solution group as usual. MetaData holds information describing the provenance of the solution group. Its syntax is
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.
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
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:
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:
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
Each Event category defines one solution event and optionally assigns a starting time and resources to it, using syntax
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
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
where Resource has syntax
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:
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:
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
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
Each Resource category reports constraint violations for one resource, using syntax
where Reference identifies the resource, and the syntax of Constraint is
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:
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
Each Event category reports constraint violations for one event, using syntax
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
Each EventGroup category reports constraint violations for one event group, using syntax
where Reference identifies the event group, and Constraint is as before. For example,
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.