Curriculum-Based Course Timetabling
(University Timetabling)

Problem description

Curriculum-Based Course Timetabling is one of the most widely studied course timetabling problems.

Educational timetabling is generally defined as the task of assigning a number of events, such as lectures and examinations, to a limited set of timeslots (and perhaps rooms), subject to a given set of hard and soft constraints. Hard constraints must be strictly satisfied. Soft constraints must not necessarily be satisfied but the overall number of violations should be minimal. The educational timetabling problems can be classified into three categories:

  • school timetabling
  • examination timetabling
  • course timetabling.

Here, we focus on curriculum-based course timetabling (CB-CTT), one of the most studied course timetabling problems, as well as post-enrollment course timetabling.

Constraints

The basic entities of the CB-CTT problem are courses, rooms, days, and periods per day. A timeslot is a pair composed of a day and a period. A curriculum is a group of courses that shares common students. The CB-CTT problem is defined as the task of assigning all lectures of each course into a weekly timetable, subject to a given set of constraints: hard constraints (H1–H4, see below) and soft constraints (S1–S10). The former must be strictly satisfied. The latter are not necessarily satisfied but the sum of their violations should be minimal. From the viewpoint of violations, the soft constraints can be divided into two types: the soft constraints with constant cost (S3 and S7–S10) and the soft ones with calculated cost (S1–S2 and S4–S6). The difference is that for those with constant cost only one penalty point is imposed on each violation, whereas many penalty points calculated dynamically in accordance with each violation are imposed for those with calculated cost. A feasible solution of the problem is an assignment in which all lectures are assigned to a timeslot and a room, so that the hard constraints are satisfied. The objective of the problem is to find a feasible solution of minimal penalty costs.

The following definitions of the constraints are:

Hard constraints
  • H1. Lectures: All lectures of each course must be scheduled, and they must be assigned to distinct timeslots.
  • H2. Conflicts: Lectures of courses in the same curriculum or taught by the same teacher must be all scheduled in different timeslots.
  • H3. Room Occupancy: Two lectures cannot take place in the same room in the same timeslot.
  • H4. Availability: If the teacher of the course is unavailable to teach that course at a given timeslot, then no lecture of the course can be scheduled at that timeslot.
Soft constraints
  • S1. Room Capacity: For each lecture, the number of students that attend the course must be less than or equal the number of seats of all the rooms that host its lectures. The penalty points, reflecting the number of students above the capacity, are imposed on each violation.
  • S2. Min. Working Days: The lectures of each course must be spread into a given minimum number of days. The penalty points, reflecting the number of days below the minimum, are imposed on each violation.
  • S3. Isolated Lectures: Lectures belonging to a curriculum should be adjacent to each other in consecutive timeslots. For a given curriculum we account for a violation every time there is one lecture not adjacent to any other lecture within the same day. Each isolated lecture in a curriculum counts as 1 violation.
  • S4. Windows: Lectures belonging to a curriculum should not have time windows (periods without teaching) between them. For a given curriculum we account for a violation every time there is one window between two lectures within the same day. The penalty points, reflecting the length in periods of time window, are imposed on each violation.
  • S5. Room Stability: All lectures of a course should be given in the same room. The penalty points, reflecting the number of distinct rooms but the first, are imposed on each violation.
  • S6. Student Min Max Load: For each curriculum the number of daily lectures should be within a given range. The penalty points, reflecting the number of lectures below the minimum or above the maximum, are imposed on each violation.
  • S7. Travel Distance: Students should have the time to move from one building to another one between two lectures. For a given curriculum we account for a violation every time there is an instantaneous move: two lectures in rooms located in different building in two adjacent periods within the same day. Each instantaneous move in a curriculum counts as 1 violation.
  • S8. Room Suitability: Some rooms may be not suitable for a given course because of the absence of necessary equipment. Each lecture of a course in an unsuitable room counts as 1 violation.
  • S9. Double Lectures: Some courses require that lectures in the same day are grouped together (double lectures). For a course that requires grouped lectures, every time there is more than one lecture in one day, a lecture non-grouped to another is not allowed. Two lectures are grouped if they are adjacent and in the same room. Each non-grouped lecture counts as 1 violation.
  • S10. Room Preferability: The room that is most suitable for given course because of the necessary equipment. Each lecture of a course in an unpreferable room counts as 10 violations.

The formulation is defined as a specific set of soft constraints together with the weights associated with each of them. The CB-CTT problem is formulated as a combinatorial optimization problem whose objective function is to minimize the weighted sum of penalty points.

Example

The example of 122 courses, 21 rooms, 71 curriculums, 5 periods per day, 2 minimal lectures and 3 maximal lectures per day.

The part of the results can be found below.

The biggest example of 730 courses, 137 rooms, 3075 curriculums, 5 periods per day, 2 minimal lectures and 3 maximal lectures per day (Erlangen 1st semester 2014).

Add-ons

In addition we can consider of certain additional constraints:

  • Reduction of rooms
  • Reduction of curriculums (curricula)
  • Lunch time planning according to capacities of restaurants in the neighbourhood
  • Consideration of commuters

According to solution (timetable), several solutions for special purpose are possible:

  • Meeting planner
  • Substitutions

See more.