Skip to content

ERP timetable solver: decomposition and the data it needs

Technical companion to erp-timetable-generation.md, which owns the product case. This doc covers three things that doc deliberately leaves out: how the problem decomposes across departments, the CP-SAT model, and the Phase 1 schema the solver consumes.

Status: draft — measured 2026-07-22 against the Sapthagiri University staging tenant. No code written.

The decomposition question

"We need to tackle this per department — but faculty teach across departments and courses. Faculty A teaches Mathematics 1 to CSE and Mathematics 2 to Electronics."

Why the department boundary is the wrong unit

The solver's clash rule is per teacher, per slot. It is completely indifferent to which subject is being taught and which department owns the cohort — one person cannot be in two rooms at once. So the moment one lecturer serves two departments, those departments stop being separable problems, even though the subjects differ. Different subject, different department, same body.

The correct unit is therefore the connected component of the faculty-sharing graph: build a graph whose nodes are cohorts and whose edges join any two cohorts sharing a teacher; each connected component is one indivisible scheduling problem. Departments are an org-chart concept and have no standing here.

Measured on the real tenant

From the 25 live teaching assignments in vidyanet_staging:

cross-department faculty: 4 of 12
  Deepa Hegde     15 per/wk   CSE, ECE, ME    PH101, EC202
  Vinod Shetty    15 per/wk   CSE, ECE, ME    CS101, CS203
  Kavya Nagaraj   12 per/wk   CSE, ECE, ME    MA101
  Ravi Shankar     9 per/wk   CSE, ECE        EC101, EC203

periods taught by cross-department faculty: 51/88 (58%)

connected components: 2
  {CSE, ECE, ME} -> 75 periods/week   (inseparable)
  {MBAG}         -> 13 periods/week   (genuinely independent)

Four lecturers carrying 58% of all teaching fuse the three engineering branches into one problem. MBA detaches cleanly only because Sneha Rao and Latha Srinivasan teach nothing outside it.

This is not a quirk of the seed data. It is the standard Indian engineering college shape: first-year basic sciences (Maths, Physics, Programming) are taught by a shared faculty pool to every branch simultaneously. Coupling in the first year is the norm, not the exception.

Four strategies, measured

Tight grid (5 days x 3 periods = 15 slots), so slack cannot hide mistakes:

Strategy Result
A — Monolithic, whole org unit at once OPTIMAL, 0.02 s, zero clashes
B — Per connected component works, same quality, components run in parallel
C — Sequential by department, each locking what earlier ones booked only 16 of 24 orderings succeed
D — Two-phase: shared faculty placed globally, frozen, then departments fill in works

Strategy C is how colleges do it by hand today, and it fails a third of the time under pressure — always starving whichever department goes last:

FAILS: CSE->ECE->MBAG->ME   (stuck at ME)
FAILS: CSE->ECE->ME->MBAG   (stuck at ME)
FAILS: CSE->MBAG->ECE->ME   (stuck at ME)

That is the real-world failure mode: the last department to schedule gets an impossible grid and no explanation why. Worth stating plainly to a prospect — it reframes "your timetable process is painful" as "your process has a one-in-three failure rate."

Recommendation

  1. Compute connected components; solve each independently, in parallel. Exact — no quality loss versus monolithic. This is the honest version of "per department": the system derives the true boundary instead of assuming the org chart is it.
  2. Inside a component, solve monolithically. Don't split what the maths says is one problem. 75 periods solve in 0.02 s; a synthetic 64-cohort university (1,216 periods) in 7.6 s.
  3. Use two-phase as the human workflow, not as an optimisation. Phase 1 places the shared-faculty teaching centrally — the negotiation a university has to hold anyway. Phase 2 lets each department fill its remainder autonomously and in parallel, with shared faculty already frozen, so CSE cannot accidentally take Kavya from ME. Fallback: phase 1 is myopic — it cannot see what phase 2 will need. If any department returns infeasible, re-solve that whole component monolithically.
  4. Never sequential-without-global-awareness. That is today's process and the measurement above is the argument against it.

Editing after publish

Departments edit their own grid freely until an edit touches a shared faculty member, at which point it stops being a local change. The dry-run conflict endpoint (Phase 0) surfaces the cross-department consequence before anything is committed:

Moving CSE-S1 Maths to Wed-P2 conflicts with Kavya Nagaraj teaching ME-S1 at that slot. Options: swap with ME-S1's Wed-P2 (1 further change), or move to Thu-P1 (no further changes).

That is the minimal-perturbation solve scoped to a single cell — 0.09 s on this instance.

The CP-SAT model

One boolean per (lesson, slot), where a lesson is one (cohort, subject, teacher) assignment and a slot is a (weekday, period) pair. The teacher is an input, not a decision — the institution already knows who teaches what, which collapses the search space enormously.

Hard constraints

Constraint Meaning
sum(x[lesson, *]) == weekly_periods the weightage is met exactly
AtMostOne(x[*, slot]) per cohort a cohort is in one place at a time
AtMostOne(x[*, slot]) per teacher the cross-department rule
AtMostOne(x[*, slot]) per room rooms don't double-book
x[lesson, slot] == 0 teacher unavailable / period is a break
consecutive-pair a lab occupies a block, not scattered singles

Soft constraints (weighted, minimised): same subject twice in one day; idle periods a cohort sits through between its first and last lesson that day; late start; teacher gaps; heavy subjects in the afternoon.

Two objectives, one model. Generation minimises the quality penalty. Repair minimises distance from the current timetable (AddHint seeds the existing grid), which is what makes a disruption cost 3 cells instead of a regenerated week.

Explaining infeasibility. Wrap relaxable requirements in assumption literals; on INFEASIBLE, SufficientAssumptionsForInfeasibility() returns a minimal conflicting subset. Verified on real data: it named exactly 4 of 25 requirements, all belonging to one over-committed lecturer.

Phase 1 schema

The solver cannot run on today's data. Five gaps, and one table closes three of them.

erp.teaching_assignments — the keystone

Today "Prof X teaches Subject Y to cohort Z" lives in three competing places — subject_teachers, teacher_level_subjects, and a denormalised teachers.subject_ids array — none of which the timetable reads. Worse, all three key on teachers.id while timetable_entries keys on users.id.

One canonical table resolves the weightage gap, the eligibility gap, and the identity mismatch together:

erp.teaching_assignments
  id                uuid pk
  org_unit_id       uuid  fk org_units
  academic_year_id  uuid  fk academic_years
  section_id        uuid  fk sections      -- post-Option D this addresses
                                           -- higher-ed cohorts too
  subject_id        uuid  fk subjects
  teacher_user_id   uuid  fk users         -- users.id, matching the timetable
  weekly_periods    int   not null         -- THE WEIGHTAGE
  block_size        int   default 1        -- 2 = lab needing consecutive slots
  is_active         bool  default true
  unique (org_unit_id, academic_year_id, section_id, subject_id, teacher_user_id)

Two rows per (cohort, subject) express the common case cleanly: theory 4 periods/block 1, lab 2 periods/block 2, possibly different lecturers.

Why weekly_periods here and not on the curriculum junction: it is a property of the delivery, not the catalogue. subjects.lecture_hours / lab_hours already exist and are NULL for all 18 subjects in the tenant — optional catalogue columns nothing populates. credits is populated but is an academic weight, not contact hours, and cannot express a consecutive-block lab.

Component computation then falls out of this one table:

-- edges: two cohorts sharing a teacher
SELECT DISTINCT a.section_id AS l, b.section_id AS r
FROM erp.teaching_assignments a
JOIN erp.teaching_assignments b
  ON a.teacher_user_id = b.teacher_user_id
 AND a.section_id < b.section_id
WHERE a.org_unit_id = :ou AND a.is_active AND b.is_active;

Union-find over those edges in the worker gives the components to solve.

The other four

erp.rooms                     -- promote/extend erp.exam_rooms
  id, org_unit_id, name, capacity, room_type ('lecture'|'lab'|'seminar'), is_active
  -- timetable_entries gains room_id (nullable during migration); backfill
  -- from the free-text room string, which is matched case-sensitively today

erp.faculty_availability
  id, org_unit_id, teacher_user_id, weekday, period_id,
  kind ('blocked'|'preferred')

erp.faculty_load_limits
  teacher_user_id, max_periods_per_day, max_periods_per_week, max_consecutive

erp.periods
  + period_type ('teaching'|'break'|'assembly')
  + bell_schedule_id   -- today one schedule per org unit, so a university
                       -- cannot run different day structures per programme

erp.timetable_versions
  id, org_unit_id, academic_year_id,
  status ('draft'|'published'|'archived'), published_at
  -- timetable_entries gains version_id; the slot-uniqueness constraint
  -- becomes (version_id, section_id, period_id, weekday)

timetable_versions is not optional polish: without draft/published state there is no safe way to generate a timetable over a live one, and no academic-year scoping means a tenant cannot hold next year's grid beside this year's.

Dependency order

erp-higher-ed-scheduling Option D  (Section re-parented onto AcademicLevel)
        │
        ▼
erp.teaching_assignments  ──►  components computable, weightage stored
        │
        ├── faculty_availability + load_limits
        ├── rooms + period_type
        └── timetable_versions
                    │
                    ▼
        solver in eval-service (Phase 2)

Phase 0 (atomic move/swap + dry-run conflict preview) depends on none of this and can ship immediately.

Changelog

  • 2026-07-22 — Created. Decomposition measured on the Sapthagiri University staging tenant: 2 components, 58% of teaching done by cross-department faculty, sequential-by-department fails 8 of 24 orderings. Schema sketch derived from the gaps in erp-timetable-generation.md.