如何制定学校时间表？

最后修改:2024年3月18日

by Abdullahi Ibrahim

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:

Example of a school 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:

algorithm BacktrackingForConstraintSatisfaction(csp):
    // INPUT
    //    csp = the definition of the CSP to solve (by recursively traversing its search tree)
    // OUTPUT
    //    an assignment of variables that satisfy the constraints, or failure if no solution exists

    assignment <- make an empty assignment
    
    return Backtrack(csp, assignment)

    function Backtrack(csp, assignment):
        if assignment is complete:
            return assignment

        var <- SelectUnassignedVariable(csp, assignment)
        
        for value in OrderValues(csp, var, assignment):
            if value is consistent with assignment:
                Add {var = value} to assignment
                inferences <- Inference(csp, var, assignment)
                
                if inferences != failure:
                    Add inferences to csp
                    result <- Backtrack(csp, assignment)
                    
                    if result != failure:
                        return result
                    
                    Remove inferences from csp
                
                Remove {var = value} from assignment
        
        return failure

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

In OrderValues, 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 SelectUnassignedVariable, 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:

Day

Time

Teacher

Subject

Classroom

Monday

08:00 - 09:00

Ms. Mary

Physics

Room2

09:00 - 10:00

Mr. Xi

Math

Room2

10:00 - 11:00

Mr. John

Chemistry

Room2

11:00 - 12:00

Ms. Clai

Science

Room2

12:00 - 1:00

Mr. Mike

English

Room2

Tuesday

08:00 - 09:00

Ms. Mary

Physics

Room2

09:00 - 10:00

Mr. Xi

Math

Room2

10:00 - 11:00

Mr. John

Chemistry

Room2

11:00 - 12:00

Ms. Clai

Science

Room2

12:00 - 1:00

Ms. Mike

English

Room2

Wednesday

08:00 - 09:00

Ms. Mary

Physics

Room2

09:00 - 10:00

Mr. Xi

Math

Room2

10:00 - 11:00

Mr. John

Chemistry

Room2

11:00 - 12:00

Ms. Clai

Science

Room2

12:00 - 1:00

Mr. Mike

English

Room2

Thursday

08:00 - 09:00

Ms. Mary

Physics

Room2

09:00 - 10:00

Mr. Xi

Math

Room2

10:00 - 11:00

Mr. John

Chemistry

Room2

11:00 - 12:00

Mr. Clai

Science

Room2

12:00 - 1:00

Mr. Mike

English

Room2

Friday

08:00 - 09:00

Ms. Mary

Physics

Room2

09:00 - 10:00

Mr. Xi

Math

Room2

10:00 - 11:00

Mr. John

Chemistry

Room2

11:00 - 12:00

Ms. Clai

Science

Room2

12:00 - 1:00

Mr. Mike

English

Room2

Here’s the schedule for SHS_2::

Day

Time

Teacher

Subject

Classroom

Monday

08:00 - 09:00

Mr. John

Chemistry

Room1

09:00 - 10:00

Ms. Clai

Science

Room1

10:00 - 11:00

Mr. Mike

English

Room1

11:00 - 12:00

Ms. Mary

Physics

Room1

12:00 - 1:00

Mr. Xi

Math

Room1

Tuesday

08:00 - 09:00

Mr. John

Chemistry

Room1

09:00 - 10:00

Ms. Clai

Science

Room1

10:00 - 11:00

Mr. Mike

English

Room1

11:00 - 12:00

Ms. Mary

Physics

Room1

12:00 - 1:00

Ms. Xi

Math

Room1

Wednesday

08:00 - 09:00

Mr. John

Chemistry

Room1

09:00 - 10:00

Mr. Clai

Science

Room1

10:00 - 11:00

Mr. Mike

English

Room1

11:00 - 12:00

Ms. Mary

Physics

Room1

12:00 - 1:00

Mr. Xi

Math

Room1

Thursday

08:00 - 09:00

Mr. John

Chemistry

Room1

09:00 - 10:00

Ms. Clai

Science

Room1

10:00 - 11:00

Mr. Mike

English

Room1

11:00 - 12:00

Ms. Mary

Physics

Room1

12:00 - 1:00

Ms. Xi

Math

Room1

Friday

08:00 - 09:00

Mr. John

Chemistry

Room1

09:00 - 10:00

Mr. Clai

Science

Room1

10:00 - 11:00

Mr. Mike

English

Room1

11:00 - 12:00

Ms. Mary

Physics

Room1

12:00 - 1:00

Mr. Xi

Math

Room1

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.

« 上一篇： 基础设施即代码
» 下一篇： 图的顶点着色