Timetable generation with constraints that actually conflict
Consider a school with two computer labs for 1,200 students. The principal wants Class 10-A to have mathematics first period on Tuesdays and Thursdays, and one part-time chemistry teacher is available only between 9:30 and 12:00 on Mondays, Wednesdays, and Fridays. These constraints collide in ways that make off-the-shelf timetable software produce schedules no one can use.
This is the problem the timetable module in StriveBit ERP, our school management software, is built around. The constraint solver is the part that matters, and it is not a generic algorithm.
The core problem is that most constraints in a real school are not hard boundaries — they are preferences with weight. The chemistry teacher's availability is hard: he will not show up outside his window. The principal's preference for maths first period is soft: she would like it, but the school will function without it. A lab is hard for a practical period: you cannot schedule a chemistry practical without a lab. But whether 10-A gets the lab on Tuesday or Thursday is soft.
We represent every constraint as a tuple of (scope, type, weight). Hard constraints have infinite weight — any schedule violating them is rejected. Soft constraints have a numeric weight, and the solver minimises total violation cost.
constraints = [
{"scope": "teacher:chem_pt", "type": "availability",
"slots": ["MON_1", "MON_2", "MON_3", "WED_1", "WED_2", "WED_3",
"FRI_1", "FRI_2", "FRI_3"], "weight": float("inf")},
{"scope": "class:10A", "type": "subject_first_period",
"subject": "maths", "days": ["TUE", "THU"], "weight": 50},
{"scope": "subject:chem_practical", "type": "requires_resource",
"resource": "lab_chem", "weight": float("inf")},
{"scope": "teacher:chem_pt", "type": "max_per_day",
"value": 3, "weight": 80},
]The solver itself is a constraint-propagation backtracking search with a twist: it does not stop at the first valid schedule. It generates all schedules that satisfy hard constraints, scores them on soft constraint violations, and returns the top five. The principal picks one.
This matters because the principal's preferences conflict with each other in ways she will not articulate upfront. She wants maths first period for 10-A, but she also wants English first period for 10-B, and the same maths teacher teaches both sections. The solver surfaces this: it returns a schedule where 10-A gets maths on Tuesday and 10-B gets it on Thursday, and the violation cost tells her the other preference was dropped.
Shared labs are where naive solvers break. A lab is a resource with capacity one per slot. Two sections cannot use it simultaneously, but the solver also needs to avoid scheduling a section's theory and practical for the same subject on the same day — students find that tedious. We encode that as a soft constraint with weight 30. Low enough that the solver will violate it if the alternative is a hard constraint violation, high enough that it gets respected in most schedules.
Part-time staff introduce a different problem. A part-time teacher's slots are scarce, and the solver tends to cluster them — all three of the chemistry teacher's sessions on Monday, Wednesday, and Friday first period. That is technically valid but pedagogically poor. We add a spread constraint: minimum two days between a teacher's sessions for the same class. Weight 60.
The search space for a school with 40 sections, 60 teachers, and 8 periods across 6 days is large but tractable. We prune aggressively: assign the hardest constraints first (part-time teachers, lab-bound practicals), then fill remaining slots greedily with backtracking. With that ordering, a school of this size should solve in seconds on a modest instance, not minutes, and return the five candidates for review.
We store the selected schedule as a set of (class, subject, teacher, slot, resource) rows. The timetable view reads from these rows. When a teacher's availability changes mid-term — and it does, every term — the solver regenerates only the affected sections, preserving the rest. That partial regeneration is fast enough to run interactively.
The payoff shows up in review. In our example, the principal looks at the first generated timetable and asks for one change: move 10-A's chemistry practical from Wednesday to Friday. The solver shows her that this would push 9-B's physics practical into a lab conflict. She keeps the original schedule, and she keeps it because she can see why.