Solving School Timetabling with Physics: A Simulated Annealing Approach 🏫⚛️

JefteMartins — Thu, 16 Apr 2026 17:13:16 +0000

Solving a school schedule is a classic NP-Hard problem. You have hard constraints (teacher availability) and soft constraints (minimizing "windows" or empty slots between classes).

When my fiancée, who is a teacher, struggled with a schedule that seemed impossible to solve manually, I decided to build a tool using Node.js and Electron to automate it. Here is how I used Simulated Annealing (SA) to solve what standard algorithms couldn't.

The Problem: Why Backtracking Isn't Enough

Initially, I used a Backtracking algorithm with MRV (Minimum Remaining Values). It's great for finding a valid solution, but it often gets stuck in "local minima"—states where the schedule is almost complete, but the remaining classes simply don't fit without breaking everything.

The Solution: Simulated Annealing

Inspired by metallurgy, Simulated Annealing allows the algorithm to occasionally accept "bad moves" to escape local traps, gradually "cooling down" to find a global optimum.

The Core Logic: Probability of Acceptance

The heart of the SA is the Boltzmann Equation. It decides whether to keep a swap that actually made the schedule "worse" (e.g., more missing classes) based on the current "Temperature".

// Decision based on Temperature (Boltzmann Equation)
if (deltaMissing <= 0 || Math.exp(-deltaMissing / temp) > Math.random()) {
  missingClasses = newMissingCount; // Accept the swap to explore new possibilities
} else {
  // Reject and restore previous state
  schedule[missingClass.groupId][day][slot] = classOccupantBackup;
  if (targetGroupForTeacher) {
    schedule[targetGroupForTeacher][day][slot] = teacherOccupantBackup;
  }
}

The Cooling Schedule

We start with a high temp to allow broad exploration and multiply it by a coolingRate (like 0.996) in each iteration to reduce the tolerance for "bad" moves as the algorithm converges.

let temp = 100.0;
const coolingRate = 0.996;

// At the end of each iteration
temp *= coolingRate; // Gradually becoming more restrictive

Smart Heuristics: The Human Factor

A schedule isn't just about filling slots; it's about the teacher's quality of life. I implemented a cost function to penalize "windows" (empty gaps in a teacher's day).

if (joinClasses) {
  let hasClassesToday = false;
  // ... check if teacher is already scheduled for the day

  if (hasClassesToday) {
    const isAdjacentBefore = slot > 0 && teacherBusy[profId][day][slot - 1];
    const isAdjacentAfter = slot < 7 && teacherBusy[profId][day][slot + 1];

    if (isAdjacentBefore || isAdjacentAfter) {
      cost -= 40; // Mega bonus for back-to-back classes
    } else {
      cost += 150; // High penalty for creating gaps (windows)
    }
  }
}

Results and Next Steps

The algorithm now delivers a complete, optimized schedule in seconds. By combining Backtracking for the initial state and SA for refinement, the tool handles complex restrictions that were previously a nightmare to solve by hand.

Next steps:

Migrating the heavy lifting to a dedicated .NET backend service to offload processing from the client-side.

Tech Stack: Node.js, Electron, JavaScript.
Concepts: Heuristics, Probability, Data Structures.

javascript #node #electron #algorithms #simulatedannealing #thermodynamics #code

Forem: JefteMartins

Solving School Timetabling with Physics: A Simulated Annealing Approach 🏫⚛️

javascript #node #electron #algorithms #simulatedannealing #thermodynamics #code