IST's Timetabling Dilemma: Constraints, Variables, and Real-World Instances

3 The course timetabling problem for Instituto Superior T´ecnico

In this section, we define the course timetabling problem for IST. In Subsection 3.1, we introduce the notation for the indices. In Subsection 3.2, we provide the required parameters. In Subsection 3.3, we characterise the decision and auxiliary variables. In Subsection 3.4, we explore the constraints that determine the feasibility of the timetables. In Subsection 3.5, we present the instances solved in our work.

3.1 Indices

The indices are presented in this subsection.

– i = 1, . . . , ni , are the indices related to the lectures;

– j = 1, . . . , nj , are the indices related to the days;

– k = 1, . . . , nk, are the indices related to the hour slots in each day;

– t = 1, . . . , nt, are the indices related to the room types;

– ℓ = 1, . . . , nℓ, are the indices related to the curricula;

– p = 1, . . . , np, are the indices related to the professors;

– µ = 1, . . . , nµ, are the indices related to the campi;

3.2 Parameters

The parameters are presented in this subsection. They are divided into four groups. The first is related to associations between lectures, curricula, and professors. The second is related to lecture characteristics. The third is related to curricula and professor workloads. The fourth is related to rooms.

1. Related to associations between lectures, curricula and professors.

– aℓ ∈ {1, . . . , ni}, is the set of lectures, i, which is part of a curricula, ℓ, for all ℓ = 1, . . . , nℓ.

– bp ∈ {1, . . . , np}, is the set of lectures, i, taught by a professor, p, for all p = 1, . . . , np.

2. Related to lecture characteristics.

– ci ∈ N, is the duration of a lecture, i, in hour slots, for all i = 1, . . . , ni .

– di ∈ {1, . . . , ni}, is the set of lectures, i ̸= i, which cannot be taught on the same day as another lecture, i, for all i = 1, . . . , ni .

– ei ∈ {1, . . . , ni}, is the set of lectures, i ̸= i, which must be taught before another lecture, i for all i = 1, . . . , ni .

3. Related to curricula and professor workloads.

– mℓ ∈ N, is the maximum daily workload for a given curricula, ℓ, in number of hour slots, for all ℓ = 1, . . . , nℓ.

– op ∈ N, is the maximum daily workload for a given professor, p, in number of hour slots, for all p = 1, . . . , np.

– rℓ ∈ N, is the maximum consecutive workload for a given curricula, ℓ, in number of hour slots, for all ℓ = 1, . . . , nℓ.

– sp ∈ N, is the maximum consecutive workload for a given professor, p, in number of hour slots, for all p = 1, . . . , np.

3.3 Variables

The variables are presented in this subsection.

1. Decision variables.

– xijk ∈ {0, 1}, is 1 if a lecture, i, is taught in a day, j, and hour slot, k; and 0 otherwise, for all i = 1, . . . , ni , j = 1, . . . , nj , k = 1, . . . , nk.

2. Auxiliary variables.

– yjkℓ ∈ {0, 1}, is 1 if a curriculum, ℓ, has a lecture scheduled in a time slot, (j, k); and 0 otherwise, for all j = 1, . . . , nj , k = 1, . . . , nk, ℓ = 1, . . . , nℓ.

– yjkp ∈ {0, 1}, is 1 if a professor, p, has a lecture scheduled in a time slot, (j, k); and 0 otherwise, for all j = 1, . . . , nj , k = 1, . . . , nk, p = 1, . . . , np.

3.4 Constraints

The constraints that define the course timetabling problem at IST are presented in this subsection. They are divided into four groups. The first is related to curriculum, professor, and room availability. The second is related to curriculum and professor workloads. The third is related to campus changes. Finally, the fourth is related to lecture assignments.

1. Curriculum, professor and room availability. These constraints ensure that students, professors and rooms are available at the time of their assignments.

(a) Professor and student juxtaposition. Students in a certain curriculum, ℓ, or professors, p, do not have more than one lecture assigned at any given time.

(b) Room juxtaposition. There are enough rooms of a type, t, for the lectures, i, which must be taught in a room of that type, vit = 1.

2. Curriculum and professor workload. These constraints ensure that regulations regarding the maximum student and professor workloads are met.

(a) Maximum daily workload. In a day, j, a curriculum, ℓ, or professor, p, does not have more hour slots, k, of lectures, i, assigned than the regulations allow, mℓ and op.

(b) Maximum consecutive workloads. A curriculum, ℓ, or a professor, p, does not exceed their maximum allowed consecutive workload, rℓ or sp.

3. Lecture assignment. These constraints ensure that regulations regarding lecture assignments are met.

(a) Single assignment. Each lecture, i, is assigned to a single time slot, (j, k).

(b) Same day incompatibility. Two lectures, i and i, are not taught in the same day, j, if the regulations state that that is the case, i ∈ di .

(c) Precedence. If there is a lecture, i, which must precede another lecture, i, i.e., i ∈ ei , then, i, must be taught in the same day as i, at an earlier hour, or a previous day.

4. Campus changes. These constraints ensure that regulations regarding student or professor campus changes within the same day are met.

(a) Minimum required time. Students of a certain curriculum, ℓ, and professors, p, have enough time, uµµ, to change campus if they have two consecutive lectures, i and i, in different campi, gi ̸= gi.

3.5 Instances

The real-world instance, denoted as IST Complete, includes 4102 lectures, 644 classes and 900 professors. The lectures take place in 2 campi. There are lectures in the first trimester, lectures in the second trimester, and lectures that must be scheduled for the whole semester. The semester lectures must be taught in the same time slot in both trimesters. Thus, both trimesters must be scheduled simultaneously. Accordingly, each class has two distinct timetables, each corresponding to a different curriculum. Similarly, professors and room types must have distinct timetables for each trimester. Lecture duration ranges from one to four hours, with each hour corresponding to two time slots. When there are consecutive lectures in different campi, students and professors must have at least one free time slot in between. Students and teachers can have eight hours of lectures in a single day; of those, only five hours can be taught consecutively. To expand the computational experiments, 30 random subdivisions with 200, 250, and 300 classes were obtained from instance IST Complete. IST has two campi where lectures are taught, with 168 and 39 rooms available for teaching. However, for the subdivisions, we considered 142 and 29 rooms for the campi. Each lecture must be assigned to a specific type of room based on its capacity. Instances from the 2007 International Timetabling Competition were also adapted and tested. These instances do not include multiple campi or trimesters. Moreover, maximum consecutive workload, precedence, and different day lectures were added, and unavailable slots from the original problem were not regarded. A summary of the instances is presented in Table 1.

Since our instances include several characteristics that are not present in the competition instances, we decided to encode our instances with a different structure than the ones from ITC 2007. Specifically to facilitate the decomposition and increment procedures and to include other parameters such as lecture duration, campi, or trimester.