Timetabling (schools, universities, public transport)

Building a timetable means assigning lessons, exams or trips to times, rooms and people so that hard rules are never broken and preferences are met as well as possible. The core is a combinatorial optimisation problem (NP-hard) solved with constraint programming, MIP or metaheuristics, not with an LLM. AI adds value around the solver: turning rules written in prose into constraints, explaining conflicts, proposing repairs and forecasting demand.

Problem & value

• Today: many schools still plan by hand in spreadsheets or with desktop tools over days or weeks; universities combine central planning with departmental negotiation; transit agencies plan service patterns, vehicle blocks and driver duties in specialised planning suites.
• AI/solver value: feasible plans in minutes instead of days, explicit soft-constraint trade-offs (teacher gaps, student travel, room utilisation), quick re-planning when a teacher or room drops out, and transparent scoring that makes decisions easier to defend.
• Benefit figures: published vendor claims vary widely and are rarely independently verified; measure your own baseline (planning hours, hard-constraint violations, room utilisation). No generic number is given here.

Variants

• School timetabling (K-12, vocational): classes, teachers, rooms, double lessons, part-time staff, subject blocks; strongly rule-driven by state regulations.
• University course timetabling: student sectioning, large rooms, multi-week patterns, curriculum conflicts (the problem class of the International Timetabling Competition ITC 2019) [3].
• Exam timetabling: no student with two exams at once, spread exams, capacity and invigilator rules.
• Public transport: line/frequency planning, trip timetables, vehicle scheduling (blocking), crew scheduling and rostering; real-time recovery is covered in OPT-020, staff rostering in OPT-003.
• Private use: family or club schedules, e.g. shared-calendar planning (AGENT-012).

How it works

master data (teachers, rooms, classes, demand, network)
  -> constraint modelling (hard rules vs weighted soft rules)
  -> solver (CP-SAT / MIP / local search) generates candidates
  -> score + explanation (which constraints are violated, by whom)
  -> human review, manual pinning of lessons/trips, re-solve
  -> publish (SIS/LMS, parent portal, GTFS feed, driver apps)

• Solver core: constraint programming (e.g. CP-SAT) for tight feasibility problems, MIP for assignment and crew pairing with column generation, metaheuristics (local search, simulated annealing, late acceptance) for large, soft-constraint-heavy instances.
• ML around the solver: demand and ridership forecasts feed transit service levels; historical data predicts course enrolments and room no-shows (PRED family, tabular-ml/time-series).
• LLM layer: an LLM translates "Ms. X teaches only Mon-Wed, no more than two free periods per day" into structured constraints or solver code, summarises infeasibility, and answers what-if questions (see OPT-018). The LLM never produces the schedule itself; the solver validates every output.
• Human-in-the-loop: the planner fixes ("pins") assignments, approves soft-rule weights and signs off the published plan; staff and works council see the rules used.

Data preparation

Data needed: courses, teachers, rooms, capacities, equipment, enrolments and, for transit, the GTFS/NeTEx network, demand and driver rules. It typically lives in the school information system, the campus-management or ERP system, Excel sheets of the deputy head or planner, and in the heads of experienced planners. Typical gaps: constraints that exist only as unwritten rules ("Ms X never teaches Friday afternoon"), inconsistent room and equipment names, duplicate teacher records, outdated enrolment data, and teacher availability collected by e-mail or on paper.

Preparation steps: 1. Inventory sources and name an owner per source (PREP-004). 2. Write down all hard and soft constraints in a structured list; this is the most valuable step. 3. Clean master data (rooms, teachers, courses) into tidy tables (PREP-011). 4. Export from legacy systems via files or APIs (PREP-005). 5. Keep last year's timetable as a regression test for the solver.

Tools: Excel/CSV, Python with pandas, the solver's import formats. Rough share of effort: 15-25 percent, mostly constraint capture rather than technical cleaning.

Implementation paths

Which path for whom

• Public (schools, universities, municipal transport): A, because certified timetabling products (e.g. Untis, Elementary, planning modules of transit software) are mature, procurable and already speak school-information-system and GTFS formats.
• Enterprise (transport operators, large universities): B, because duty and vehicle scheduling is core, needs deep integration with own data and is best built on an OR solver plus LLM front end.
• Developer: C, because OR-Tools, Timefold or OptaPlanner run fully open-source on HW1 and keep the solver under your control.
• SMB (private schools, training providers): A, because standard timetabling is a solved product category at SMB prices.

Path A — Buy

• Schools (DACH/EU): Untis (Untis Group, Austria; EU), Stundenplan tools such as TimeTabler and aSc Timetables (aSc, Slovakia; EU), Lantiv Timetabler, Edval (Australia, widely used).
• Universities: UniTime (open-source, Apache-licensed, plus commercial hosting) [4], Scientia, CELCAT (UK/France), Infosilem, Ad Astra; campus systems such as HISinOne, CAMPUSonline.
• Public transport: Hacon/Siemens Mobility HaCon (DE; EU), PTV Group (DE; EU), GIRO HASTUS (CA), Optibus (IL), IVU Traffic Technologies (DE; EU) for planning, vehicle and crew scheduling.
• Check: EU hosting, import/export of school or HR master data, solver transparency, support for state-specific rules, price per pupil/student.

Path B — Build on cloud APIs

• Solver as a service / library: Timefold Solver (Java/Python; EU, Belgium) offers a school-timetabling quickstart and a Timefold Platform for employee/field/shift planning [1]; Google OR-Tools CP-SAT with documented timetabling examples [2]; commercial solvers Gurobi, CPLEX, FICO Xpress, or HiGHS (open).
• LLM layer: a frontier model with structured outputs (Claude, Gemini, GPT, Mistral in EU regions) to extract constraints from prose documents and produce explanations; code generation for model definitions follows the pattern of OPT-018.
• Integration: REST service in front of the solver, nightly import from the school or HR system, GTFS/NeTEx export for transit.

Path C — Self-host (open source)

• Tools: FET (free timetabling software for schools) [5], UniTime [4], Timefold Solver Community, OR-Tools, HiGHS, OptaPlanner lineage, jMetal/pymoo for custom metaheuristics.
• LLM layer (optional): an open-weight Qwen- or Mistral-class model on one GPU via vLLM/Ollama.
• Hardware: solvers run on CPU (HW1); a 16-32 core server is enough for most schools and universities; LLM helper optional on HW2.

Path D — Custom training

Seldom needed for the core. Custom ML is justified for demand forecasting, learning solver parameters/heuristics (reinforcement learning or learned neighbourhoods are active research), or for fine-tuning a small LLM to a domain-specific constraint language. Requires historic timetables and enrolments.

State of the art (2026)

• Exact + hybrid solvers dominate: CP-SAT and MIP/CP hybrids with large-neighbourhood search win most benchmark classes; the ITC 2019 instances for real university data remain the standard benchmark [3].
• Constraint streams and declarative models (Timefold, OR-Tools) let planners express rules close to business language, and make score explanations possible.
• LLM-assisted modelling: research and products translate natural-language requirements into solver models and explain infeasibility; accuracy on complex models is limited and every generated constraint must be tested against known cases.
• Learning-guided search: RL and graph neural nets propose assignments or heuristics; they help on large instances but seldom beat tuned solvers on hard feasibility.
• Limits: poor or missing master data, conflicting rules between stakeholders, and political trade-offs are the usual blockers, not computing power. Over-optimised timetables are fragile to disruption; plan slack and keep a repair mode.

Shared resources & combinations

• Shared building block: optimization-solver stack (CP-SAT, MIP, local search) reused by OPT-002 (production), OPT-003 (workforce), OPT-019 (field service), OPT-027 (projects).
• Natural combinations: OPT-018 (LLM-to-solver copilot), OPT-020 (disruption recovery on the same data), OPT-028 (demand-responsive transport), OPT-025 (traffic signals), AGENT-012 (calendar agents).
• Data pipelines: SIS/HR master-data sync and GTFS/NeTEx are shared with mobility and public-sector use cases.

Effort, cost & KPIs

• Path A: weeks to a few months incl. data cleaning; licences per school/student or per vehicle.
• Path B/C: 2-6 months for a first production model; most effort is modelling rules and stakeholder alignment, not compute. Open-source tools cost mostly staff time.
• KPIs: hard-constraint violations (target 0), weighted soft-constraint score, teacher gaps and student idle time, room utilisation, planning lead time, re-planning time after a change, for transit: vehicle and driver count, deadhead share, on-time performance, passenger waiting time.

People & change

Involve management early for scope and fairness principles, the head of timetabling as process owner, and IT for integration and accounts. Teachers and staff are the end users and are strongly affected by the result, so involve them before the pilot, not after. Works council or staff council: yes. Timetables and duty rosters affect working hours (§87(1) no. 2 BetrVG) and the system processes personal staff data, which makes §87(1) no. 6 relevant as well; inform the council in good time under §90(1) no. 3 and consider an expert under §80(3). In public schools the Personalrat or teachers' representation applies under state law. Data protection: staff and student data are personal, so involve the DPO and conclude an AVV (Art. 28 GDPR) with every processor; a DPIA (Art. 35 GDPR) is needed only if systematic evaluation of individuals is added.

AI literacy: the solver is not an LLM, so train planners on what the LLM front end can and cannot do, as a measure that supports AI literacy (AI Act Art. 4). Communicate that fairness rules are visible and adjustable. Pilot with one department or a partial plan for one term. Typical concern: "the machine decides over my schedule". Address it with transparent rules, a violation report, and the planner always approving the final plan.

See GUIDE-004, GUIDE-008 and GUIDE-005.

Risks, regulation & compliance

• EU AI Act: typically minimal risk; scheduling classrooms or trips is not in Annex III (education: admission, assessing learning outcomes, proctoring) [6]. It can become high-risk if the system allocates tasks or evaluates staff based on individual behaviour or personal traits (Annex III no. 4, employment/work allocation), or if transit scheduling is a safety component of critical infrastructure. No Art. 5 prohibition is relevant unless emotion recognition at school or work were added, which must not be done. AI literacy (Art. 4) applies.
• GDPR: teacher and student data (preferences, special-needs, part-time status, absences) is personal; health-related restrictions are special category data (Art. 9). Use data minimisation, pseudonymous IDs inside the solver, a data processing agreement and EU hosting.
• Labour law/co-determination: in Germany, works or staff councils typically must be involved (BetrVG/Personalvertretungsrecht); working-time and driving-time rules (EU Regulation 561/2006 for drivers) are hard constraints.
• Fairness and transparency: document the rules and weights; document how teachers' preferences are weighted to avoid systematic disadvantage of part-timers or carers.
• Mitigations: human sign-off, validation by an independent constraint checker, versioned plans.

Getting started

1. Collect the rule set from stakeholders and classify rules as hard or soft; write them down.
2. Clean the master data (teachers, rooms, classes) and fix last year's timetable as a benchmark.
3. Run a pilot with FET, UniTime or Timefold on one department or school year and compare to manual.
4. Add an LLM assistant for rule intake and change requests only after the solver model is stable.
5. Establish a change process (pinning, re-solve, communication) and measure the KPIs each term.

Sources

1. Timefold — Solver documentation and school timetabling quickstart — https://docs.timefold.ai
2. Google OR-Tools — CP-SAT scheduling examples — https://developers.google.com/optimization/scheduling
3. International Timetabling Competition 2019 — https://www.itc2019.org
4. UniTime — university timetabling system — https://www.unitime.org
5. FET — Free Timetabling Software — https://lalescu.ro/liviu/fet/
6. Regulation (EU) 2024/1689 (AI Act), Annex III — https://eur-lex.europa.eu/eli/reg/2024/1689/oj
7. HiGHS open-source solver — https://highs.dev
8. GTFS reference — https://gtfs.org/documentation/schedule/reference/