How to Make a School Timetable? | Baeldung on Computer Science

1. Introduction

Creating a school timetable is a complex task that involves assigning classes, subjects, teachers, and classrooms to specific time slots.

It’s a classic constraint-satisfaction problem (CSP), where we search for a feasible solution that satisfies all the specified constraints.

In this tutorial, we’ll show how to use a general-purpose CSP solver to create a school timetable.

2. Importance of Creating a School Timetable

Creating a school timetable is essential for efficient and organized school operations:

It helps us optimize the utilization of available resources, such as classrooms.
A well-structured timetable provides consistency in the daily schedule of school activities.
Well-designed timetables can accommodate extracurricular activities, such as sports, allowing students to engage in other educational experiences.

3. Creating a School Timetable

Before diving into the algorithm, let’s specify all the requirements and constraints for creating a timetable.

We need to determine the number of periods per day, the list of all subjects offered, teachers’ availability, and other factors to specify a timetable:

3.1. Variables

Let’s use the following notation:

$L$ is the set of available lecturers
$S$ denotes the subjects
$D$ is the set of working days in a week ( $D = \{Monday, Tuesday, \ldots, Friday\}$ )
$T = \{8{-}9 AM, 9{-}10AM, \ldots\}$ denotes time slots
$C$ is the set of classes
$R$ is the set of classrooms

For the decision variable, we let $X(l,d,t,s,c,r)$ be a binary variable that equals $1$ if a class $c$ has subject $s$ with teacher $l$ in classroom $r$ on day $d$ during the time slot $t$ . Otherwise, $X(l,d,t,s,c,r)$ is zero.

3.2. Constraints

Let’s describe the constraints.

Each class has a single lecturer for a particular subject:

(1) $\begin{equation*} \left|\left\{ l \in L | (\exists d\in D, \exists t \in T, \exists r \in R) X(l, d, t, s, c, r) = 1\right\}\right| = 1 \quad \forall c \in C, \forall s \in S \end{equation*}$

It is specified how many times a class is taught in each subject:

(2) $\begin{equation*} \sum_{l \in L} \sum_{t \in T} \sum_{d \in D} \sum_{r \in R} X(l,d,t,s,c,r) = v \in N \quad \forall c \in C, \forall s \in S \end{equation*}$

Further, for each lecturer $l$ , subject $s$ , working day $d$ , and time slot $t$ , there should be at most one class in which the lecturer teaches that subject during that specific time and day:

(3) $\begin{equation*} \sum_{c\in C} \sum_{d\in D} \sum_{t\in T} \sum_{r\in R} X(l,d,t,s,c,r)\leq 1 \quad \forall l\in L,\forall s\in S, \forall d\in D, \forall t\in T \end{equation*}$

To guarantee that for each classroom $r$ , there’s exactly one combination of lecturer, subject, working day, and time slot assigned, we require that each classroom be occupied by at most one class at any given time:

(4) $\begin{equation*} \sum_{l\in L} \sum_{d\in D} \sum_{t\in T} \sum_{c\in C} \sum_{s\in S} X(l,d,t,s,c,r) \leq 1 \quad \forall r\in R \end{equation*}$

Similar to Equation (3), each lecturer $l$ can teach at most one class at any given time slot and working day:

(5) $\begin{equation*} \sum_{c\in C} \sum_{d\in D} \sum_{t\in T} \sum_{r\in R} \sum_{s\in S} X(l,d,t,s,c,r) \leq 1 \quad \forall l\in L \end{equation*}$

We allow all classes to follow their lectures simultaneously:

(6) $\begin{equation*} \sum_{r\in R} \sum_{c\in C} \sum_{s\in S} \sum_{l\in L} X(l,d,t,s,c,r) \leq |C| \quad \forall d\in D, \forall t\in T \end{equation*}$

Finally, the decision variable $X$ (representing the assignment of a lecturer, subject, working day, time slot, classroom, and subject) must be non-negative:

(7) $\begin{equation*} X(l,d,t,s,c,r) \geq 0 \quad \forall d\in D, \forall t\in T, \forall c\in C, \forall r\in R, \forall s\in S, \forall l\in L \end{equation*}$

We designed constraints (3 – 6) with inequalities rather than strict equalities to introduce flexibility within the scheduling framework. For example, that means allowing a classroom to be empty during a period.

For simplicity, we assumed that each lecturer could teach all the subjects. However, each lecturer can teach a specific set of subjects in a real-world scenario. This doesn’t affect our approach since we can use $S(l)$ instead of $S$ to denote the subjects that $l \in L$ can teach.

3.3. Algorithm

We can use a general-purpose CSP solver:

We only have to feed it the variables and constraints specific to this problem.

In $ORDER{-}VALUES$ , we use a value-ordering heuristic. For instance, when assigning a class or classroom to a particular time slot or teacher, we prioritize those imposing the fewest constraints on the available options for other time slots and related variables.

$INFERENCE$ does forward checking. For example, when a subject is assigned to a time slot in a day and a class, we remove it from the remaining set of subjects that must be scheduled for that class. If it detects a variable has no options, we know we have to backtrack on the current assignment.

Finally, in $SELECT{-}UNASSIGNED{-}VARIABLE$ , we prioritize variables with the fewest available values.

4. Example

Let’s use the following example:

$\begin{aligned} D&= [Monday, Tuesday, Wednesday, Thursday, Friday] \\ T&=[8{-}9 AM, 9{-}10 AM, 10{-}11 AM, 11AM{-}12 PM, 12{-}1PM] \\ L&=[Mr. Mike, Mr. John, Mr. Xi, Ms. Mary, Ms. Clai] \\ S&=[Math, English, Science, Physics, Chemistry] \\ R&=[Room_1, Room_2] \\ C&=[SHS_1, SHS_2] \\ v &= 2 \\ \end{aligned}$

$SHS$ stands for senior high school.

We start with Monday, assigning to the two classrooms two teachers and subjects to two classes of students in the first time slot. Continuing like this, we get our solution. Here’s the timetable for class $SHS_1$ :

Here’s the schedule for $SHS_2$ ::

In these timetables, we ensure that the two classrooms are occupied in every time slot, with no overlapping lectures. All the other constraints are also satisfied.

5. Optimization

Any feasible timetable will do if we’re only concerned with satisfying constraints. However, there are reasons we may prefer one timetable over another. For example, teachers can ask not to have free gaps. So, a schedule where each lecturer holds classes consecutively will be preferred to the one in which there are many periods that teachers sit out between classes. Alternatively, we may want students not to take similar subjects one after another.

We don’t include such requests as constraints because the algorithm can treat many acceptable timetables as infeasible. Instead, we formulate an objective function that evaluates each schedule and indicates which is better. Optimizing it via our algorithm will give us a feasible solution that considers our preferences.

Let’s check out some examples.

5.1. Maximizing Classroom Utilization

To calculate classroom utilization, we can count the number of time slots the $i$ -th classroom is assigned and compute the utilization rate:

(8) $\begin{equation*} \text{Classroom Utilization Rate}_{i} = \frac{\text{Number of time slots the i-th classroom is assigned}}{\text{Total number of time slots}} \end{equation*}$

Then, the average classroom utilization rate ( $ACUR$ ) will be :

(9) $\begin{equation*} \text{ACUR} = \frac{1}{|R|}\sum_{i=1}^{|R|} \text{Classroom Utilization Rate}_{i} \end{equation*}$

In our example, the utilization rate is 1.0.

5.2. Balancing Teacher Workloads

Balancing teacher workloads ensures that no teacher is overburdened with too many classes while others have too few. To calculate teacher workload balance, we can compute the standard deviation of the number of classes taught by each teacher:

(10) $\begin{equation*} \sqrt{\frac{1}{|L|}\sum_{i=1}(\text{Workload}_i - \text{Average Workload})^2}} \end{equation*}$

where $\text{Workload}_{i}$ is the number of classes taught by the $i$ -th teacher, and $|L|$ is the number of teachers.

If all the teachers have approximately the same workload, the deviation will be close to zero, indicating a balanced schedule.

5.3. Balancing Teachers’ Workload by Day

We could try to distribute their teaching assignments evenly throughout the week. Balancing teachers’ workload by day aims to achieve a schedule where each lecturer teaches approximately the same number of classes daily. An uneven distribution of classes can lead to stressful peaks in a teacher’s schedule.

6. Conclusion

Creating a school timetable is a complex problem that can be effectively solved as a constraint-satisfaction problem. There are many tools for constraint-satisfaction solving, so all we have to do is formulate the constraints according to our needs.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex