The Logic of Course Scheduling with OR-Tools

During my years of teaching, I witnessed the nightmare of every September firsthand: the course schedule. It is a process that takes days for even an experienced assistant principal in a medium-sized school, and yet only settles down after being corrected over and over following phone calls like "My two classes clash on Tuesday during the 7th period." My computer engineering side knew this was a solved class of problems; in this post, I will explain the logic behind that solution.

Why is course scheduling so hard?

Intuitively, it seems simple: place classes into time slots. But let's look at the numbers. In a school with 20 classes, 50 teachers, and 40 hours a week, there are hundreds of course blocks to be placed, and each placement constrains the others. This is a classic NP-hard scheduling problem: scanning the solution space with brute force would take longer than the lifespan of the universe, while "doing it manually with good intuition" produces either conflicts or unfair distributions.

There is also a human dimension: a teacher's day off, first/last period workload, block lesson preferences... When these are violated, the schedule "works", but no one is happy with it.

Hard vs. soft constraints

The first step in modeling is dividing the rules into two categories:

Hard constraints — can never be violated:

A teacher cannot be in two places at the same time.
A class cannot have two lessons at the same time.
A classroom cannot be assigned to two classes at the same time.
The weekly total hours of a course must equal the value in the curriculum.

Soft constraints — can be violated but will be penalized:

A teacher's preferred day off.
Balanced distribution of the same course across the week (e.g., not piling 6 hours of math onto a single day).
Block lesson preferences (e.g., two consecutive hours for laboratory classes).
Fair distribution of the first and last periods among teachers.

This distinction is not just technical, but a social contract: being able to tell a school "these are guaranteed, and these will be met as much as possible" ensures acceptance of the system.

The CP-SAT Approach

Google OR-Tools' CP-SAT solver is one of the most practical tools accessible today for these types of combinatorial problems. The core of the model is defining a boolean variable for each (class, course, hour) triplet:

from ortools.sat.python import cp_model
 
model = cp_model.CpModel()
 
# x[şube, ders, gün, saat] = 1 ise o ders o saatte işleniyor
x = {}
for s in subeler:
    for d in dersler[s]:
        for g in range(5):
            for h in range(8):
                x[s, d, g, h] = model.new_bool_var(f"x_{s}_{d}_{g}_{h}")
 
# Hard: bir şube aynı saatte en fazla bir ders alır
for s in subeler:
    for g in range(5):
        for h in range(8):
            model.add_at_most_one(x[s, d, g, h] for d in dersler[s])
 
# Hard: bir öğretmen aynı saatte en fazla bir yerde olur
for o in ogretmenler:
    for g in range(5):
        for h in range(8):
            model.add_at_most_one(
                x[s, d, g, h]
                for (s, d) in atamalar[o]
            )
 
# Hard: haftalık saat toplamı müfredata eşit
for s in subeler:
    for d in dersler[s]:
        model.add(
            sum(x[s, d, g, h] for g in range(5) for h in range(8))
            == haftalik_saat[s, d]
        )

Soft constraints, on the other hand, enter the objective function with penalty variables:

cezalar = []
 
# Soft: öğretmenin tercih ettiği boş gün
for o in ogretmenler:
    if o in bos_gun_tercihi:
        g = bos_gun_tercihi[o]
        calisiyor = model.new_bool_var(f"calisiyor_{o}_{g}")
        model.add_max_equality(
            calisiyor,
            [x[s, d, g, h] for (s, d) in atamalar[o] for h in range(8)],
        )
        cezalar.append(calisiyor * AGIRLIK_BOS_GUN)
 
model.minimize(sum(cezalar))
 
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 120
status = solver.solve(model)

The beauty of CP-SAT lies here: thanks to high-level constraints like add_at_most_one and add_max_equality, the model remains close to the language you use to describe the problem. The solver manages its own search strategy and, even within a 120-second limit, returns solutions that are "practically perfect, even if not proven optimal".

Real School Data: Where Theory Ends

Building the model is only half the battle. The other half is facing real school data:

Data is never clean. In a teacher list imported from XLSX, the same person might appear with three different spellings. Validation and matching in the import layer require as much effort as the solver itself.
Constraints cannot be written without discussion. Rules like "the gym can accommodate two classes at once, but not during ceremonies" can only be anticipated by someone who has lived the school environment. Domain knowledge directly translates to model quality here.
An infeasible result is not an error; it is a diagnosis. When a model returns with no solution, the reason is usually a demand that is also impossible in real life: an assignment trying to fit 30 hours of classes into 25 hours of availability. The system's ability to explain "which constraints conflict" builds user trust.
Weights are calibrated together. Instead of determining soft constraint weights at a desk, adjusting them based on the school's feedback to initial outputs yielded much better results.

Conclusion

The course scheduling problem stands right at the intersection of educational domain knowledge and algorithmic thinking: no matter how elegant the model is, it is useless without knowing how to ask the right constraint questions; and no matter how deep the domain knowledge is, it cannot scale without a solver like CP-SAT.

If you are working on a similar problem — whether it is a school schedule, hospital shift, or course timetable — feel free to reach out.

The Logic of Course Scheduling with OR-Tools

The Logic of Course Scheduling with OR-Tools

Related product

Ders Dağıtım Sistemi

Why is course scheduling so hard?

Hard vs. soft constraints

The CP-SAT Approach

Real School Data: Where Theory Ends

Conclusion