Twice a year, the Interdisciplinary Humanities Center at UC Santa Barbara matches volunteer language interpreters with student-teacher conferences throughout the Goleta and Santa Barbara school districts. After a few successful iterations, the demand for interpreters increased enough to justify the application of a sophisticated scheduling system. In this project, I teamed up with the Interdisciplinary Humanities Center to develop such a system, utilizing Google’s CP-SAT Solver to arrange a schedule that fairly, conveniently and optimally pairs interpreters with student-teacher conferences.
Goals
-
Collect and organize all interpreter availability and teacher meeting requests.
-
When pairing interpreters with student-teacher conferences, the scheduling approach should be:
-
Objective-driven: A maximal number of student-teacher conferences include an interpreter.
-
Constraint-driven: Schedules are fair, convenient and practical for all interpreters and teachers.
-
-
Create and distribute personalized schedules for both interpreters and teachers.
Takeaways
-
Google’s open source software suite OR-Tools provides many useful models for constraint programming problems.
-
The solution space of all combinations matching interpreters to student-teacher conferences is huge.
-
As expected, the SAT solver does not scale efficiently and quickly grows unmanageable as input increases.
-
While unable to scale efficiently, Google’s CP-SAT Solver nonetheless provides an optimal schedule.