Timetabling at IMADA [pdf]

This document describes the timetabling of elective courses at IMADA, which is done quarterly. The timetable is done over a week and repeated for all weeks in the quarter. Past and current timetables are available at this link.

Data

The following entities are defined for the scheduling.

Days, Periods, and Timeslots
There are 5 teaching days in the week (from Monday to Friday). Each day is split into 5 class periods of 2 hours each, starting at 08:00 and finishing at 18:00. A timeslot is a pair composed of a day and a class period. The total number of scheduling timeslots is 25.

Courses and Lectures
Courses are divided into elective and mandatory courses. Each course consists of a fixed number of lectures to be scheduled in distinct timeslots, it is attended by a given number of students and it is taught by a teacher.

The schedule of lectures of mandatory courses is fixed and cannot be changed. This schedule may vary throughout the weeks of the teaching period.

Lectures of mandatory courses are of different types: F - Forelæsning, L - Laboratory, E - Eksaminatorier, T - Togt = excursion, P - Project, MØ - MatØk hold, etc. Moreover, for each type there might be more than one team, meaning that the same lecture is given more than once in a week and students can take one of them. MatØk students are treated as a different team and have special lectures for them identified by M.

Preassignments of elective courses are possible.

Student Enrollments
Students are enrolled to courses and can attend different combinations of them. MatØk students are included. The assignment of students to teams may or may not be known at the moment of scheduling the IMADA timetable. Instructors will be enrolled to the courses they have been assigned, thus preventing overlap with the courses they have to attend. If a team is not defined yet, the instructor is enrolled in all teams.

Teachers
Each course, elective or mandatory, has a teacher. There might be courses that are taught by the same teacher. A teacher can be unavailable for certain timeslots.

Rooms
There is only one room available and suitable for all courses: this is the IMADA's seminar room. However, if needed, other rooms can be found in the Campus. Hence lectures can be allocated to a dummy room, meaning that its location has to be decided later.

There might be some timeslots in which a room is unavailable. For example, no lecture can be scheduled in the IMADA seminar room when there is the Computer Science Colloquium or the Mathematics Colloquium.

These data are contained in a series of text files that compose the data of a specific quarter.

Scheduling process

In scheduling the lectures the following conditions must be satisfied:

  1. Only one lecture is assigned in the Seminarroom in a timeslot.

  2. Lectures must be assigned to rooms in timeslots only when rooms are ``available''.

  3. No teacher has to teach two lectures in the same timeslot or has to teach in a timeslot in which he declared to be ``unavailable''.

  4. No student has to attend more than one lecture at the same time. This includes both elective and mandatory courses.

    For mandatory courses, lectures whose type has only one team are clearly included in this condition. Lectures whose type has several teams are included by selecting only one of them at random. Since teams are not decided when IMADA timetable is done, this procedure should be enough to guarantee that a student can find at least a team to take the lecture.

  5. A course must not have more than a lecture in a day.

  6. Course preassignments in timeslots are maintained.

  7. A course must not have more than one lecture in a disadvantaged timeslot (that is, starting at 8:00 or at 16:00).

A timetable that satisfies these conditions is feasible. Violations of conditions already present in the schedule of mandatory courses are ignored (for example two mandatory courses that overlap).

In addition to the conditions above, the schedule seeks to meet as much as possible the following preference criteria.

  1. Lectures starting at 16:00 should be avoided, above all on Friday.

  2. Students should not be required to attend more than three lectures in a day.

  3. Lectures of the same course should be spread or kept close according to teacher's preferences. To this end lectures should be separated by a day distance within the minimal and the maximal value specified. For example, courses that want two lectures close each other might have min_sep=0 and max_sep=1 while courses that want lectures more uniformly spread over the week might have min_sep=2 and max_sep=4.

    Note that in the recent years the number of lectures per week increased to three, which makes the distance criterion more problematic. Currently the attempt is still to schedule lectures in consecutive days. This is a criterion hard to achieve and also not fully understood. Some teachers prefer to spread the lectures, others to schedule them close.

  4. Lectures starting at 8:00 should be avoided.

  5. Lectures on Friday starting at 14:00 should be avoided.

  6. Lectures should be scheduled in the Seminarrrum. It is however possible to schedule lectures in a another room (to be decided in a later stage among those left free at the Campus) if this is the only way to satisfy the conditions expressed above.

The problem of finding a timetable is formulated as an integer programming (IP) problem in which the conditions are imposed as constrains and the preference criteria are taken into account by a weighted sum that makes the objective function to be minimized.

Each preference criteria contributes to the objective function by a score which is given by the number of students involved. However, in all criteria where discomfort may affect both the teacher and the students, the score of a lecture that violates a criterion is given by SL+A, where SL is the number of students attending the lecture and A is a parameter determining the influence of the teacher (currently it is set to 1).

Starting weights for each criterion are set as follows: 10000 for teachers with more than a lecture in the same day, 2000 for lectures on Friday at 16, 100 for lectures at 16. All the remaining weights are set to 1. Changes of weights are to be expected.

If a feasible solution is not found some hard constraints are progressively relaxed until a feasible solution is found. In the order the constrains relaxed are:

Relaxed criteria are brought in the objective function weighted by a very high weight.

Implementation details


Marco Chiarandini 2011-06-22