Course Timetabling

Published

July 4, 2024

A Resource Constrained Project Scheduling Model for Course Timetabling

Let \(I\) indexed by \(i\) be a set of \(n\) events or activities, \(T\) indexed by \(t\) be a set of time slots periods, \(M\) indexed by \(j\) a set of \(m\) machines and \(R\) indexed by \(k\) a set of \(r\) renewable resources. Each resource has unitary capacity and each event consumes either zero or one unit amount of the resources. Each event \(i\) has associated a duration \(p_i\), a release time \(a_i\), a deadline \(b_i\) and a subset of machines \(\mu_i\subseteq M\) where it can be processed.

The task is to determine for all events \(i\in I\) starting times \(x_i \in T\) and processing machines \(y_i \in \mu_i\) such that:

  • [SLOT] the starting times are within the release dates and the deadlines, ie, \(a_i\leq x_i\leq b_i\);

  • [RESCON] in each time slot the total resource consumption is less than or equal to the resource availability of each resource \(k=1,\ldots,r\);

  • [ROOM] the machine assigned processes only one event at a time.

This scheduling model finds application in course timetabling. Events are course classes. Machines are rooms. Room capacity determines the restriction to \(\mu_i\) valid rooms for each course. The time slots are non overlapping time intervals of equal duration that partition an available planning horizon (ie, the academic semester) identified by a triple \(P=\{(h, d, w) \mid h \in H, d \in D, w \in W\}\) that indicates the time, day and week when the class starts. A typical length of a slot is one hour but finer granularity is possible. Renewable resources are teachers, students and courses. Each of these resources has a capacity of one and events consume one unit of the resource if it belongs to the course, it has to be taught by the teacher and attended by the student. Constraint [RESCON], therefore, ensures that there are no overlaps for teachers and students in the timetable while constraint [ROOM] ensures that there is only one class in each room at any time.

In the instances of course timetabling, other constraints apply.

  • [PRE] preassignments of starting times and/or machines

  • [ARC] precedences \(i\rightarrow j\) meaning that event \(i\) must be scheduled before event \(j\), that is, \(x_i+p_i\leq x_i\)

  • [FRB] forbidden slots

  • [JOIN] joined events that must be scheduled together in the same room

  • [UNAV] unavailabilities of resources (teachers and machines/rooms)

Among all schedules that satisfy the requirements above the following criteria are used to determine the best ones. They are grouped by resource type:

Rooms:

  • [ROOM_STB] room stability (for subset of events - we assume the subsets to be decided in preprocessing)

  • [ROOM_DES] room desirability (capacity just above demand)

Courses:

  • [CRS_OVERLAP] avoid excess of capacity for resource of type student (aka student overlaps, this was mentioned above as a constraint, however it is in practice never possible to satisfy and hence relaxed to become a preference)

  • [CRS_STB] Weekly stability of events that belong to a course

  • [CRS_SLOT] Minimize the usage of bad slots

Teachers:

  • [TCH_SPREAD] weekly spread of events per teacher (maximize or minimize)

Students:

  • [STD_OVER] overlaps

  • [STD_WRKLD] workload per day between 0 or 3-6 hours

The relative or absolute importance of these criteria is not given. In addition, it has to be expected that individual preferences yield different importance for the criteria.