Class Timetable Optimizer Constraints

Timetabling is a constraint satisfaction problem, and the arithmetic here is a necessary condition test rather than a solver. Every scheduled session simultaneously consumes one room and one teacher, so the number of sessions that can run in a single period is bounded by the smaller of those two pools. Multiplying that bottleneck by periods per day and days per week gives weekly capacity, and demand must not exceed it. This is a counting argument in the spirit of Hall's marriage theorem: passing it proves nothing, since the aggregate can balance while some subset of sessions still has nowhere to go, but failing it proves infeasibility outright, which is the more useful result because it tells an administrator exactly which resource to add. Utilization above roughly 85 to 90 percent is the practical warning zone; most institutions find that once room occupancy passes that band, satisfying the soft constraints becomes very difficult and the schedule loses the slack needed to absorb a sick teacher or a room closure. The hard constraints counted here are the three pairwise clash rules: no teacher, no room, and no student group may appear twice in the same period. Soft constraints such as preferred teaching hours, avoiding single period gaps, spreading a subject across the week, and balancing daily load are penalties rather than prohibitions, and they are what makes the problem hard in practice. The main limitation is that aggregate capacity ignores structure. Specialist requirements bind far more tightly than totals suggest: a science department may have ample general rooms but only two laboratories, and a part time teacher available on two days effectively shrinks the capacity available for every class they teach. Room seat counts, student group overlaps for elective courses, and consecutive teaching limits all restrict the true solution space beyond what this count captures.

Automated timetabling is one of the oldest applied computing problems in education. C. C. Gotlieb presented The Construction of Class-Teacher Time-Tables at the IFIP Congress in 1963, framing school scheduling as a formal assignment problem suitable for a computer, and the field has carried that framing since. The connection to graph theory followed quickly: assigning periods so that conflicting classes never coincide is a graph colouring problem, and heuristics such as the Welsh and Powell degree ordering method published in 1967 were applied directly to timetables. In 1975 Shimon Even, Alon Itai and Adi Shamir established that timetable construction is NP-complete, which explained why exact methods had struggled and legitimized the turn toward heuristics. Through the 1980s and 1990s the field consolidated. Dominique de Werra published influential surveys connecting timetabling to graph colouring and network flow, and the Practice and Theory of Automated Timetabling conference series, first held in Edinburgh in 1995 with organizers including Edmund Burke, gave the community a shared venue and a shared vocabulary of hard and soft constraints. The International Timetabling Competitions of 2002, 2007, 2011 and 2019 supplied standard benchmark instances that let metaheuristics such as simulated annealing, tabu search, and evolutionary algorithms be compared honestly against integer programming formulations. Modern practice is largely hybrid, and open constraint solvers such as Google OR-Tools CP-SAT now make the exact approaches practical for institution scale instances that were once far out of reach.