The Problem Model
The Curriculum-based timetabling problem consists in the weekly scheduling of the lectures for several university courses within a given number of rooms and time periods, where conflicts between courses are set according to the curricula published by the University and not based on enrolment data. This formulation applies to University of Udine (Italy) and too many Italian Universities, although it is slightly simplified with respect to the real problem to maintain a certain level of generality.
Description
The problem consists of the following entities:
Days, Timeslots, and Periods. We are given a number of teaching days in the week (typically 5 or 6). Each day is split in a fixed number of timeslots, which is equal for all days. A period is a pair composed by a day and a timeslot. The total number of scheduling periods is the product of the days times the day timeslots.
Courses and Teachers. Each course consists of a fixed number of lectures to be scheduled in distinct periods, it is attended by given number of students, and is taught by a teacher. For each course there is a minimum number of days that the lectures of the course should be spread in, moreover there are some periods in which the course cannot be scheduled.
Rooms. Each room has a capacity, expressed in terms of number of available seats. All rooms are equally suitable for all courses (if large enough).
Curricula. A curriculum is a group of courses such that any pair of courses in the group have students in common. Based on curricula, we have the conflicts between courses and other soft constraints.
The solution of the problem is an assignment of a period (day and timeslot) and a room to all lectures of each course.
Hard constraints
Lectures: All lectures of a course must be scheduled, and they must be assigned to distinct periods.
RoomOccupancy: Two lectures cannot take place in the same room in the same period.
Conflicts: Lectures of courses in the same curriculum or taught by the same teacher must be all scheduled in different periods.
Availabilities: If the teacher of the course is not available to teach that course at a given period, then no lectures of the course can be scheduled at that period.
Soft constraints
RoomCapacity: For each lecture, the number of students that attend the course must be less or equal than the number of seats of all the rooms that host its lectures.
MinimumWorkingDays: The lectures of each course must be spread into a minimum number of days.
CurriculumCompactness: Lectures belonging to a curriculum should be adjacent to each other (i.e., in consecutive periods). 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.
RoomStability: All lectures of a course should be given in the same room.
Last Updated: Monday, July 30, 2007 10:48 PM