University Course Timetabling: Model.
Due to the set of standardized time patterns and administrative rules
enforced at the university, it is generally possible to represent all
meetings of a class by a single variable. This tying together of
meetings considerably simplifies the problem constraints. Most classes
have all meetings taught in the same room, by the same instructor, at
the same time of day. Only the day of week differs. Moreover, these
days and times are mapped together with the help of meeting patterns,
e.g., a 2 hours x 3 day per week class can be taught only on Monday,
Wednesday, Friday, beginning at 5 possible times
Or, for instance, a 1 hour x 2 day per week class can be taught only
on Monday-Wednesday, Wednesday-Friday or Monday-Friday, beginning at
10 possible times
In addition, all valid placements of a course in the timetable have a
one-to-one mapping with values in the variable's domain. This domain
can be seen as a subset of the Cartesian product of the possible
starting times, rooms, etc. for a class represented by these values.
Therefore, each value encodes the selected time pattern (some
alternatives may occur, e.g., 1.5 hour x 2 day per week may be an
alternative to 1 hour x 3 day per week), selected days (e.g., a two
meeting course can be taught in Monday-Wednesday, Tuesday-Thursday,
Wednesday-Friday), and possible starting times. A value also encodes
the instructor and selected meeting room. Each such placement also
encodes its preferences (soft constraints), combined from the
preference for time, room, building and the room's available
equipment. Only placements with valid times and rooms are present in a
class's domain. For example, when a computer (classroom equipment) is
required, only placements in a room containing a computer are present.
Also, only rooms large enough to accommodate all the enrolled students
can be present in valid class placements. Similarly, if a time slice
is prohibited, no placement containing this time slice is in the
class's domain.
As mentioned above, each value, besides encoding a class's placement
(time, room, instructor), also contains information about the
preference for the given time and room. Room preference is a
combination of preferences on the choice of building, room, and
classroom equipment. The second group of soft constraints is formed by
student requirements. Each student can enrol in several classes, so
the aim is to minimize the total number of student conflicts among
these classes. Such conflicts occur if the student cannot attend two
classes to which he or she has enrolled because these classes have
overlapping times. Finally, there are some group constraints
(additional relations between two or more classes). These may either
be hard (required or prohibited), or soft (preferred), similar to the
time and room preferences (from -2 to 2).