ERP timetable: assisted generation and safe swaps¶

An ERP admin should be able to (a) move one period without breaking three others, and (b) go from an empty grid to a conflict-free week for a whole branch in one sitting instead of several days. Today neither is possible: the grid is filled one cell at a time through a modal, there is no move or swap operation at all, and the module cannot address higher-education cohorts.

This doc covers the why and the shape of the solution. It proposes a constraint solver (Google OR-Tools CP-SAT) running in the eval-service, not in the backend, and it deliberately puts the low-tech half (atomic swaps) before the solver.

Status: implemented (Phases 0–2) — PRs open to staging 2026-07-29 (webapp MySetu-AI/kwiloai_webapp#1454, eval-service MySetu-AI/kwiloai_eval_service#39). See the changelog for the as-built shape, which differs from the original proposal below: weightage lives on the curriculum, not a separate teaching_assignments store. Owner: Kantharaju. Routes: /erp/timetable (staff), /parent/timetable (guardian portal). Roles: org_admin, unit_manager, instructor (read), learner/guardian (read).

Hard dependency: erp-higher-ed-scheduling.md must land first. That doc owns the fact that timetable and exam-ops can only address a K-12 Class → Section cohort, and its non-goal 4 explicitly hands auto-generation to this doc: "Filling the grid intelligently is a separate problem; this is about being able to fill it at all." Generating a timetable for a university branch is meaningless until a university branch can be timetabled. Its recommended Option D — re-parent Section onto AcademicLevel — is also the best possible outcome for us: the generator keeps keying on section_id, every cohort in the product becomes one shape, and the solver needs zero cohort branching.

Why this exists¶

Who asked: a real college/university tenant raised it — manual period allocation does not survive a multi-branch institution. (Action: name the institution and the call date here before this doc leaves draft; the gate answer was "a real college told us" without attribution.)
User pain: two distinct pains, and the second one is not what it looks like.
Cold start. An admin filling a timetable opens a modal per cell and picks subject + teacher + types a room. For an engineering college with 6 branches × 4 years × 2 sections ≈ 48 sections × ~35 slots, that is ~1,700 modal round-trips. Admins give up and keep the timetable in Excel.
Swaps. The admin's words: "even if we make one swap, it makes things very difficult." The code explains why — there is no swap. There is no PATCH /entries/{id}, no move, no swap endpoint. Moving a period is DELETE then re-POST, two non-atomic calls; if the re-POST fails validation the original entry is already gone. And because the API raises on the first conflict it finds, the admin discovers knock-on breakage one 422 at a time instead of seeing it up front.
Cost of not doing it: blocks multi-branch college deals. The timetable is the precondition for attendance and exam operations — if setup takes weeks, the tenant never reaches the modules that make the ERP sticky, and we keep hand-seeding timetables for every pilot ourselves.
Validated or guess: validated by a tenant for the cold-start pain, and structurally validated for the swap pain — the missing endpoint is a fact in the code, not an inference.
Success signal: an admin produces a published, conflict-free week for a whole branch in one sitting and says so; and after a swap, zero faculty double-booking complaints. Sean Ellis counterfactual: remove it a week after rollout and the admin goes back to Excel immediately and tells us.

What exists today (2026-07-21)¶

Backend apps/backend/src/erp/timetable/, migration erp0005_timetable.py.

erp.periods — one bell schedule per org unit, (sequence, start, end). No break/lunch flag, no per-program schedules.
erp.timetable_entries — binds {section_id, subject_id, teacher_user_id, period_id, weekday, room}. room is free text, not an FK. Unique on (org_unit_id, section_id, period_id, weekday).
erp.substitutions — dated cover for one entry.
Conflict checks that do exist (service.py): section slot taken, teacher double-booking, room clash (exact case-sensitive string match), period overlap. Each raises on first conflict.

The blocker, owned elsewhere¶

timetable_entries.section_id FKs public.sections, the K-12 Class → Section axis, so a university branch cannot be timetabled at all today. Since this request is literally about "too many branches in a college or university," that is the first thing in the way — but it is not ours to solve. It is fully specified in erp-higher-ed-scheduling.md (gate passed the same day), and this feature simply waits for it.

Facts a generator needs that we do not store¶

Needed	Today
Weekly quota per (cohort, subject) — the "weightage"	`Subject.lecture_hours` / `lab_hours` exist on the global catalog row, capped at 10, read by no ERP code. No per-cohort override.
Who is qualified to teach what	Three competing stores (`subject_teachers`, `teacher_level_subjects`, `teachers.subject_ids`), none used by the timetable, and they key on `teachers.id` while the timetable keys on `users.id`.
Faculty availability / max load	Does not exist. No blocked slots, no max periods per day or week, no consecutive-period cap. HR `leave_applications` is never consulted.
Rooms	Free-text string. `erp.exam_rooms` exists (name + capacity) but is exam-only and unlinked.
Break / lunch slots	No `period_type` on `erp.periods`.
Draft vs published, academic year	Neither. You cannot hold next year's timetable beside this year's, or preview a generated one before it goes live.

The approach¶

Do not use an LLM to build the timetable¶

This is curriculum-based course timetabling — NP-hard, and the thing LLMs are worst at. R-ConstraintBench (arXiv 2508.15204) measures exactly this class of problem and finds accuracy collapses as constraint count grows. A wrong timetable is worse than no timetable: it silently double-books a professor and the institution finds out from students.

LLMs earn their place in two narrow spots, both of which belong in the existing chatbot microservice (per our "all LLM lives in chatbot" rule):

Natural language → constraint rows. "Dr. Rao doesn't teach Friday afternoons" becomes an availability record the admin confirms.
Explaining infeasibility in plain English, from the solver's unsat core.

Use CP-SAT (OR-Tools), not a genetic algorithm¶

Recommendation: ortools CP-SAT, Apache-2.0, pip-installable, pure-Python API over a C++ core, wheels for our Python 3.12.

Why over GA / simulated annealing — which is what most Indian school ERPs ship:

It can prove infeasibility and explain it. AddAssumptions() + SufficientAssumptionsForInfeasibility() returns a minimal set of constraints that conflict. That becomes: "You asked for 5 periods of Thermodynamics but Prof. Rao is only free 4 slots — relax one." A metaheuristic just returns a best-effort grid with 12 unexplained conflicts. For an admin-facing product this difference is the product.
It supports warm starts. AddHint() seeds the solver with the current timetable, so "repair after a swap" becomes minimal-perturbation re-solve — 3 cells move, not 300. This is the single most valuable capability for the pain the tenant actually described.
Our instances are small. ~1,700 lectures × ~35 slots ≈ 50k booleans. That is comfortable for CP-SAT — seconds to low minutes with a time limit.

Alternative considered: Timefold Solver (Apache-2.0, ex-OptaPlanner) has a first-class school-timetabling quickstart, but its Python binding runs on a JVM — a heavy dependency for our container. Keep as fallback if constraint modelling in CP-SAT gets unwieldy.

Where it runs: eval-service, never the backend¶

Decided 2026-07-21: no additional computing inside the backend. Prod backend is --cpu=2 --memory=2Gi with --session-affinity and up to 10 instances (.github/workflows/ci-cd.yml:569-575); staging is --cpu=1. A solve pegs a core for tens of seconds and would starve every co-tenant request on that instance.

Long-running work goes to the eval-service, using the queue pattern already in src/services/service_bus.py:

backend  ──enqueue {type, version, payload}──▶  Azure Service Bus
                                                      │
                                              eval-service consumer
                                                (CP-SAT solve)
                                                      │
                                    writes result + status to shared Postgres
                                                      │
backend/frontend  ◀──── polls its own DB for run status ────┘

This mirrors ingest_document exactly: deterministic message_id for dedup, W3C traceparent injected so the trace joins up in App Insights, and the worker writing status back to shared Postgres rather than calling us back. The solver code itself lands in the eval-service repo, not this one.

Solver model sketch¶

Teacher is an input, not a decision — the institution already knows who teaches what, which collapses the search space enormously. So: for each (cohort, subject) with weekly quota q, create q lecture items and assign each to a (weekday, period) slot.

Hard: exactly q lectures per (cohort, subject) per week; ≤1 lecture per cohort per slot; ≤1 lecture per teacher per slot; ≤1 lecture per room per slot; nothing in break periods; nothing in a teacher's blocked slots; labs occupy consecutive periods.
Soft (weighted objective): spread a subject across days rather than stacking it; minimise teacher idle gaps; cap consecutive teaching periods; prefer heavy subjects in the morning; balance daily load across sections.

Decompose by connected components of the faculty-sharing graph and solve components in parallel. Note that shared first-year faculty (maths, physics teaching every branch) usually couple the whole first year into one component — so decomposition helps less than it looks, which is fine at our sizes.

Evidence: solved against real staging data (2026-07-22)¶

Prototyped against the Sapthagiri University tenant in vidyanet_staging (org unit af170c61…): 2 programs, 4 branches, 28 semesters, 18 subjects, 25 curriculum rows, 25 teaching assignments, 22 instructors. Seven cohorts actually carry a curriculum. OR-Tools CP-SAT 9.15, 750 boolean variables.

The weightage gap is confirmed, not theoretical. lecture_hours and lab_hours are NULL for all 18 subjects — the field exists and nothing populates it. credits and subject_type are populated 18/18, so the prototype derived weekly periods from credits (VTU theory convention, 1 credit = 1 period/week). That is a stopgap: credits is an academic weight, not a contact-hours figure, and it cannot express a lab needing 2 consecutive periods. Phase 1 still needs a real weekly_periods column.

The shared-faculty coupling is real: Kavya Nagaraj teaches Engineering Mathematics I to CSE, ECE and ME Semester 1 simultaneously (12 periods/week); Deepa Hegde and Vinod Shetty each carry 15 periods across 4 cohorts. This is exactly Prakash's constraint in erp-higher-ed-scheduling.md.

Scenario	Result
Generate from an empty grid (88 periods/week, 7 cohorts, 6×5 grid)	OPTIMAL in 0.11 s, zero clashes, zero idle gaps, independently re-verified
Repair after Deepa Hegde becomes unavailable all Monday (3 lessons displaced)	OPTIMAL in 0.09 s, 3 cells moved out of 88 (3.4 %) — the rest of the timetable untouched
Prove impossible: force the same 88 periods into a 4×4 grid with that lecturer away 2 days	INFEASIBLE, and the solver named the minimal conflicting set — exactly her 4 lessons out of 25 — yielding "needs 15 periods/week, free for only 8"
Scale to a full university (8 branches × 8 semesters = 64 cohorts, 384 lessons, 1,216 periods/week, 16,128 booleans)	OPTIMAL in 7.6 s, zero clashes

The minimal-perturbation result is the direct answer to "one swap makes things very difficult": a disruption costs 3 changed cells, not a regenerated week. And the scale result answers "too many branches" — an instance an order of magnitude larger than the tenant solves in under eight seconds on a laptop, which is why this belongs in a queued worker rather than anywhere near a request thread.

The prototype could not write its output back. timetable_entries.section_id requires a sections row, and these cohorts are academic_levels. The solve works; the schema cannot store the answer. That is the Option D dependency, demonstrated rather than argued.

Can we just do it per department?¶

Mostly no, and the data says why. Four of twelve lecturers teach across departments and carry 58% of all teaching, which fuses CSE, ECE and ME into a single 75-period problem; only MBA separates cleanly. The scheduler's real unit is the connected component of the faculty-sharing graph, not the org chart — a lecturer teaching Maths 1 to CSE and Maths 2 to ECE couples those departments even though the subjects differ, because the clash rule is per person, not per subject.

Critically, scheduling department-by-department in sequence — what colleges do by hand today — failed 8 of 24 possible orderings on a tight grid, always starving whichever department went last. Full measurement, the CP-SAT model, and the Phase 1 schema are in erp-timetable-solver-design.md.

Phasing¶

Phase 0 — Safe swaps. No solver, no AI. Atomic PATCH /entries/{id} and a real swap endpoint in one transaction; a dry-run conflict preview that returns all conflicts instead of raising on the first; drag-and-drop move on the grid showing what breaks before you commit. This addresses the pain the tenant described most vividly and ships independently of everything below.

Phase 1 — Model the facts. (Gated on erp-higher-ed-scheduling.md Option D landing — cohort addressability is that doc's job, not this one's.) Adds weekly_periods on the cohort↔subject junction — the "weightage" the request names; one canonical teaching-assignment table resolving the users.id vs teachers.id mismatch; faculty availability + load caps; erp.rooms + FK migration off the free-text string; period_type for breaks; draft/published state and academic-year scoping. This is the real work. The solver is the easy part.

Phase 2 — Generate. solve_timetable queue message; erp.timetable_solve_runs for status/objective/diagnostics; CP-SAT in eval-service under a time limit; draft → review → publish in the UI.

Phase 3 — Repair and explain. Minimal-perturbation re-solve on disruption ("Prof. Rao is on leave Tuesday — repair the week"); unsat core → chatbot → plain-English explanation of what to relax.

Non-goals¶

Not exam timetabling. That is exam_ops, a different problem (seating, capacity, no weekly recurrence) with its own room model.
Not student-level elective scheduling / individual student timetables. We schedule cohorts, not students. Elective batch-splitting is explicitly deferred — today uq_erp_entry_section_slot makes it unrepresentable.
Not a general constraint editor. Admins pick from a fixed vocabulary of constraints with sensible defaults; arbitrary rule authoring is out.
Not fully automatic publishing. A generated timetable always lands as a draft a human reviews. No auto-publish, ever.
Not replacing manual editing. The grid stays fully hand-editable; the solver is an accelerator, not a gatekeeper.
Not changing the cohort model. Re-parenting Section onto AcademicLevel belongs to erp-higher-ed-scheduling.md; this feature consumes the result and adds no cohort branching of its own.

Rejected alternatives¶

LLM generates the grid. Rejected on evidence — see above.
Solver in the backend process. Rejected: CPU starvation of co-tenants on a 2-vCPU instance with session affinity.
Genetic algorithm / simulated annealing. Rejected: cannot explain infeasibility, and explanation is the difference between a tool admins trust and a black box they abandon.
Generate first, model the data later. Rejected: with no weekly quota, no eligibility and no availability stored, a generator has nothing to solve. Garbage in, confidently-wrong timetable out.

Metrics¶

North star: time from empty grid to published conflict-free week for one branch. Target: one sitting (< 2 hours), from the current multi-day baseline.
Guardrail: post-publish conflict/complaint rate must not rise. A fast wrong timetable is a worse product than a slow right one.
Secondary: % of tenants whose timetable is fully in Kwilo (no parallel spreadsheet); solver runs that end in a published draft vs abandoned.

Risks¶

Garbage in, garbage out. If the tenant never fills quotas and availability, output is nonsense. Mitigation: Phase 1 data-capture UX is treated as the hard problem, and the generator refuses to run on incomplete inputs rather than guessing.
Black-box distrust. Mitigation: draft/preview/publish, per-constraint explanation, and never auto-publishing.
Queue starvation. One university re-solving repeatedly could monopolise eval-service. Mitigation: per-org concurrent-run cap and solver time limit.
Regenerating over a live timetable. Mitigation: draft/published state and academic-year scoping land in Phase 1, before any generation exists.

Changelog¶

2026-07-29 — Phases 0–2 implemented; PRs open to staging. webapp MySetu-AI/kwiloai_webapp#1454, eval-service MySetu-AI/kwiloai_eval_service#39. The as-built shape refines the proposal below in one important way — there is no teaching_assignments table. A review point ("why re-enter what academic setup already captured?") moved the one genuinely new fact, the weekly class count, onto the curriculum where subjects are added.
Phase 0 — safe swaps. Atomic move/swap endpoints + a dry-run preview that returns every conflict, not the first. uq_erp_entry_section_slot made DEFERRABLE (erp0014) so an in-place swap exchanges two slots in one transaction.
Phase 1 — inputs from academic setup. weekly_periods + block_size added to level_subjects (higher ed) and class_subjects (K-12), migration 00073 — the weightage, captured when a subject is added. Only erp.timetable_solve_runs is new (erp0015, async run status + draft JSON). Generation reads curriculum weightage ⋈ teacher_level_subjects / subject_teachers (resolving teachers.id → users.id) ⋈ subjects; subjects missing a weightage or a teacher are skipped and logged.
Phase 2a — CP-SAT solver in eval-service (POST /api/v1/timetable/solve): exact quota, no cohort/teacher double-booking, consecutive lab blocks, spread + compactness objective, unsat-core infeasibility explanation. Stateless — schedules by UUIDs.
Phase 2b — orchestration. generate gathers inputs, calls the solver over HTTP (synchronous for v1; the run row is shaped for async Service Bus later), records a run; runs/{id} returns the draft grid; publish materialises it atomically, guarding against a teacher clash with cohorts not regenerated.
Phase 2c — UI. A /erp/timetable "Generate" tab (generate → review → publish, infeasibility in plain English), an editable "classes/week" column in the College Curriculum table (higher ed) and the Academic Structure subjects table (K-12).
Validation. Ran the real production solver-client against the real Sapthagiri University curriculum over live HTTP: 88 conflict-free placements, all three shared faculty in distinct slots; infeasible case returned the minimal unsat core. A synthetic 64-cohort university (16k booleans) solves in ~8 s.
Deferred (design decisions, not omissions): rooms, faculty availability/load caps, period breaks, multi-version drafts, async Service Bus dispatch, connected-component decomposition (see erp-timetable-solver-design.md).
2026-07-21 — Doc created. Product Mindset Gate passed (tenant-validated cold start; swap pain confirmed structurally in code). Architecture decided: CP-SAT in eval-service via Service Bus, no compute in the backend. Scoped against erp-higher-ed-scheduling.md, written the same day, which owns cohort addressability and hands auto-generation here via its non-goal 4.