tech demo · school timetabling
The school timetable, solved with a free optimizer and examined in public
We took the public archive that academic research has used to measure itself on school timetabling for over a decade (XHSTT, maintained by the University of Twente): 25 real schools from 12 countries, each with its own rules and its best known solution published, with author and date. One of them is a Spanish school: 66 teachers, 21 groups and 225 lessons to place into 35 weekly slots.
Every September, in thousands of schools, that puzzle is solved by hand: the head of studies, a spreadsheet and weeks of juggling duty shifts, split groups and gaps until everything fits. We handed it to CP-SAT, Google's open-source optimizer, free of charge: you describe the school's rules and it searches for the best possible fit. On the Spanish school it found a timetable satisfying every mandatory rule in 0.2 seconds, on a laptop.
We have found no published CP-SAT results on this archive, and we searched hard: as far as we know, the ones on this page are the first public numbers for this solver here. The exam is measured against solutions that specialised teams have refined for years, and the scoreboard below shows how it went: certified optima in several schools and a clear defeat in Finland.
the exam · 20 minutes per school
Same budget for everyone: 20 minutes and 12 threads per school, on a laptop, a single pass. Every result is two numbers, hard violations / penalties: first the mandatory rules broken (a teacher in two places at once), then the annoyance points (gaps, badly spread sessions). The "best known" column is the best solution published by research for that school, and the gap is how many points behind it we finished. Certified optimum means the optimizer also proved that no better solution exists.
12 schools examined: certified optimum in 4. On the Spanish one, a valid timetable in 0.2 s.
Loading the exam table…
"n/a": no reference transcribed in the pilot, so the gap is not computed. The numbers come from a public JSON and update when each run finishes.
The Spanish school, up close
Instance ES-SS-08 is a real school (the weekdays in the file are in Catalan: Dilluns, Dimarts...) with 66 teachers, 21 groups, 4 shared courts and gyms and 225 lessons to place. Its rules range from the mandatory, nobody can be in two places at once, to the quality-of-life kind: keep sessions of the same subject on non-consecutive days, respect each teacher's unavailable hours.
The hard part, finding a timetable that satisfies every mandatory rule, took 0.2 seconds. The remaining 20 minutes went into polishing penalties: the exam ended at 0/437, zero violations and 437 annoyance points. The best published solution, by a Danish team using integer programming, leaves 335, and the published lower bound (the mathematical floor: nobody can go below it) is 334. We finished 102 points behind a solution with years of dedicated work behind it.
The practical reading is not the gap, it is the scale: what a school solves with weeks of staff time, a free optimizer leaves valid in under a second and decent in minutes. The remaining annoyances get negotiated with the people who know the school, which is how a timetable gets polished anyway.
The long round: no 20-minute cap
The 20 minutes are the comparable baseline: the same time for everyone. The second round removes that cap with a stopping rule declared in advance: every school not closed to optimality keeps going until the optimum is certified or until two hours pass without an improvement, whichever comes first. The full trajectory is published: every improvement with its minute, the stopping criterion and the total time. The short round stays as it is: the two tables live side by side.
The long round is under way. Each school will appear here when it finishes, with its chart: the cost dropping as the optimizer finds better timetables, drawn on the notebook's own grid.
The trajectory records the optimizer's internal objective at each improvement. The final number for each school is always the calibrated evaluator's, and across the whole exam the two matched.
How to check it
- The protocol was sealed before running: model, time budget, machine and metric were written down before the exam started, and the two possible headlines, the good one and the bad one, were drafted in advance.
- The judge is a calibrated evaluator: before solving anything, our cost evaluator had to reproduce exactly the 46 solutions with published cost from 9 schools in 8 countries, including the 335 of the Spanish case. It nailed all 46, and it was also cross-checked against KHE, the engine written by the author of the XHSTT specification, compiled separately: the same 46 costs.
- Anyone can repeat it: the data and the best solutions are public in the XHSTT archive at the University of Twente, which also accepts new solution submissions and publishes them with name and date.
The limits of this exam
Coverage is 12 of the 25 schools. The model covers the rule types of the Spanish case and its neighbours; the other 13 use mechanisms not yet modelled (teacher workload balancing, free splitting of long lessons, large-scale room assignment) and are declared out, not approximated by eye.
We compare against years of dedicated research. The archive's best solutions come from teams who do this for a living, with days of compute and hand-tuned methods. That an off-the-shelf optimizer matches several of them in 20 minutes is the news, not that it fails to beat them all.
And the exam is a laboratory one. A real school brings constraints that no public archive contains: part-time staff, teachers shared across schools, preferences nobody writes down. The benchmark proves the engine; the suit is cut to each school's own rules.
The 13 schools out of coverage, with the reason
Data: XHSTT-2014 archive (University of Twente, Gerhard Post and collaborators), no affiliation. This page's results: public JSON, generated from the exam records.
And in your company?
The timetable is not really about schools: it is about fitting scarce resources under rules that step on each other. Nursing shifts, retail rotas, university rooms and exams, a factory's weekly plan. The same engine, with your rules.
If you have a rota that gets built by hand every month and nobody dares to touch, write to us. A short first job settles it quickly, with a measurable acceptance criterion like this page's. No fluff: we will tell you whether it can be done or not.