Introduction

In timetabling problem at Purdue University a timetable for large lecture classes is constructed by a central scheduling office in order to balance the requirements of many departments offering large classes that serve students from across the university. Smaller classes, usually focused on students in a single discipline, are timetabled by “schedule deputies” in the individual departments. Such a complex timetabling process, including subsequent student registration, takes a rather long time. Initial timetables are generated about half a year before the semester starts. The importance of creating a solver for a dynamic problem increases with the length of this time period and the need to incorporate the various changes that arise.

As for Fall 2004 semester, this problem consists of about 830 classes (forming almost 1800 meetings) having a high density of interaction that must fit within 50 lecture rooms with capacities up to 474 students. Room availability is a major constraint for Purdue. Overall utilization of the time available in rooms exceeds 78%; moreover, it is around 94% for the four largest rooms. About 90,000 course requests by almost 30,000 students must also be considered. 8.4% of class pairs have at least one student enrolment in common.

The timetable maps classes (students, instructors) to meeting locations and times. A major objective in developing an automated system is to minimize the number of potential student course conflicts which occur during this process. This requirement substantially influences the automated timetable generation process since there are many specific course requirements in most programs of study offered by the University.

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.

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).

Constraints

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.

Student Sectioning

Many courses at Purdue University consist of several sections, with students enrolled in the course divided among them. Sections are often associated together by some constraints. For example, sections of the same course should not overlap. Each such section forms one class which has its own preferences. Therefore each is treated separately - there is a variable for each section.

An initial sectioning of students into course sections is processed. This student sectioning is based on Carter's homogeneous sectioning and it is intended to minimize future student conflicts. However, there is still a possibility of improving the solution with respect to the number of student conflicts. This can be achieved via section changes during the search.

In the current implementation, sectioning is altered only by switching student enrolments between two different sections of the same course. Each student enrolment in a course with more than one section is processed. An attempt is made to switch it with a student enrolment from a different section. If this switch decreases the total number of student conflicts, it is applied.