Fast University Timetabling via Room-wise CP-SAT Decomposition and Incremental Repair

• Éber Júnio Borges Moreira UnB
• Sérgio Antônio Andrade de Freitas UnB

DOI: https://doi.org/10.5753/semish.2026.20823

Resumo

We propose a room-wise CP-SAT decomposition with incremental repair to speed up the course timetabling problem. We solve per-room subproblems and enforce cross-room instructor non-overlap via incremental global blocking. When infeasibility arises, we apply selective rollback and a controlled fallback that preserves completeness but can introduce instructor conflicts; all runs are checked by a global validator reporting coverage, violations, and perlecture preference satisfaction. On 11 real instances from a large Brazilian public university (DS1–DS11, up to 6,278 lectures), we achieved 100% coverage in all runs and solved the largest case in seconds (4.45 s on DS11), with high preference satisfaction when fallback was not triggered (89.6% on DS11).

Referências

Ahuja, R. K., Ergun, Ö., Orlin, J. B., and Punnen, A. P. (2002). A survey of very largescale neighborhood search techniques. Discrete Applied Mathematics, 123(1–3):75–102.

Bonutti, A., De Cesco, F., Di Gaspero, L., and Schaerf, A. (2012). Benchmarking curriculum-based course timetabling: formulations, data formats, instances, validation, visualization, and results. Annals of Operations Research, 194:59–70.

Ceschia, S., Di Gaspero, L., and Schaerf, A. (2023). Educational timetabling: Problems, benchmarks, and state-of-the-art results. European Journal of Operational Research, 308(1):1–18.

Chen, M. C., Sze, S. N., Goh, S. L., Sabar, N. R., and Kendall, G. (2021). A survey of university course timetabling problem: Perspectives, trends and opportunities. IEEE Access, 9:106515–106529.

Di Gaspero, L., McCollum, B., and Schaerf, A. (2007). Curriculum based course timetabling (track 3). In Proceedings of the ICAPS 2007 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling (SSC/ITC track description). ITC-2007 Track 3 description; available online.

Di Gaspero, L. and Schaerf, A. (2003). Multi-neighbourhood local search with application to course timetabling. In Practice and Theory of Automated Timetabling IV (PATAT 2002), volume 2740 of Lecture Notes in Computer Science, pages 262–275. Springer.

Gomes, C. P., Selman, B., Crato, N., and Kautz, H. (2000). Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of Automated Reasoning, 24(1–2):67–100.

Google OR-Tools (2026). Cp-sat solver. [link]. Accessed on 2026-02-26.

McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A. J., Di Gaspero, L., Qu, R., and Burke, E. K. (2010). Setting the research agenda in automated timetabling: The second international timetabling competition. INFORMS Journal on Computing, 22(1):120–130.

Meyers, C. and Orlin, J. B. (2007). Very large-scale neighborhood search techniques in timetabling problems. In Practice and Theory of Automated Timetabling VI (PATAT 2006), volume 3867 of Lecture Notes in Computer Science, pages 24–39. Springer.

Moreira, E. J. B. and De Freitas, S. A. A. (2024). A cp-sat approach for academic resource timetabling in higher education institutions: A case study at a major public university. In 2024 21st International Conference on Information Technology Based Higher Education and Training (ITHET), pages 1–8.