An Improved Adaptive and Dynamic Constraint Satisfaction Model for Large-Scale Scheduling

Large-scale dynamic scheduling becomes computationally expensive when resource changes cause the complete constraint graph to be reconsidered even though only a limited part of the schedule is affected. This paper develops and evaluates an improved Adaptive and Dynamic Constraint Satisfaction Problem (A-DCSP) model that combines graph partitioning, impact localization, incremental repair, localized constraint propagation, and controlled boundary synchronization. University course timetabling was represented as a constraint graph, while lecturer- and room-unavailability events were localized through bounded graph neighbourhoods. Assignments outside the affected region remained fixed during repair, and cross-partition constraints incident to the region were checked before global schedule validation. The model was implemented in Python with Google OR-Tools and evaluated against global recomputation and global incremental propagation using the ITC-2007 comp01, comp05, and comp07 benchmark instances and deterministic synthetic workloads containing 100–2,000 courses. The evaluation comprised 486 real-benchmark observations, 108 partition-sensitivity observations, and 810 synthetic observations. On the real benchmarks, the partitioned A-DCSP reduced mean update latency by 70.6%–96.6%, inspected 68.6%–96.3% fewer variables, checked 54.6%–95.1% fewer constraints, and produced 99.1%–99.8% fewer assignment changes than global recomputation. At 2,000 synthetic courses, it inspected 4.611 variables and 23.500 constraints, with a mean update latency of 0.6422 seconds. All 1,404 observations recorded zero hard-constraint violations. The results show that event-dependent graph localization reduces update cost and schedule disruption while controlled boundary coordination maintains feasibility within a centralized software environment.