HSEval Version 2.1 (May 2018)

High School Timetable Data Format Specification: Glossary

This page defines terms used by the specification of the data format of high school timetable files.

    HSEval home page

    Archive
    Class
    Constraint
    Cost
    Cost function
    Course
    Day
    Duration
    Event
    Event group
    Event resource
    Identifier
            Infeasibility value
            Instance
            Instance event
            Name
            Objective value
            Resource
            Report
            Required
            Resource group
            Resource type
            Role
            Room
            Solution
            Solution event
            Solution group
            Solution resource
            Student
            Sub-event
            Teacher
            Time
            Time group
            Week
            Weight
            Workload


Archive

An archive is a collection of instances of the high school timetable problem, together with zero or more solution groups containing solutions to those instances. For more information, consult the main entry here.


Class

A recommended name for a resource type whose resources each represent one group of students who attend events together, at least for the most part.


Constraint

A constraint is a condition that a solution should obey; if it doesn't, then a cost is incurred. For more information, consult the constraints page.


Cost

A cost is a penalty incurred for violating one or more constraints. The total cost of all hard constraint violations is the infeasibility value, and the total cost of all soft constraint violations is the objective value. The aim of a solver should be to produce a solution which minimizes the infeasibility value as its first priority, and the objective value as its second priority.


Cost function

A cost function is a child category of a constraint that determines which function is applied to the deviations before multiplying by the weight to give a cost. For more information, consult the constraints page.


Course

A course is a set of events. As far as HSEval is concerned it is just an alternative name for an event group, but other software might treat it differently, for example when displaying timetables. The intention is that the set of events of one course should constitute a course of study in one subject for one group of students. For more information, consult the main entry for Events here.


Day

A day is a set of times. As far as HSEval is concerned it is just an alternative name for a time group, but other software might treat it differently, for example when displaying timetables. The intention is that all the times of each day should lie in a common Day category. For more information, consult the main entry for Times here. See also Week.


Duration

The duration of an instance event or solution event is the number of times that it occupies. For more information, consult the main entry for events here.


Event

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. For more information, consult the main entry here. For the distinction between instance events and solution events, consult the specification of solutions here.


Event group

An event group is a set of events. For more information, consult the main entry for events here.


Event resource

An event resource is a component of an event to which one resource of a particular type may be assigned. For more information, consult the main entry for events here.


Identifier

An identifier is a string used to refer to one part of the file from another part. It is defined by an Id attribute of the category it identifies, and referenced by Reference attributes elsewhere in the file.

Where there is an Id attribute there is often a Name child category containing just text. The identifier is used to reference its category, while the name is used when displaying the category in human-readable form. As an exception, instances are often referred to by their identifier rather than name, especially in tables where space is limited.

It is usual in XML for the scope of an identifier to be the entire file, and for different Id attributes to define distinct identifiers. However, that would make it awkward to bring instances together from different sources, so a different rule is used here.

The identifiers that label the instances of an archive must be distinct from each other. They are referenced only at the start of solutions, where the references are known to be to instances, so they do not have to be distinct from other identifiers.

Within an instance, the kinds of entities that have identifiers are: time groups (including days and weeks), times, resource types, resource groups, resources, event groups (including courses), events, and constraints. Identifiers that label entities of the same kind within the same instance must be distinct from each other, but they need not be distinct from identifiers that label entities of other kinds, or instances, or entities within other instances. Resources of different resource types are considered to be entities of the same kind.

Each identifier defined within an instance is visible throughout its instance and throughout the solutions of that instance, but not elsewhere.


Infeasibility value

The infeasibility value of a solution is the total cost of all hard constraint violations incurred by that solution. See also objective value.


Instance

An instance is one occurrence of the high school timetable problem, for a particular school in a particular year (or semester, etc.). For more information, consult the main entry here.


Name

A name is some text used to identify a category when displaying it in human-readable form. See also identifier.


Objective value

The objective value of a solution is the total cost of all soft constraint violations incurred by that solution. See also infeasibility value.


Report

A report is an optional section of a solution, giving the infeasibility value and the objective value of the solution, as well as a list of the constraint violations that contributed to these costs. For more information, consult the main entry for solutions here.


Required

A boolean child category of a constraint which determines whether the constraint is hard or soft. For more information, consult the Constraints page.


Resource

A resource is an entity, typically a teacher, a room, a student, or a class (group of students), which attends events. For more information, consult the main entry here.


Resource group

A resource group is a set of resources of the same type. For more information, consult the main entry for resources here.


Resource type

Resource types supply a basic classification of resources: each resource has exactly one resource type. The most frequently encountered resource types are Teacher, Room, Class, and Student, but arbitrary resource types may be defined. For more information, consult the main entry for resources.


Role

A role is some text, typically in the form of an integer or identifier, which labels an event resource so that it can be referenced from elsewhere in the file. A role must be unique within the enclosing event, but many events may and usually do utilize the same roles.


Room

A recommended name for a resource type whose resources represent rooms, or (more generally) the locations where events occur.


Solution

A solution of an instance is a description of how the events of that instance should be split into fragments and assigned times and resources so as to produce a timetable. For more information, consult the main entry here.


Solution event

A solution event, also known as a sub-event, is a component of a solution, representing one fragment of an instance event. For more information, including an explanation of the difference between solution events and instance events, consult the main entry for solutions here.


Solution group

A solution group is a collection of solutions to some instances of the high school timetabling problem. It must lie within an archive, and the instances its solutions solve are the instances of that archive. For more information, consult the main entry here.


Solution resource

A solution resource is a component of a solution event, capable of being assigned a resource. For more information, consult the main entry for solutions here.


Student

A recommended name for a resource type whose resources represent individual students.


Teacher

A recommended name for a resource type whose resources represent teachers.


Time

A time is a component of an instance representing one indivisible interval of time in which an event may be running. For more information, consult the main entry here.


Time group

A time group is a set of times. For more information, consult the main entry here.


Week

A week is a set of times. As far as HSEval is concerned it is just an alternative name for a time group, but other software might treat it differently, for example when displaying timetables. The intention is that all the times of each week should lie in a common Week category. For more information, consult the main entry for times here. See also Day.


Weight

The weight of a constraint is an integer which determines how heavily violations of the constraint are weighted in the total cost. For more information, consult the constraints page.


Workload

The workload of an instance event or solution event is an integer representing how much work the event entails. For more information, consult the main entry for limit workload constraints here.



HSEval Software Copyright Jeffrey H. Kingston 2012