Performance Analysis of the CP-SAT Algorithm for Practicum Scheduling Optimization Using Google OR-Tools
Laboratory practicum scheduling at higher education institutions involving multiple study programs, limited laboratory facilities, and complex theory class constraints constitutes a combinatorial optimization problem classified as NP-Hard. Previous studies on academic scheduling have applied various meta-heuristic and exact methods; however, few have simultaneously integrated laboratory specialization rules, multi-credit session contiguity, and theory schedule blocking within a single optimization framework. This study designs and implements an automated practicum scheduling system based on the Constraint Programming with Boolean Satisfiability (CP-SAT) method using Google OR-Tools to address the scheduling challenges at STMIK Widya Cipta Dharma. A quantitative optimization approach was employed, encompassing six systematic stages: data collection, requirements analysis, Set Theory-based data preprocessing, CP-SAT mathematical model formulation with five hard constraints and a hierarchical penalty objective function, algorithm execution, and five-aspect verification testing. The dataset comprises 22 practicum courses, 63 groups, 1,327 students, 5 laboratories, and 129 theory schedule blocking entries. The computational environment utilized an AMD Ryzen 7 8845HS processor (16 logical cores, 16 GB RAM) running Python 3.14.3 with OR-Tools 9.15.6755 on Windows 11. The CP-SAT solver processed 17,010 Boolean decision variables and achieved OPTIMAL status in 1.65 seconds, producing 102 conflict-free sessions with 100% compliance across all hard constraints and effective suppression of Saturday scheduling (Z=2.0). Resilience testing across three realistic scenarios confirmed consistent OPTIMAL status. Scalability stress testing from 129 to 329 theory blocks (26.9%–68.5% saturation) demonstrated graceful performance degradation, with the solver maintaining OPTIMAL status throughout, though objective values increased from Z=2.0 to Z=52.0 at highest saturation. Post-optimization field audit revealed that discrepancies between computed and actual schedules stem from uncoordinated student-initiated group swaps rather than algorithmic errors, highlighting the need for institutional swap-management protocols to preserve schedule optimality.
Keywords: Constraint programming, CP-SAT, Laboratory scheduling, Google OR-Tools, Timetabling.
Abdipoor, S., Yaakob, R., Goh, S. L., & Abdullah, S. (2023). Meta-heuristic approaches for the University Course Timetabling Problem. Intelligent Systems with Applications, 19, 200253. https://doi.org/10.1016/j.iswa.2023.200253
Arratia-Martinez, N. M., Maya-Padron, C., & Avila-Torres, P. A. (2021). University Course Timetabling Problem with Professor Assignment. Mathematical Problems in Engineering, 2021(1), 1–9. https://doi.org/10.1155/2021/6617177
Bashab, A., Osman Ibrahim, A., Abakar Tarigo Hashem, I., Aggarwal, K., Mukhlif, F., A. Ghaleb, F., & Abdelmaboud, A. (2023). Optimization Techniques in University Timetabling Problem: Constraints, Methodologies, Benchmarks, and Open Issues. Computers, Materials & Continua, 74(3), 6461–6484. https://doi.org/10.32604/cmc.2023.034051
Cappart, Q., Moisan, T., Rousseau, L.-M., Prémont-Schwarz, I., & Cire, A. A. (2021). Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 3677–3687. https://doi.org/10.1609/aaai.v35i5.16484
Ceschia, S., Di Gaspero, L., & Schaerf, A. (2023). Educational timetabling: Problems, benchmarks, and state-of-the-art results. European Journal of Operational Research, 308(1), 1–18. https://doi.org/10.1016/j.ejor.2022.07.011
Chen, M. C., Sze, S. N., Goh, S. L., Sabar, N. R., & Kendall, G. (2021). A Survey of University Course Timetabling Problem: Perspectives, Trends and Opportunities. IEEE Access, 9, 106515–106529. https://doi.org/10.1109/ACCESS.2021.3100613
Da Col, G., & Teppan, E. C. (2022). Industrial-size job shop scheduling with constraint programming. Operations Research Perspectives, 9, 100249. https://doi.org/10.1016/j.orp.2022.100249
De Coster, A., Musliu, N., Schaerf, A., Schoisswohl, J., & Smith-Miles, K. (2022). Algorithm selection and instance space analysis for curriculum-based course timetabling. Journal of Scheduling, 25(1), 35–58. https://doi.org/10.1007/s10951-021-00701-x
Dokeroglu, T., Kucukyilmaz, T., & Talbi, E.-G. (2024). Hyper-heuristics: A survey and taxonomy. Computers & Industrial Engineering, 187, 109815. https://doi.org/10.1016/j.cie.2023.109815
Eldharif, E. A., Sallabi, O. M., & Mosa Eltharif, A. A. (2024). An Improved Genetic Algorithm Tool for Exam Timetabling Solutions. 2024 IEEE 4th International Maghreb Meeting of the Conference on Sciences and Techniques of Automatic Control and Computer Engineering (MI-STA), 672–677. https://doi.org/10.1109/MI-STA61267.2024.10599714
Fan, H., Xiong, H., & Goh, M. (2021). Genetic programming-based hyper-heuristic approach for solving dynamic job shop scheduling problem with extended technical precedence constraints. Computers & Operations Research, 134, 105401. https://doi.org/10.1016/j.cor.2021.105401
Fatemi-Anaraki, S., Tavakkoli-Moghaddam, R., Foumani, M., & Vahedi-Nouri, B. (2023). Scheduling of Multi-Robot Job Shop Systems in Dynamic Environments: Mixed-Integer Linear Programming and Constraint Programming Approaches. Omega, 115, 102770. https://doi.org/10.1016/j.omega.2022.102770
Lailiyah, S. (2020). PENERAPAN ALGORITMA TABU SEARCH PADA SISTEM PENJADWALAN UJIAN TUGAS AKHIR MAHASISWA. Jurnal Informatika Wicida, 10(1), 1–10. https://doi.org/10.46984/inf-wcd.1193
Lan, L., & Berkhout, J. (2025). PyJobShop: Solving scheduling problems with constraint programming in Python. ArXiv Preprint ArXiv:2502.13483. https://doi.org/https://doi.org/10.48550/arXiv.2502.13483
Lavanya, A., Gaurav, L., Sindhuja, S., Seam, H., Joydeep, M., Uppalapati, V., Ali, W., & S.D, V. (2023). Assessing the Performance of Python Data Visualization Libraries: A Review. International Journal of Computer Engineering in Research Trends, 10(1), 28–39. https://doi.org/10.22362/ijcert/2023/v10/i01/v10i0104
Lemos, A., Monteiro, P. T., & Lynce, I. (2022). Introducing UniCorT: an iterative university course timetabling tool with MaxSAT. Journal of Scheduling, 25(4), 371–390. https://doi.org/10.1007/s10951-021-00695-6
Lindner, N., & Reisch, J. (2022). An analysis of the parameterized complexity of periodic timetabling. Journal of Scheduling, 25(2), 157–176. https://doi.org/10.1007/s10951-021-00719-1
Mokhtari, M., Vaziri Sarashk, M., Asadpour, M., Saeidi, N., & Boyer, O. (2021). Developing a Model for the University Course Timetabling Problem: A Case Study. Complexity, 2021(1), n/a-n/a. https://doi.org/10.1155/2021/9940866
Moreira, É. J. B., & 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. 2024 21st International Conference on Information Technology Based Higher Education and Training (ITHET), 1–8. https://doi.org/10.1109/ITHET61869.2024.10837617
Naderi, B., Ruiz, R., & Roshanaei, V. (2023). Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook. INFORMS Journal on Computing, 35(4), 817–843. https://doi.org/10.1287/ijoc.2023.1287
pandas development team, T. (2024). pandas-dev/pandas: Pandas. Zenodo. https://doi.org/10.5281/zenodo.10537285
Perron, L., Didier, F., & Gay, S. (2023). The CP-SAT-LP solver (invited talk). 29th International Conference on Principles and Practice of Constraint Programming (CP 2023), 1–3. https://doi.org/10.4230/LIPIcs.CP.2023.3
Perron, L., & Furnon, V. (2024). OR-Tools. Google. https://developers.google.com/optimization/
Rafida, V., Widiyatni, W., Harpad, B., & Yulsilviana, E. (2021). Implementation of Multi-attribute Rating Technique Simple in Selection of Acceptance Scholarship of PMDK (Case Study: STMIK Widya Cipta Dharma). International Journal of Modern Education and Computer Science, 13(1), 22–33. https://doi.org/10.5815/ijmecs.2021.01.02
Rappos, E., Thiémard, E., Robert, S., & Hêche, J.-F. (2022). A mixed-integer programming approach for solving university course timetabling problems. Journal of Scheduling, 25(4), 391–404. https://doi.org/10.1007/s10951-021-00715-5
Siew, E. S. K., Sze, S. N., Goh, S. L., Kendall, G., Sabar, N. R., & Abdullah, S. (2024). A Survey of Solution Methodologies for Exam Timetabling Problems. IEEE Access, 12, 41479–41498. https://doi.org/10.1109/ACCESS.2024.3378054
Sylejmani, K., Gashi, E., & Ymeri, A. (2023). Simulated annealing with penalization for university course timetabling. Journal of Scheduling, 26(5), 497–517. https://doi.org/10.1007/s10951-022-00747-5
Tan, J. S., Goh, S. L., Kendall, G., & Sabar, N. R. (2021). A survey of the state-of-the-art of optimisation methodologies in school timetabling problems. Expert Systems with Applications, 165, 113943. https://doi.org/10.1016/j.eswa.2020.113943
Thepphakorn, T., Kuntasup, M., & Pongcharoen, P. (2025). Moth flame optimisation based timetabling tool for educational course timetabling. International Journal of Innovation and Learning, 1(1). https://doi.org/10.1504/IJIL.2025.10067328
Waskom, M. (2021). seaborn: statistical data visualization. Journal of Open Source Software, 6(60), 3021. https://doi.org/10.21105/joss.03021
Yesin, V., Karpinski, M., Yesina, M., Vilihura, V., & Warwas, K. (2021). Ensuring Data Integrity in Databases with the Universal Basis of Relations. Applied Sciences, 11(18), 8781. https://doi.org/10.3390/app11188781
Yunusoglu, P., & Topaloglu Yildiz, S. (2022). Constraint programming approach for multi-resource-constrained unrelated parallel machine scheduling problem with sequence-dependent setup times. International Journal of Production Research, 60(7), 2212–2229. https://doi.org/10.1080/00207543.2021.1885068
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
The copyright is reserved to Research in Education, Technology, and Multiculture that is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Address:
CV. IMRECS: Jalan Gagak I, Kecamatan Larangan, Kota Tangerang. Postal Code: 15155
STKIP Al Islam Tunas Bangsa: Jalan Z.A. Pagar Alam No. 41 Gedong Meneng Bandar Lampung