The format XHSTT grew out of several years of discussions, which led to a quite abstract formulation. Consequently, it can be difficult in the beginning to understand XHSTT. This page gives a short and hopefully gentle introduction to XHSTT. It might be worthwhile to have a look at the FAQ section as well. For extensive documentation we refer to HSEval.
General structure
The principal goal of XHSTT is to contain datasets for High School Timetabling. Apart from this, XHSTT can contain solutions as well, in fact it can contain an archive of instances and groups of solutions. For now we focus on the instance itself, i.e. in XML we look at the children of the <instance>-tag.
An instance contains 4 groups of items: items related to time, items related to resources, items related to events, and items related to constraints. Here we see the first pecularity of XHSTT: the first 3 groups (<Times>, <Resources>, and <Events>) contain relatively little information. This means that almost all business logic is carried by the constraints, or said differently a constraint usually will have several parameters that describe the information how to apply it.
Times
The Times section contains 4 entities: TimeGroups, Weeks, Days and Times. A Day or Week is simply a special TimeGroup, which can be added as a property to a Time. At all other places it is referred to as TimeGroup. The reason for the existence of Days and Weeks is for displaying only. In the datasets Weeks do not occur: all instances describe a weekly timetable. As can be guessed, a TimeGroup is a set of Times. Times are assumed to be consecutive as given in the instance.
Resources
The Resources section contains 3 entities: ResourceTypes, ResourceGroups and Resources. A Resource has exactly one ResourceType. The ResourceType is introduced for displaying (for example: distinguishes teachers from students), and consistency in assigning resources to events, see the Role section below. ResourceGroups are groups of Resources of the same ResourceType.
Events
The Events section contains 3 entities: EventGroups, Courses and Events. Courses are special EventGroups. An Event has a property Course. At all other places Courses are referred to as EventGroup. Obviously, an EventGroup is simply a set of Events.
Now what is an Event? This question has two answers in XHSTT. The first answer is that an Event is a lesson of a fixed Duration. Hence our timetabling problem is to set a begin Time to events, which implies that the Event is planned to this Time, and some consecutive Times if the Duration exceeds 1. Since an Event has (can have) Resources attached to it, these Resources are now busy at these Times. Here we meet the 2 basic requirements in timetabling, which are made explicit as constraint in XHSTT: we need to assign a (begin)Time to each Event (AssignTimeConstraint) and we have to make sure that Resources are not planned double (AvoidClashesConstraint). Some datasets have only these constraints, see the artificial datasets (all except the Sudoku).
The other interpretation of Event is slightly more complicated: an Event can represent all lessons with exactly the same properties, i.e. a course. These properties are for example the Resources class and teacher. In this case the duration is the total Duration required for this class-teacher combination. So now a part of the planning problem is to divide the "instance" Event in "solution" Events; here the "solution" Events are the lessons in the first interpretation. To know which interpretation is valid, a dataset with Events of Durations greater than 1 will contain one or more SplitEventsConstraints, explaining how the "instance" event can be divided into "solution" events. If these constraints don't give enough details, one can add DistributeSplitEventsConstraints to control the number of "solution" Events of a certain Duration.
An example of the first interpretation is FinlandArtificialSchool. Note that SplitEventsConstraint has MinimumAmount=1 and MaximumAmount=1, which means that the "instance" Event should lead to exactly 1 "solution" Event. An example of the second interpretation is BrazilInstance1. Here MinimumAmount=1 and MaximumAmount=999, so we can split the "instance" Event to as many "solution" Events as you wish. Since the summed Durations of the "solution" Events must be the Duration of the "instance" Event (otherwise the solution is marked invalid by HSEval), this total Duration is an upper bound for the number of "solution" Events. Note that in BrazilInstance1 MinimumDuration=1 and MaximumDuration=2, implying that "solution" Events should have Duration 1 or 2. In BrazilInstance1 there is also several DistributeSplitEventsConstraints, which express that for some Events we need at least one or two lessons of Duration 2.
Roles
Above we described 2 scheduling decisions that are needed in high school timetabling: creating "solution" Events from "instance" Events, and setting start Times to the "solution" Events. The third scheduling decision is the assignment of Resources to Events. To enable this, Roles are added to Events. Roles are properties of Events, and reappear in the Constraints AssignResourceConstraint, PreferResourcesConstraint, and AvoidSplitAssignmentsConstraint. The primary aim of Roles is to describe what Resource has to be assigned to an Event. Mostly, this Resource is a room or a teacher. The Role always contains a ResourceType; the Resource assigned to the Role should be of this ResourceType. For an example we refer to FAQ, number 1 and 4. If a Resource of another ResourceType is assigned to the Role, the solution will be marked invalid by HSEval.
Constraints
In XHSTT Constraints exist in two modes: constraints that are Required (hard Constraints) and Constraints that are not Required (soft Constraints). All Constraints can be in either mode. If all Required Constraints are satisfied, we call the schedule feasible. Violating Required Constraints add costs to the Infeasibility Value of the solution. The non-Required Constraints add cost to the Objective Value. During scheduling (generating solutions) our primary goal is minimizing the Infeasibility Value, and the secondary goal is minimizing the Objective Value. Apart from Required or not, a Constraint also has a Weight: the generated cost increases linearly with the Weight.
It is allowed to use constraint of the same type several times. So what we call a "constraint" in fact is a "constraint type", that can reappear with different parameters any number of times.
The Constraints in XHSTT can work on Events, EventGroups, and Resources. For more details we refer to the Constraints documentation.
Completeness
XHSTT is by no means complete. There are several requirements that are not covered yet. Some of these are mention in ToDo.