Timetable Scheduling — Problem Formalization (v3)¶

The timetable problem: place every required lesson into a weekly slot, assign it a room and a teacher. The solver works from curriculum definitions and estimated enrollment — no student lists are needed. Teacher assignments can be partially locked by the admin; the solver optimizes the rest.

1. Building Blocks¶

1.1 School Organization¶

School — the top level.
Department — a self-contained part of the school (Primary, Middle School, High School). Each department has its own daily rhythm and is configured with two settings (see below).
Grade — a year level within a department (Grade 1, Year 7, Year 10…).
Homeroom — an administrative class group within a grade (1A, 1B, 2A…). Whether homerooms exist and how much weight they carry depends on the department configuration.

Department Configuration¶

Each department has two independent settings.

Setting 1 — Homeroom role.

Level	Homerooms exist	Homeroom teacher	Base room	Scheduling weight
None	✗	✗	✗	—
Administrative	✓	✓ (reference/tutor)	Optional	None — purely organizational
Scheduling-active	✓	✓ (mandatory)	✓ (mandatory)	First-slot hard constraint

Setting 2 — Scheduling mode.

Mode	How the admin defines the curriculum
Homeroom-derived	Curriculum per grade; students mostly stay with their homeroom. Admin marks exceptions (split disciplines, option blocks).
Track-and-block	Curriculum per track within a grade; students grouped by track and subject choice. Admin defines option blocks and cross-track disciplines.

Valid combinations:

Homeroom role	Scheduling mode	Example
Scheduling-active	Homeroom-derived	Primary
Scheduling-active	Track-and-block	Middle School with morning homeroom
Administrative	Track-and-block	High School with tutor groups
Administrative	Homeroom-derived	Unusual — homerooms as groups without scheduling weight
None	Track-and-block	High School, no homerooms

(None + homeroom-derived is invalid.)

🎨 UX — two questions at department creation:

"What role do homerooms play?" — No homerooms / Admin purposes only / Anchor the school day

"How is the timetable structured?" — Students stay with their homeroom / Students grouped by track and subject choice

1.2 Academic Year¶

A timetable is built for a specific academic year (e.g., 2025–2026), defined by a name, start date, and end date.

1.3 Rooms¶

Each room has:

A name or code
A maximum capacity
Optionally, a designated department (priority access, others can use when free)
Optionally, a designated discipline (only that discipline can use the room — hard rule)

Three tiers of access: discipline-locked → department-priority → shared.

No homeroom permanently occupies a room. When homerooms are scheduling-active, the base room is a default gathering point, not a permanent reservation.

1.4 The Shape of a Day¶

Each department defines its own daily structure, which can vary by day of the week.

A day template is an ordered sequence of time slots, each with a start time, end time, and type (lesson, break, or lunch). Slot durations are not uniform — a department can mix 45-minute, 60-minute, and 90-minute lessons in the same day.

Primary (09:00–15:00): Lesson 45′ → Lesson 45′ → Break 30′ → Lesson 60′ → Lunch 60′ → Lesson 45′ → Lesson 45′ → Break 30′ → Lesson 45′

Middle School (08:00–14:00): Lesson 60′ → Lesson 60′ → Break 20′ → Lesson 90′ → Lunch 40′ → Lesson 60′ → Lesson 60′

1.5 Kitchen Shifts¶

The kitchen is a shared bottleneck with a limited number of lunch shifts, each with a time window and a maximum student capacity. Every homeroom (or grade) is assigned to one shift. Kitchen shifts must be set before timetable generation.

1.6 Disciplines and Curriculum¶

A discipline is a subject (English, Mathematics, PE…).

A curriculum defines the weekly teaching requirements per grade or per track:

Which disciplines must be taught
Minutes per week per discipline (the system maps this to slots based on the day template)
Whether consecutive slots are preferred (double periods)

Curriculum tracks. In some departments, multiple tracks coexist within a grade (e.g., IGCSE and IB in Year 10). Each track has its own subject requirements. In departments without explicit tracks, there is one default track per grade.

Option blocks. Disciplines that must run simultaneously so students can choose one ("Block A: Art / Music / Drama"). All disciplines in a block occupy the same time slot.

Cross-track disciplines. Disciplines shared across tracks ("PE is taken by both IGCSE and IB students together").

Estimated enrollment. For each grade or track, the admin provides an estimated number of students (typically from the previous year plus a margin). The solver uses this, combined with room capacities, to determine whether a discipline needs parallel lessons — e.g., 50 students need Math, largest suitable room holds 25, so the solver schedules 2 simultaneous Math lessons per required slot.

1.7 Teachers¶

Each teacher has:

A maximum weekly teaching load (contractual cap, shared across departments). Can be exceeded with approval (see Section 2.3).
Qualifications — which disciplines they can teach, per department.
Availability — days and time windows when they can be scheduled.
Supervision duties — assigned break/lunch slots. Count toward the weekly teaching load. Block the teacher from teaching or substituting during that slot.
Non-teaching duties — coordination roles (department head, counselor). Tracked as separate hours that do not subtract from the teaching maximum. May reduce stated availability (e.g., "Thursday mornings blocked for department meetings").

A teacher can work across multiple departments. External or visiting teachers have the same model but typically narrow availability.

Supervision Staffing¶

Each break/lunch slot has a required supervisor count (configurable, always less than the number of groups on break). The system assigns teachers from the available pool. A supervision assignment blocks that teacher for the full break/lunch duration.

1.8 Teacher Assignments¶

Teacher assignments link teachers to disciplines for a given grade or track. Assignments are partial — the admin locks what they care about, the solver fills the rest.

Each discipline × grade/track has one of three states:

Locked — the admin assigns a specific teacher. The solver must respect this. If parallel lessons are needed, the locked teacher gets one; the solver fills the others from the qualified pool.
Open — no teacher assigned. The solver picks from qualified teachers, optimizing for load balance, availability, and compactness.
Open with preference — the admin indicates a preferred teacher. The solver treats this as a soft goal, not a hard lock.

Locked variants:

Co-teaching — two teachers simultaneously for the same lesson.
Alternation — two teachers alternate on different days.

Post-generation editing. The admin can always manually swap teachers for individual slots after generation, regardless of how the original assignment was made.

🎨 UX. A matrix (grades/tracks × disciplines) where cells are: teacher name (locked), empty (open), or teacher name with "preferred" indicator. Live validation for overload, qualifications, availability. After generation, solver-assigned teachers shown in a distinct style; all cells editable.

1.9 The Year Calendar¶

Once the weekly timetable is built, it projects onto the academic year. Each date is:

Regular — normal weekly timetable applies
Holiday — no classes
Extra — no classes, open for extra activities

Specific dates can override the day template ("December 20th is a short day").

2. The Scheduling Problem¶

2.1 What Are We Solving?¶

Inputs (human decisions):

Curriculum per grade/track: disciplines, weekly minutes, option blocks, cross-track disciplines.
Estimated enrollment per grade/track.
Rooms with capacities and designations.
Day templates per department.
Teachers with qualifications, availability, and load limits.
Locked teacher assignments (optional).
Homeroom configuration.

The solver determines:

Parallelism: how many simultaneous lessons of each discipline are needed per grade/track (from estimated enrollment ÷ room capacities).
When: a day and time slot for every lesson.
Where: a room for every lesson.
Who: a teacher for every lesson (respecting locks, optimizing the rest).

The solver also ensures teacher consistency — all lessons of the same discipline for the same grade/track are taught by the same teacher across the week, unless co-teaching or alternation is specified.

2.2 Hard Constraints¶

A valid timetable must satisfy all of these.

No teacher cloning. A teacher cannot be in two places at once. Checked by actual clock time, not slot number (departments can have overlapping grids).

No conflicts within an enrollment group. Lessons targeting the same enrollment group (homeroom in homeroom-derived mode, track+grade in track-and-block mode) cannot overlap — except for option block disciplines, where each student attends one.

No room double-booking. One lesson per room at a time.

Room discipline lock. If a room is designated to a discipline, only that discipline uses it.

Option block disciplines are simultaneous. All disciplines within an option block occupy the same slot for the same grade/track.

Every lesson has a room. Each lesson is assigned exactly one room.

Curriculum fully covered. Every discipline meets its required weekly minutes per grade/track.

Teacher qualifications respected. Teachers only teach disciplines they're qualified for.

Teacher availability respected. No lessons outside a teacher's available windows.

Locked assignments respected. The solver cannot override a locked teacher assignment.

Every lesson has a teacher. At least one teacher assigned per lesson — locked or solver-chosen.

Kitchen shift capacity. Student count per shift does not exceed capacity.

Homeroom first slot (scheduling-active only). The homeroom teacher teaches their homeroom in the first lesson slot of every day.

Maximum 4 consecutive teaching slots. A teacher cannot teach more than 4 slots in a row without an intervening break or free slot.

Contiguity when specified. If the curriculum marks a discipline as requiring consecutive slots (e.g., double periods), the solver must schedule them back-to-back. This is a hard constraint only when contiguity is explicitly requested.

No room changes within enrollment group (per department). Configurable per department as a hard constraint. When enabled (typical for Primary), all lessons for the same enrollment group in a day take place in the same room — students never move. When disabled, room changes are allowed but minimized as a soft goal (see Section 2.4).

2.3 Soft-Hard Constraints (Overridable)¶

Hard by default, but an authorized person can approve exceptions. The system tracks who approved and why.

Teacher weekly load. Should not exceed the contractual maximum, but can with approval.

Room department priority. Department-designated rooms used by that department first. Others may use them when free. Overridable per case.

2.4 Soft Constraints (Optimization Goals)¶

A timetable is better if it satisfies more of these, but it's still valid if it doesn't.

Minimize room changes within enrollment groups (high). Fewer room transitions per day. When not enforced as a hard constraint per department (see Section 2.2), the solver still minimizes transitions.
Distribute substitution availability (medium). Spare teacher slots spread across different times and days, not clustered on Friday afternoon. Idle mid-day slots are valuable — they serve as substitution capacity and time for other duties.
Prefer department-designated rooms (low). Use the department's own rooms when possible.

3. What the Admin Does¶

The admin defines structure, curriculum, and enrollment estimates. The solver handles everything else.

3.1 Homeroom-Derived Mode¶

Create homerooms for each grade.
Enter curriculum — disciplines and weekly hours per grade.
Provide estimated enrollment per homeroom (or per grade, distributed evenly). Typically previous year's numbers plus a margin.
Mark split disciplines — where students leave their homeroom for a different grouping (e.g., "Foreign Languages").
For each split, define the options ("Spanish, French, Mandarin" — running as an option block).

The admin's mental model: homerooms + curriculum + a few splits. They don't think about parallelism or scheduling — the solver handles that.

🎨 UX — two-step flow per grade:

Curriculum grid auto-populates: every homeroom gets every discipline.

Admin marks exceptions as "split" and defines the parallel options.

3.2 Track-and-Block Mode¶

Define curriculum tracks (IGCSE, IB, etc.). Single-path grades have one default track.
Enter subjects and hours per track.
Provide estimated enrollment per track.
Define option blocks — subjects that run simultaneously.
Mark cross-track disciplines ("PE shared across tracks").

The admin thinks in tracks, subjects, and blocks. Parallelism is the solver's problem.

🎨 UX — wizard:

Define tracks

Subjects and hours per track

Estimated enrollment per track

Option blocks

Cross-track disciplines

Teacher assignments happen after this, in the assignment matrix (Phase 3).

3.3 Homerooms + Track-and-Block¶

Scheduling-active homerooms: First slot is anchored — students gather with their homeroom teacher. From slot 2, they follow the track-and-block structure. The admin picks which discipline the homeroom teacher teaches in slot 1.

Administrative homerooms: No scheduling effect. All slots follow track-and-block.

3.4 Summary¶

Homeroom role	Scheduling mode	Admin provides	Solver determines
Scheduling-active	Homeroom-derived	Homerooms, curriculum, estimates, splits	Parallelism, slots, rooms, teachers
Scheduling-active	Track-and-block	Homerooms, tracks, subjects, estimates, blocks	First-slot lessons + all track lessons, parallelism, slots, rooms, teachers
Administrative	Track-and-block	Homerooms (admin only), tracks, subjects, estimates, blocks	All lessons, parallelism, slots, rooms, teachers
None	Track-and-block	Tracks, subjects, estimates, blocks	All lessons, parallelism, slots, rooms, teachers

4. Setup Phases¶

Phase 1 — Structure. Departments (with settings), grades, homerooms, day templates, kitchen shifts, rooms.

Phase 2 — Curriculum and enrollment. Curriculum per grade/track, option blocks, cross-track disciplines, split exceptions, estimated enrollment.

Phase 3 — Teacher assignments (partial). Lock preferences, leave the rest open.

Phase 4 — Kitchen shift allocation. Assign homerooms/grades to shifts.

Phase 5 — Generate timetable. Solver runs.

Phase 6 — Supervision duties. Assign teachers to break/lunch supervision. Can happen before or after Phase 5.

Phase 7 — Substitution pool. Compute each teacher's remaining available slots.

🎨 UX — stepper: Structure → Curriculum & Enrollment → Teachers → Kitchen → Generate → Supervision → Substitution. Completion gates per step. Going back warns about invalidation.

5. Timetable Views¶

The generated timetable is a weekly grid — the same data projected through different lenses.

In homeroom-derived departments, the natural view is per homeroom:

              Mon          Tue          Wed          Thu          Fri
 Slot 1     English      Math         English      Science      Math
 Slot 2     Math         English      Science      English      Art
 Break      ──────       ──────       ──────       ──────       ──────
 Slot 3     Science      PE           Math         Math         English
 Lunch      ══════       ══════       ══════       ══════       ══════
 Slot 4     Art          Science      PE           History      Science
 Slot 5     History      History      Art          PE           History

Each cell is a discipline (teacher and room behind the scenes). Split slots show the parallel options.

Available views:

View	Shows	Default for
By homeroom	Homeroom's weekly schedule	Homeroom-derived
By grade/track	All lessons for a grade or track	Track-and-block
By teacher	Full week across all departments	All
By room	Room occupancy across the week	All
By student	Personal schedule (available after complete enrollment: track/option choices made and class list assignment done)	Track-and-block

The year schedule repeats the weekly grid from September to June, minus holidays and overrides.

6. Substitution Hours¶

After generation, the system computes each teacher's substitution availability:

Contractual maximum − (teaching hours + supervision hours) = substitution hours
Specific free slots where the teacher is available, not teaching, and not supervising

Example: Ms. Rossi has a 22-hour cap, 18 teaching hours, 2 supervision duties → 2 substitution hours, in her free slots.

Substitutions beyond the contractual maximum require explicit approval.

7. Cross-Department Dependencies¶

Departments are mostly self-contained but share:

Teachers — no double-booking; weekly cap shared across departments.
Rooms — shared and department-priority rooms cross boundaries.
Kitchen — lunch shifts are school-wide.
Calendar — holidays and events affect everyone.

8. Students and the Timetable¶

The solver works from estimated enrollment, not student lists. No students are needed to generate a timetable.

After generation, students are enrolled and assigned to homerooms, tracks, and option-block choices. The system validates room capacity and flags violations. The admin resolves mismatches by rebalancing students across parallel lessons or swapping rooms.

Year rollover provides most of the data: returning students are promoted (Grade 1 → Grade 2), departures are marked, new enrollments are added. The estimated enrollment for the next year is typically this year's actuals plus a margin for new students and attrition.

9. Open Questions¶

Resolved¶

Week A / Week B rotations: Not used. Weekly schedules repeat.
Co-teaching: Multiple teachers on the same discipline × grade/track.
Split classes: Option blocks (parallel disciplines in the same slot).
Teacher assignments: Partial — admin locks preferences, solver optimizes the rest. Post-generation manual swaps always possible.
Travel time between rooms: Not a concern.
Homeroom teacher scheduling: First-slot hard constraint when scheduling-active.
Mid-year changes: Targeted fixes preferred. Full regeneration as last resort.
Supervision: Counts toward teaching load. Configurable supervisor count per slot.
Consecutive teaching: 4-slot max without a break.
Non-teaching duties: Separate hours, don't subtract from teaching max.

Still Open¶

Discipline ordering preferences. Pedagogical rules about when subjects happen? ("Heavy" subjects in the morning?)
Student choices and year rollover. When students are promoted to a new grade, do their curriculum choices (track, option block selections) carry over or must they choose again? Does the new grade's curriculum require fresh choices?