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.
