Purdue is a large (39,000 students) public university with a broad spectrum
of programs at the undergraduate and graduate levels. In a typical term there
are 9,000 classes offered using 570 teaching spaces. Approximately 259,000 individual
student class requests must be satisfied. The complete university timetabling
problem is decomposed into a series of subproblems to be solved at
the academic department level, where the resources required to provide instruction
are controlled. Several other special problems, where shared resources or
student interactions are of critical importance, are solved institution wide. A
major consideration in designing the system has been supporting distributed
construction of departmental timetables while providing central coordination of
the overall problem. This reflects the distributed management of instructional
resources across multiple departments at the University.
Purdue University timetabling problem is naturally decomposed into
- a centrally timetabled large lecture room problem (about 800 classes being
timetabled into 55 rooms with sizes up to 474 seats),
- individually timetabled departmental problems (about 70 problems with 10
to 500 classes),
- and a centrally timetabled computer laboratory problem (about 450 classes
timetabled into 36 rooms with 20 to 45 seats).
The large lecture room problem consists of the largest classes on campus that are
attended by students from multiple departments. The problem is also very dense.
For instance, rooms are utilized on average over 70% of the available time, and
this rate increases with room size (utilization is over 85% for all rooms above 100
seats and about 97% for the four largest rooms having over 400 seats). Since there
are many interactions between this problem and the departmental problems, the
large lecture problem is solved first and the departmental problems are solved
on top of this solution.
On the opposite end of the spectrum, the computer laboratory problem is
solved at the very end of the process, on top of the large lecture room and
departmental problem solutions. It contains only small classes, most of which
have many sections (laboratories are normally the smallest subparts of a course).
A typical example is a course having one large lecture class for 100 students, two
departmental recitations with 50 students each, and four computer laboratories
of 25 students.
The departmental problems are solved more or less concurrently. These problems
are usually quite independent of one another, occurring in mostly different
sets of rooms, with separate instructors and students. However, there are some
cases with higher levels of interactions, particularly among students. In order
to address these situations, a concept referred to as "committing" solutions has
been introduced. Each user of the timetabling system (e.g., a departmental schedule
manager) can create and store multiple solutions. At the end of the process
a single solution must be selected and committed. During the commit, all conflicts
between the current solution and all other solutions that have already been
committed are checked and the commit is successful only when there are no hard
conflicts between these solutions. Each problem being solved also automatically
considers all of the previously committed solutions. This means that a room, an
instructor, or a student is available at a particular time only if that time is not
already occupied in a commited solution for a different problem. This approach
can be beneficial, for instance, in a case where there are two or more departments
with many common students. Here, the problems can be solved in an
agreed upon order (the second department will solve its problem after the first
department commits its solution). Moreover, if a room must be shared by two
departments, a room sharing matrix can be defined, stating the times during the
week that a room is available for each department to use. Finally, there is also
an option to combine two or more individual problems and solve as one larger
problem, considering all of the relations between the problems in real time.
To minimize potential time conflicts, Purdue has historically subscribed to a set of standard meeting patterns.
With few exceptions, 1 hour x 3 day per week classes meet on Monday, Wednesday, and Friday at the half hour
(7:30, 8:30, 9:30, ...). 1.5 hour x 2 day per week classes meet on Tuesday and Thursday during set time blocks. 2 or 3
hours x 1day per week classes must also fit within specific blocks, etc. Generally, all meetings of a class should be
taught in the same location. Such meeting patterns are of interest to the problem solution as they allow easier changes
between classes having the same or similar meeting patterns.
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).
There are two types of basic hard constraints:
resource constraints (expressing that only one course can be taught by an instructor or in a particular room at the
same time), and group constraints (expressing relations between several classes, e.g., that two sections of the same
lecture can not be taught at the same time, or that some classes have to be taught one immediately after another).
Except the constraints described above, there are several additional constraints which came up during our work on
this lecture timetabling problem. These constraints were defined in order to make the automatically computed timetable
solution acceptable for users from Purdue University.
First of all, if there are two classes placed one after another so that there is no time slot in between (also called
back-to-back classes), distances between buildings need to be considered. The general feeling is that different rooms
in the same building are always reasonable, moving to the building next door is to be discouraged, a couple of buildings
away strongly discouraged, and any longer distance prohibited.
Each building has its location defined as a pair of coordinates [x,y]. The distance between two buildings is estimated
by Euclides distance in such two dimensional space, i.e., (dx^2 + dy^2)^(1/2) where dx and dy are differences between
x and y coordinates of the buildings. As for instructors, two subsequent classes (where there is no empty slot in between,
called also back-to-back classes) are infeasible to teach when such difference is more than 200 meters (hard constraint).
The other options (soft constraints) are:
- if the distance is zero (same building), then no penalty,
- if the distance is above zero, but not more than 50 meters, then the placement is discouraged,
- if the distance is between 50 and 200 meters, the placement is strongly discouraged
Our concern for distance between back-to-back classes for students is different. Here it is simply a question of
whether it is feasible for students to get from one class to another during the 10-minute passing period. At present,
the distance between buildings not more than 670 meters is considered as an acceptable travel distance. For the
distance above 670 meters, the classes are considered as too far. If there is a student attending both classes, it
means a student conflict (same as when these classes are overlapping in time). The only exeption is when the
first meeting is 90 minutes long -- the acceptable travel distance is 1000 meters, since there is for 15-minute passing period.
Next, since the automatic solver tries to maximize the overall accomplishment of soft time and room constraints
(preferences), the resultant timetable might be unacceptable for some departments. The problem is that some
departments define their time and room preferences more strictly than others. The departments which have not defined
time and room preferences usually have most of their classes taught in early morning or late evening hours. Therefore,
we introduced the departmental time and room preferences balancing mechanism. The solver is trying to fulfill the time
and room preferences as well as to balance the used times between individual departments. This means that each
department should use each time unit (half-hour, e.g., Monday 7:30 – 8:00) in a similar portion to the other time
units used by the department.
Finally, since all of the classes are at least 60 minutes long, every window of empty time slots
of a room that is surrounded by classes on both sides and that is less than 60 minutes long (i.e., the room is not
used for 30 minutes between two consecutive classes) is considered useless – no other class can use it.
The number of such useless hours should be minimized. Also the situation when a room is occupied by a
class which is using less than 2/3 of its seats is discouraged. Both these
soft constraints are considered much less important than all the constraints described above.
Many course offerings consist of multiple classes, with students enrolled in the
course divided among them. These classes are often linked by a set of constraints,
namely:
- Each class has a limit stating the maximum number of students who can be enrolled in it.
- A student must be enrolled in exactly one class for each subpart of a course.
- If two subparts of a course have a parent–child relationship, a student enrolled
in the parent class must also be enrolled in one of the child classes.
Moreover, some of the classes of an offering may be required or prohibited for
certain students, based on reservations that can be set on an offering, a configuration,
or a class.
Before implementing the solver, an initial sectioning of students into classes
is processed. This sectioning is based on Carter’s homogeneous sectioning
and is intended to minimize future student conflicts. However, it is still possible
to improve on the number of student conflicts in the solution. This can be accomplished
by moving students between alternative classes of the same course
during or after the search.
In the current implementation, students are not re-sectioned during the
search, but a student re-sectioning algorithm is called after the solver is finished
or upon the user’s request.
Since students are not re-sectioned during the timetabling search, the computed
number of student conflicts is really an upper bound on the actual number
that may exist afterward. To compensate for this during the search, student conflicts
between subparts with multiple classes are weighted lower than conflicts
between classes that meet at a single time (i.e., having student conflicts that
cannot be avoided by re-sectioning).
|
