Contents
Input/output data format is XML, with the following structure:
<?xml version="1.0" encoding="UTF-8"?>
<!--Examination Timetabling-->
<examtt
version="1.0"
campus="1"
term="Fal"
year="2007"
created="Wed Jun 25 14:58:57 EDT 2008">
| examtt root element |
| version | file version |
| campus | campus designation |
| term | semester (e.g., Spr or Fal) |
| year | year (e.g., 2007) |
| created | creation time of the file |
1. Definition of examination periods:
<periods>
<period id="1" length="120" day="07/12/10" time="8:00am-10:00am" penalty="0"/>
<period id="2" length="120" day="07/12/10" time="10:20am-12:20pm" penalty="0"/>
<period id="3" length="120" day="07/12/10" time="1:00pm- 3:00pm" penalty="0"/>
<period id="4" length="120" day="07/12/10" time="3:20pm- 5:20pm" penalty="0"/>
<period id="5" length="120" day="07/12/10" time="7:00pm- 9:00pm" penalty="0"/>
<period id="6" length="120" day="07/12/11" time="8:00am-10:00am" penalty="0"/>
<period id="7" length="120" day="07/12/11" time="10:20am-12:20pm" penalty="2"/>
...
</periods>
| period: definition of an examination period |
| id | period unique id |
| length | period length (in minutes) |
| day | period date (string) |
| time | period time (string) |
| penalty | penalization of using this period |
Unless changed on an exam, if an exam is assigned to a period with non-zero penalty, this penalty is added
to the overall period penalty of the solution.
2. Definition of examination rooms:
<rooms>
<room id="1" size="58" alt="32" coordinates="447,392"/>
<room id="2" size="50" alt="25" coordinates="447,392"/>
<room id="3" size="60" alt="30" coordinates="450,463"
<period id="3" available="false"/>
<period id="5" penalty="2"/>
...
</rooms>
| room: definition of an examination room |
| id | room unique id |
| size | room size (number of seats in the room) |
| alt | alternative room size (number of seats in the room if an exam requests alternate seating) |
| coordinates | room location coordinates X,Y |
- Distance between rooms in meters is: 10 * ((x2-x1)^2 + (y2-y1)^2)^1/2
- Location attribute might not be present (e.g., for non-campus locations), distance between such a room and any other room are considered as infinite in such a case
Room period preferences:
| period: definition of a period preference of a room |
| id | period unique id |
| available | if false, room is not available during this period (default is true) |
| penalty | penalization of using the room during this period (default is zero) |
Room can be unavailable for certain periods. Unless changed on an exam, if an exam is assigned to a room in a period with non-zero penalty,
this penalty is added to the overall room penalty of the solution.
3. Definition of examinations:
<exams>
<exam id="1" length="120" alt="true" minSize="10" maxRooms="2" average="14">
<period id="1"/>
<period id="3" penalty="2"/>
<period id="4" penalty="-2"/>
...
<room id="1"/>
<room id="5" penalty="2"/>
<room id="12" penalty="-1"/>
...
<assignment>
<period id="1"/>
<room id="5"/>
<room id="12"/>
</assignment>
</exam>
<exam id="2" length="60" alt="false">
<period id="2"/>
<period id="4" penalty="2"/>
...
<room id="1"/>
<room id="4"/>
...
<assignment>
<period id="4"/>
<room id="4"/>
</assignment>
</exam>
<exam id="3" length="60" alt="false" maxRooms="0">
<period id="2"/>
<period id="5" penalty="2"/>
...
<assignment>
<period id="2"/>
</assignment>
</exam>
...
</exams>
| exam: definition of an examination |
| id | examination unique id |
| length | length (in minutes) |
| alt | alternate seating requested |
| minSize | minimal size of the requested room (zero if not present) |
| maxRooms | maximal number of rooms (4 if not present) |
| average | index of average period (for rotation penalty) |
List of available periods and rooms is included in the exam element. If an exam is assigned to period and room(s), assignment element is also present.
The following hard constraint must be met
- Only one exam can be placed in a room at any period.
- Only available periods and rooms may be used (periods/rooms listed under the exam).
- A room cannot be used on periods during which it is not available.
- An exam must be placed in a room (or a set of rooms) so that the overall seating capacity of the rooms equals or is
greater than the number of students attending the exam, with respect to the requested seating type
(e.g., each room has a normal seating (size attribute) and alternate seating capacities defined (alt attribute),
an exam can request either normal (alt=false) or alternate seating (alt=true)). Maximal number of rooms into which
an exam can be split (maxRooms attribute) cannot be exceeded as well.
- If maximal number of rooms is set to zero, an exam is to be placed only in a period (without any room assignment).
- Required distribution constraints must be satisfied(see bellow).
4. Definition of students (and their enrollments):
<students>
<student id="1">
<exam id="2048"/>
<exam id="1976"/>
<exam id="1978"/>
<period id="3" available="false"/>
</student>
<student id="2">
<exam id="389"/>
<exam id="1924"/>
<exam id="2103"/>
</student>
...
</students>
Each student has a unique id and a list of examinations into which he/she is enrolled.
A student might be not available at some periods (direct conflict occurs when an exam with
such a student is placed into such a period)
5. Definition of instructors (and their enrollments):
<instructors>
<instructor id="1">
<exam id="123"/>
<exam id="235"/>
<exam id="1235"/>
</instructor>
<instructor id="2">
<exam id="389"/>
<exam id="1234"/>
<period id="7" available="false"/>
</instructor>
...
</students>
Each instructor has a unique id and a list of examinations into which he/she is enrolled.
An instructor might be not available at some periods (direct conflict occurs when an exam with
such a student is placed into such a period)
6. Definition of distribution constraints:
<constraints>
<different-period id="1">
<exam id="123"/>
<exam id="345"/>
<exam id="2334"/>
</different-period>
<different-room id="2" hard="false" weight="2">
<exam id="12"/>
<exam id="157"/>
</different-room>
...
</constraints>
Distribution constraints are constraints that take place between two or more exams.
Each instructor has a unique id and a list of examinations into which he/she is enrolled.
Soft constraints have
hard attribute set to false (default is true), and have
a weight defined. This weight is added to overall distribution penalty of a solution if
the constraint is not satisfied.
Following constraints are defined:
- same-room ... exams are required/preferred to take place in the same room or rooms.
- different-room ... exams are required/preferred to take place in different rooms (no two exams of the constraint are to be placed in the same room).
- same-period ... exams are required/preferred to take place during the same periods.
- different-period ... exams are required/preferred to take place during different period.
- precedence ... exams are required/preferred to take place in the order they are listed in the constraint. For instance if exam A is in the precedence constraint before exam B, it is to be placed in a period that precedes the period in which exam B is placed.
</examtt>
