Performance Analysis of the CP-SAT Algorithm for Practicum Scheduling Optimization Using Google OR-Tools

Abstract

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.