CP-SAT Based Fair Substitution Scheduling for Government Schools: A Deployed System Study

This paper presents an automated system for assigning substitute teachers in Indian government schools when regular teachers are absent. The traditional manual process takes one to two hours daily and creates unfair workload distribution where the same teachers are repeatedly overloaded while others are rarely asked to substitute. The system uses CP-SAT constraint programming to solve this as an optimization problem. It maximizes slot coverage while spreading substitution duty evenly across available teachers. The approach respects operational rules like matching teacher seniority to grade levels, limiting appearances per class, avoiding subject repetition, and preventing consecutive period assignments in the same classroom. A key innovation is four stage relaxation. The system first tries to satisfy all constraints strictly. If slots remain unfilled, it progressively relaxes appearance limits, subject restrictions, seniority rules, and finally uses greedy assignment for remaining gaps. This ensures maximum constraint satisfaction at each level rather than abandoning all rules at once.The system includes crisis mode for absence rates above 35 percent, progressively increasing per-teacher caps until critical slots are covered. Testing used real school timetables with simulated absences at five rates (10 to 50 percent) across six weekdays, comparing against a greedy baseline mimicking manual scheduling. In the typical 10 to 30 percent absence range, CP-SAT reduces maximum teacher load by 35 percent and workload variation by 32 percent while maintaining 99 percent fill rates and solving under 200 milliseconds. Importantly, it enforces educational validity that greedy methods ignore, preventing inappropriate assignments like senior teachers in junior classes or excessive same-class coverage. The system has been deployed in multiple Delhi government schools. Schools report near-zero scheduling time, improved fairness, reduced teacher complaints, and transparent audit trails for assignment decisions. At extreme absence rates (40 to 50 percent), greedy achieves slightly higher fill by ignoring fairness, but these scenarios trigger administrative interventions like class merging anyway. The work contributes a complete constraint programming formulation with explicit fairness, staged relaxation maintaining constraint satisfaction, crisis handling through cap escalation, quality enforcement through multiple constraint types, and real world deployment validation rather than simulation alone.