Contents
Changes
Data Format v2.4 is almost the same as , with the following exceptions:
- Due to the course enrollment projections, students are now weighted (an offering element of a element has a new attribute weight).
- There are few new group constraints (NDB_GT_1, CH_NOTOVERLAP, FOLLOWING_DAY and EVERY_OTHER_DAY), see for more details.
Input/output data format is XML, with the following structure:
<?xml version="1.0" encoding="UTF-8"?>
<!--University Course Timetabling-->
<timetable
version="2.4"
initiative="puWestLafayetteTrdtn"
term="2007Fal"
created="Mon Mar 26 14:42:12 EDT 2007"
nrDays="7"
slotsPerDay="288">
| timetable root element |
| version | file version |
| initiative | campus designation |
| term | semester (e.g., 2007Spr or 2007Fal) |
| created | creation time of the file |
| nrDays | number of days per week (default is 7 days, Monday through Sunday) |
| slotsPerDay | number of slots per day (default is 288, 5 minute long time slots, going from midnight till midnight) |
1. Definition of rooms:
<rooms>
<room id="201" constraint="true" capacity="48" location="489,468"/>
<room id="202" constraint="true" capacity="40" location="488,473"/>
<room id="203" constraint="true" capacity="39" location="488,473"/>
<room id="54" constraint="true" capacity="51" location="437,411">
<sharing>
<pattern unit="6">FFFFFFFFFFFFFFF0000002200000000000000FFFFFFFFFFFFFFFFFFFFFFFFFF0000000000000000000000...</pattern>
<freeForAll value="F"/>
<notAvailable value="X"/>
<department value="0" id="3"/>
<department value="1" id="1"/>
<department value="2" id="2"/>
</sharing>
</room>
<room id="49" constraint="false" capacity="63" discouraged="true" ignoreTooFar="true"/>
...
</rooms>
| room: definition of a room |
| id | room id |
| capacity | room capacity (number of seats in the room) |
| location | room location coordinates x,y
- distance between rooms in meters: 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
|
| ignoreTooFar |
- true if the distances between this room ant any other room should not be considered (no distance conflicts for this room)
- false if the distances should be considered (this is the default, when ignoreTooFar attribute is not present)
|
| constraint |
- true if room constraint should be created (default is true),
- false otherwise (classes can overlap in time in this room)
|
| discouraged |
- true if the use of this room should be discouraged (a constraint minimizing the use of such room is posted for this room),
- false otherwise (default is false)
|
If a room is not available all the times or if there is a sharing between two or more departments defined for the room, the sharing element is present:
| sharing: room availability & sharing matrix |
| pattern | defines the room availability & sharing sharing matrix:
- since the sharing matrix is defined for bigger periods than individual slots (typically for 30 minute periods) in the user interface, unit attribute defines the relation between these periods and the slots (e.g., unit="6" means that each chatacter in the matrix stands for 6 consecutive slots).
- time periods are enumerated going from the first day to the last day, for each day from the beginning to the end
- the above example for room 54 can define the following sharing (time slots are 5 minute long, going from midnight till midnight):
|
|
| freeForAll | identification of free for all time (a given time can be used by any of the given departments) |
| notAvailable | identification of not avaialble time (a given time cannot be used by any of the given departments) |
| department | transformation between the identification of the department in the sharing matrix (attribute value) and the department id (attribute id) |
2. Definition of instructors:
A set of instructors is not explicitly defined, however all classes that are sharing an instructor are refering to an instructor with the same unique id.
There are also no preferences or requirements needed to be set on instructors, all theses preferences and requirements are inherited to classes (e.g., if an instructor is not available during Fridays, there is no available Friday time location on classes requiring that instructor).
If an instructor is already teaching some class of another problem (which does already have a committed solution), appropriate committed classes are included in the XML file (see class definition below).
3. Definition of classes:
<classes>
<class id="1492" offering="685" config="686" committed="false" subpart="828" classLimit="40" scheduler="11"
dates="00000000000000000000000000000000000000111111001111101111110111111011111101111110111111011111101111110000000011111101111110111111011111101111110111111">
<room id="207" pref="0"/>
<room id="209" pref="0" solution="true"/>
<time days="1010100" start="90" length="12" pref="0.0"/>
<time days="1010100" start="102" length="12" pref="0.0" solution="true"/>
<time days="1010100" start="114" length="12" pref="0.0"/>
<time days="1010100" start="126" length="12" pref="0.0"/>
<time days="1010100" start="138" length="12" pref="0.0"/>
<time days="1010100" start="150" length="12" pref="0.0"/>
<time days="1010100" start="162" length="12" pref="0.0"/>
<time days="1010100" start="174" length="12" pref="0.0"/>
<time days="1010100" start="186" length="12" pref="0.0"/>
<time days="1010100" start="198" length="12" pref="0.0"/>
</class>
<class id="1605" offering="694" config="695" committed="false" subpart="844" minClassLimit="32" maxClassLimit="40" scheduler="11"
dates="00000000000000000000000000000000000000111111001111101111110111111011111101111110111111011111101111110000000011111101111110111111011111101111110111111">
<instructor id="448" solution="true"/>
<room id="210" pref="-4" solution="true"/>
<time days="0101000" start="108" length="18" pref="0.0"/>
<time days="0101000" start="126" length="18" pref="-20.0" solution="true"/>
<time days="0101000" start="144" length="18" pref="0.0"/>
<time days="0101000" start="162" length="18" pref="-20.0"/>
<time days="0101000" start="180" length="18" pref="0.0"/>
</class>
<class id="1581" committed="true" subpart="842"
dates="00000000000000000000000000000000000000111111001111101111110111111011111101111110111111011111101111110000000011111101111110111111011111101111110111111">
<room id="22" pref="0" solution="true"/>
<time days="1010100" start="174" length="12" pref="0.0" solution="true"/>
<instructor id="444" solution="true"/>
</class>
...
</classes>
| class: definition of a class |
| id | class id |
| offering | instructional offering id (top most unit in the class organization structure; offering, config, subpart and parent attributes are needed for student sectioning) |
| config | offering configuration id (each instructional offering has one or more configurations) |
| subpart | scheduling subpart id (one configuration has one or more scheduling subparts; classes of the same instructional type (e.g., lecture, recitation, laboratory) are grouped together into schedling subparts) |
| parent | id of parent class (only present if the class has a parent) |
| scheduler | managing department id (this department is used, e.g., for room sharing) |
| department | controlling department id (this department is only used for departmental balancing constraints, it is only present if departmental balancing is enabled) |
| committed | true for committed classes (committed classes are of different problems (that already have a solution committed), on top of which the current solution is to be built; only committed classes that related to the current problem (e.g., using the same resource) are included) |
| classLimit | class limit (maximal number of students that can attend the class) |
minClassLimit,
maxClassLimit | minimal and maximal class limit (only present if min!=max, see for description) |
| roomToLimitRatio | minimal room size = roomToLimitRatio * minClassLimit (default roomToLimitRatio is 1.0) |
| nrRooms | number of rooms that the class requires (default is 1, can be zero or a positive integer number) |
| dates | binary string defining on what days during the term the class can be taught |
Each class (variable) contains
- a given set of instructors (all instructors are required to be present, there is no choice of instructors on the solver side)
- a set of available rooms (if nrRooms>0; only valid rooms are present, i.e., rooms that are too small or prohibited for given class are excluded)
- a set of available times (only valid times are present, i.e., the times that meet the required time pattern and that are not prohibited)
Each placement (value) contains
- all given instructors
- given number (nrRooms) of rooms selected out of the set of available rooms
- one time selected out of the set of available times
a. instructors:
| instructor |
| id | instructor id |
| solution | identification of solution placement (when solution=true) |
b. room placements:
| room |
| id | room id |
| pref | room preference (room preference is a combination of room, building, room group and room feature preferences that are put on given class; minimization of the overall room preference is one of the optimization criteria) |
| solution | identification of solution placement (when solution=true) |
c. time placements:
Each time location encodes the selection (e.g., MWF 7:30 - 8:30) of
- days (e.g., 1010100 means Monday + Wednesday + Friday),
- start time (e.g., 90 means 7:30 am),
- length of each meeting (e.g., 12 means 60 minutes)
| time |
| days | selection of days (binary string encoding days Monday, Tuesday, Wednesday, .. Sunday) |
| start | start time slot |
| length | number of time slots each meeting takes |
| pref | normalized time preference (minimization of the overall time preference is one of the optimization criteria) |
| solution | identification of solution placement (when solution=true) |
Two time placements overlap when
- dates are overlapping (binary operation XOR of dates attributes returns a non-zero value) and
- days are overlapping (binary operation XOR of days attributes returns a non-zero value) and
- times are overlapping ((t1.start + t1.length > t2.start) AND (t2.start + t2.length > t1.start))
As for student sectioning, each student that requires an offering has to be enrolled in
- a class of each scheduling subpart of one of the instructional configurations of the offering
- if a student is enrolled in a class that has a parent class defined, it has to be also enrolled in the parent class (parent class is always of a different subpart than the children class)
A student conflict occurs when
- a student is enrolled into two classes that overlap in time
- a student is enrolled into two classes that are back-to-back (the second class starts by the time the first class ends) and that are being placed in rooms that are two far
- distance between two rooms is higher than 670 meters
- if the first class is in time that is 18 time slots (90 minutes) long, the allowed distance between two rooms is 1000 meters (15 minute long passing time in opposite to standard 10 minute long passing time)
Minimization of student conflicts is one of the optimization criteria.
An instructor can teach two classes if they are not overlapping in time. If those classes are back-to-back (the second class starts by the time the first class ends), the distance between rooms of these classes is considered
- it is discouraged to have two back-to-back classes with the distance above zero but below or equal to 50 meters (0 < distance <= 50)
- it is strongly discouraged to have two back-to-back classes with the distance above 50 meters but below or equal to 200 meters ( 50 < distance <= 200)
- it is prohibited to have two back-to-back classes with the distance above 200 meters
Minimization of overall instructor back-to-back preference (weighted 1 for discouraged, 4 for strongly discouraged) is one of the optimization criteria.
Department balancing constraint was introduced only for Large Lecture Room problem. It tries to distribute the times during the day fairly between the departments (preventing, e.g., one department to have all its classes during unpopular times like before 8:30 am or after 4:30 pm).
As for the effectivity of selected times and rooms, it is
too big rooms criteria:
- discouraged to use a room that has 25% more seats than the smallest available room
- strongly discouraged to use a room that has 50% more seats than the smallest available room
useless half-hours criteria:
- discouraged to have an empty half-hour (6 time slots) window in a room (each meating is at least an hour long)
broken standard time pattern criteria: (standard time patterns are using MWF or TTh)
- discouraged to have an empty time slot on Monday, Wednesday or Friday without an empty time slot at the same time on all other days from Monday, Wednesday or Friday (e.g., Monday 7:30 am is empty, but Wednesday and Friday 7:30 am is not)
- discouraged to have an empty time slot on Tuesday or Thursday without an empty time slot at the same time on the other day Thursday or Tuesday respectively
Minimization of the above cases is also included in optimization, but it usually has much lower weight than all the other criteria.
4. Definition of group (distribution) constraints:
<groupConstraints>
<constraint id="121" type="BTB" pref="R">
<class id="1479"/>
<class id="1480"/>
</constraint>
<constraint id="170" type="DIFF_TIME" pref="-2">
<class id="1615"/>
<class id="1616"/>
<class id="499"/>
</constraint>
<constraint id="1046" type="CLASS_LIMIT" pref="R" courseLimit="160" delta="-20">
<class id="1605"/>
<class id="1606"/>
<class id="1607"/>
<class id="1608"/>
<class id="1609"/>
</constraint>
<constraint id="1045" type="CLASS_LIMIT" pref="R">
<parentClass id="1609"/>
<class id="1614"/>
<class id="1615"/>
</constraint>
...
<groupConstraints/>
| constraint: definition of a group (distribution) constraint |
| id | constraint id |
| type | constraint type (see [Group Constraint Types]) |
| pref |
constraint is either required or prohibited (hard constraint):
R .. constraint is required,
P .. constraint is prohibited
or it is preferred or discouraged (soft constraint):
-2 .. strongly preferred,
-1 .. preferred,
1 .. discouraged,
2 .. strongly discouraged
(minimization of the overall group constraint preferences (for soft group constraints) is one of the optimization criteria)
|
courseLimit,
delta | CLASS_LIMIT constraint only, the sum courseLimit + delta defines overall minimal class limit of the classes in the constraint (default value for delta attribute is zero) |
Each constraint also contains a list of classes (class elements) between which the constraint is being ensured. Only classes of the given problem (that is being described by the XML file) and the classes that have committed solution are included.
Constraint CLASS_LIMIT is a special constraint that is connected with the classes that does have defined minimal and maximal class limit (attributes minClassLimit and maxClassLimit). It is always required and it ensures the following properties:
- limit of a class (that does not have any children classes) is MIN ( maxClassLimit, assignedRoomSize/roomToLimitRatio )
(assignedRoomSize is the size of the assigned room, in case of multiple rooms (nrRooms>1), it is the size of the smallest room that is assigned to a class)
- limit of a class (that does have children classes) is MIN ( maxClassLimit, assignedRoomSize/roomToLimitRatio, sumChildrenClassLimits )
(sumChildrenClassLimits is the sum of the class limits of the children classes)
- sum of class limits of classes in the CLASS_LIMIT constraint (all classes of the same scheduling subpart, with the same parent class) is equal or greater than minClassLimit of the parent class
(parentClass element pointing to the parent class is defined for the constraint in this case)
- for the top most classes (classes with no parents), sum of class limits of classes in the CLASS_LIMIT constraint (all classes of the same scheduling subpart) is equal or above course limit
(courseLimit attribute defining the desired minimal class limit of the classes in the constraint is defined in this case)
(in some cases attribute delta is also defined, it is a compensation for classes of the subpart that are of different problems (and that do not have any committed solution yet), minimal class limit of the classes in the constraint is than equal to courseLimit + delta)
5. Definition of student demands:
<students>
<student id="4">
<offering id="701" weight="1.3200"/>
<class id="1669"/>
<class id="2394"/>
<class id="795"/>
<class id="287"/>
<class id="212"/>
<class id="285"/>
</student>
<student id="32">
<offering id="702" weight="0.9500"/>
<offering id="705" weight="1.0000"/>
<class id="1699"/>
<class id="1744"/>
<prohibited-class id="1712"/>
<prohibited-class id="1704"/>
<prohibited-class id="1710"/>
<prohibited-class id="1706"/>
<prohibited-class id="1702"/>
<prohibited-class id="1707"/>
</student>
...
</students>
| student: course demands of a student |
| id | student id |
| offering | student demands an offering with given id
attribute weight reflects the course enrollment projection (i.e., for each class, sum of the weights of the enrolled students should not exceed the classLimit) |
| class | student is enrolled in class with given id |
| prohibited-class | student cannot be enrolled in class with given id |
Each student contains a set of instructional offerings that he/she requests. Only offerings of the given problem (the problem that is being described by the XML file) are included.
A student can be already enrolled into some classes (classes that already have a committed solution). These classes are listed in the XML file as committed and appropriate class elements of student element are pointing to them.
Some classes of the current problem (classes that are not marked as committed) can be prohibited for the given student, e.g., due to the existing enrollments. Such classes are indicated by prohibited-class elements.
If the XML file contains a solution, resultant student sectioning is indicated in the file by class elements (of student element) pointing to these (not-committed) classes.
</timetable>
|
