Problem description

The problem is described as follows:

<aside> 📖

Hi, I'm SalvadOR, responsible for creating a school timetable to organize classes, teachers, and rooms for an upcoming semester. We have some strict requirements to meet. This is a very hard problem we face every year, and I need your help to design an optimal timetable.

Here's the situation:

There are 4 classes, each requiring specific teaching sessions.
There are 4 teachers, and each teacher has assigned subjects to teach.
There are 4 rooms, and only one class can occupy a room during any given period.
The timetable spans 30 periods, and we must ensure that all requirements are met without any conflicts or overlaps.

I desperately need a timetable that satisfies all requirements (each class meets with the right teacher in the right room the required number of times), avoiding any type of clashes such as double-booking a teacher, room, or class during the same period.

We say a timetable is optimized when it minimizes idle periods and maximizes resource utilization (teachers and rooms).

</aside>

The problem is accompanied by three data files. The first one specifies the problem dimensions:

# This contains problem dimensions: 4 classes, 4 teachers, 4 rooms, 30 periods, and 120 scheduling requirements.

NUMBER OF TEACHERS =          4
NUMBER OF SUBJECTS =         20
NUMBER OF CLASSES =          4
NUMBER OF ROOM AVAILABLE =          4
NUMBER OF REQUIREMENTS =        120

The next one specifies four scheduling requirement matrices:

# A matrix specifying how often each class-teacher combination needs to meet in specific rooms.

# For instance:
# A "6" in the third row of the matrix means Class 3 must meet Teacher 4 in Room 1 six times.
# A "5" in the fifth row means Class 1 must meet Teacher 2 in Room 2 five times.

# The matrix is of the following format:
# teacher  1 2 3 4
# --------------------
# class 1: 2 2 1 2
#       2: 1 1 1 2
#       3: 1 1 1 6
#       4: 2 2 3 2 room 1
# ------------
# class 1: 2 5 1 2
#       2: 0 4 3 2
#       3: 1 2 1 0
#       4: 2 2 1 2 room 2
# ------------
# class 1: 2 1 1 2
#       2: 0 0 5 1
#       3: 2 1 4 1
#       4: 6 1 2 1 room 3
# ------------
# class 1: 3 1 2 1
#       2: 1 4 1 4
#       3: 3 3 2 1
#       4: 2 0 1 1 room 4
# ------------

2  2  1  2  
1  1  1  2  
1  1  1  6  
2  2  3  2  
2  5  1  2  
0  4  3  2  
1  2  1  0  
2  2  1  2  
2  1  1  2  
0  0  5  1  
2  1  4  1  
6  1  2  1  
3  1  2  1  
1  4  1  4  
3  3  2  1  
2  0  1  1

I was not able to fully understand the data presented in the last file. I will base my formulation on the first two files.

A CP formulation

Variables

We define a binary variable $x_{tcrp}$ to indicate whether teacher $t$ teaches to class $c$ in room $r$ in period $p$.

<aside> 🚨

There are more interesting ways of modelling this problem. One example is to introduce variables $c_{rp}$ and $t_{rp}$ to represent the class and teacher corresponding to room $r$ and period $p$. However, specifying the constraints required using Minizinc which unfortunately I do not have installed.

</aside>

Constraints

At any period, a teacher can be at most in one room
At any period, a class can be at most in one room
At any period and room, at most one teacher and one class can be present
The constraint requirement counts must be respected

Implementation

I implemented this formulation using OR-Tools

from ortools.sat.python import cp_model

num_rooms = 4
num_teachers = 4
num_classes = 4
num_periods = 30

requirements = [
   [[2, 2, 1, 2],
    [1, 1, 1, 2],
    [1, 1, 1, 6],
    [2, 2, 3, 2]],

   [[2, 5, 1, 2],
    [0, 4, 3, 2],
    [1, 2, 1, 0],
    [2, 2, 1, 2]],

   [[2, 1, 1, 2],
    [0, 0, 5, 1],
    [2, 1, 4, 1],
    [6, 1, 2, 1]],

   [[3, 1, 2, 1],
    [1, 4, 1, 4],
    [3, 3, 2, 1],
    [2, 0, 1, 1]]
]

model = cp_model.CpModel()

x = dict()
for t in range(num_teachers):
    for c in range(num_classes):
        for r in range(num_rooms):
            for p in range(num_periods):
                x[(t, c, r, p)] = model.new_bool_var(f'x_{t}_{c}_{r}_{p}')

for p in range(num_periods):
    for t in range(num_teachers):
        model.add(sum(x[t, c, r, p] 
	        for c in range(num_classes) 
	        for r in range(num_rooms)) <=1 )

for p in range(num_periods):
    for c in range(num_classes):
        model.add(sum(x[t, c, r, p] 
	        for t in range(num_teachers) 
		      for r in range(num_rooms)) <=1 )

for p in range(num_periods):
    for r in range(num_rooms):
        model.add(sum(x[t, c, r, p] 
	        for c in range(num_classes) 
	        for t in range(num_teachers)) <= 1)

for r in range(num_rooms):
    for c in range(num_classes):
        for t in range(num_teachers):
            model.add(sum(x[t, c, r, p] 
            for p in range(num_periods)) == requirements[r][c][t])

solver = cp_model.CpSolver()
solver.solve(model)
print(solver.status_name())