The Course Scheduling Problem at Bilkent University

Bilkent is a large university having two campuses, several schools and around ten thousand students. The course scheduling problem is becoming considerably more demanding each year and thus, there is a need to use advanced techniques for course timetabling.

At Bilkent, the classes can meet during the weekdays from 08:40 to 17:30. Each day there are nine time slots in which a class meeting can be scheduled. Each meeting lasts 50 minutes with a ten minute break in between classes. So the class meetings start at {8:40, 9:40,$\ldots$,16:40} and end at {9:30, 10:30,$\ldots$,17:30}. A course that requires two time slots is called a 2-hour course. In the similar manner, there are 3-, 4-, and 5-hour courses which requires three, four and five time slots, respectively.

Other than the 2-hour courses, all other courses are to be scheduled on two separate days, that is:

3-hour courses

One class meeting requires one time slot and the other one requires two consecutive time slots.

4-hour courses

Both class meetings require two consecutive time slots.

5-hour courses

One class meeting requires two consecutive time slots and the other one requires three consecutive time slots.

A course may have several sections depending upon the student enrollment in the course. If a course is to meet on two separate days, then the class meetings cannot be assigned to two consecutive days. For example, if the first class meeting is scheduled on Monday, the second class meeting can be scheduled at the earliest on Wednesday.

Each section of a course may have different class sizes ranging from 10 to 65 students. The variety in section sizes requires scheduling of class meetings in an appropriate classroom which has sufficient capacity to accommodate all students. Currently, the classrooms can be grouped into four types based on their capacity:

Type-1 classrooms

Maximum capacity of 25 students.
 

Type-2 classrooms

Maximum capacity of 30 students.
 

Type-3 classrooms

Maximum capacity of 40 students.
 

Type-4 classrooms

Maximum capacity of 65 students.

Thus, as an example, if a section has 35 students, then its class meetings can take place in a type-3 or a type-4 classroom.

Although in some other institutions instructor and course section assignments may be done by timetabling programs [3], the number of sections for each course and the instructor of each course section are known in advance at Bilkent. Further more, each course section is reserved for a specific student group. That is, for each course section, the students who can enroll are known in advance. This makes it possible to compute the number of required sections for each course prior to the course scheduling process at each semester.

Summing-up, following ten constraints are needed to comply with the conditions and requirements of Bilkent University. All these constraints are treated as if they are hard constraints at Bilkent.

1. All class meetings will be assigned to a day.
2. All class meetings will be assigned to a feasible time slot.
3. Two class meetings belonging to the same course section cannot be scheduled on two consecutive days.
4. There is a limited daily classroom capacity.
5. There are limited number of classrooms in each classroom type.
6. The course sections assigned for specific student groups cannot overlap.
7. Sections of the courses that are taught by the same instructor cannot overlap.
8. An instructor cannot teach more than a fixed number of class meeting hours per day.
9. A student can attend at most eight hours of class meetings per day.
10. All class meetings should be assigned to an appropriate size classroom.