Timetable generation with constraints that actually conflict
A school in Ghaziabad has two computer labs for 1,200 students. Their 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.
We built the timetable module for their school ERP last year. 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. On a standard EC2 instance, the solver runs in 4 to 11 seconds and returns five candidate schedules.
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. This takes under a second.
The principal reviewed the first generated timetable and asked for one change: move 10-A's chemistry practical from Wednesday to Friday. The solver showed her that this would push 9-B's physics practical into a lab conflict. She kept the original schedule.