"""School timetabling with Heusor. Every lesson needs a timeslot and a room. A room, a teacher and a student group can each be in one place at a time; teachers prefer to stay in one room and to teach their lessons back to back; a group should not have the same subject twice in a row. Run it: python school_timetabling.py """ from __future__ import annotations import copy import random from dataclasses import dataclass from datetime import date, datetime, time, timedelta from typing import Annotated import heusor from heusor import ( ConstraintFactory, HardSoftScore, Joiners, PlanningPin, PlanningVariable, constraint_provider, planning_entity, planning_solution, problem_fact, ) # ─── The model ────────────────────────────────────────────────────────────── @problem_fact @dataclass class Timeslot: day_of_week: str start_time: time end_time: time @problem_fact @dataclass class Room: name: str @planning_entity @dataclass class Lesson: id: int subject: str teacher: str student_group: str timeslot: Annotated[Timeslot | None, PlanningVariable] = None room: Annotated[Room | None, PlanningVariable] = None pinned: Annotated[bool, PlanningPin] = False @planning_solution @dataclass class Timetable: timeslots: list[Timeslot] rooms: list[Room] lessons: list[Lesson] score: HardSoftScore | None = None # ─── The constraints ──────────────────────────────────────────────────────── ANY_DAY = date(2026, 1, 5) def within_30_minutes(first: Lesson, second: Lesson) -> bool: """The second lesson starts 0 to 30 minutes after the first ends.""" return ( timedelta(0) <= datetime.combine(ANY_DAY, second.timeslot.start_time) - datetime.combine(ANY_DAY, first.timeslot.end_time) <= timedelta(minutes=30) ) @constraint_provider def define_constraints(f: ConstraintFactory): return [ # Hard: a room, a teacher and a student group are in one place at a time. f.for_each_unique_pair( Lesson, Joiners.equal(lambda lesson: lesson.timeslot), Joiners.equal(lambda lesson: lesson.room), ) .penalize(HardSoftScore.ONE_HARD) .as_constraint("Room conflict"), f.for_each_unique_pair( Lesson, Joiners.equal(lambda lesson: lesson.timeslot), Joiners.equal(lambda lesson: lesson.teacher), ) .penalize(HardSoftScore.ONE_HARD) .as_constraint("Teacher conflict"), f.for_each_unique_pair( Lesson, Joiners.equal(lambda lesson: lesson.timeslot), Joiners.equal(lambda lesson: lesson.student_group), ) .penalize(HardSoftScore.ONE_HARD) .as_constraint("Student group conflict"), # Soft: a teacher prefers to stay in one room. f.for_each_unique_pair(Lesson, Joiners.equal(lambda lesson: lesson.teacher)) .filter(lambda first, second: first.room != second.room) .penalize(HardSoftScore.ONE_SOFT) .as_constraint("Teacher room stability"), # Soft: a teacher prefers lessons back to back. f.for_each(Lesson) .join( Lesson, Joiners.equal(lambda lesson: lesson.teacher), Joiners.equal(lambda lesson: lesson.timeslot.day_of_week), ) .filter(within_30_minutes) .reward(HardSoftScore.ONE_SOFT) .as_constraint("Teacher time efficiency"), # Soft: a group should not have the same subject twice in a row. f.for_each(Lesson) .join( Lesson, Joiners.equal(lambda lesson: lesson.subject), Joiners.equal(lambda lesson: lesson.student_group), Joiners.equal(lambda lesson: lesson.timeslot.day_of_week), ) .filter(within_30_minutes) .penalize(HardSoftScore.ONE_SOFT) .as_constraint("Student group subject variety"), ] # ─── The data ─────────────────────────────────────────────────────────────── DAYS = ["MONDAY", "TUESDAY", "WEDNESDAY", "THURSDAY", "FRIDAY"] # Seven one-hour periods with a lunch break between the fourth and the fifth. PERIOD_STARTS = [time(8, 30), time(9, 30), time(10, 30), time(11, 30), time(13, 30), time(14, 30), time(15, 30)] # Lessons per week of each subject, for every group: 30 in all. CURRICULUM = { "Math": 5, "English": 4, "Physics": 3, "Chemistry": 3, "Biology": 3, "History": 3, "Geography": 2, "Spanish": 2, "Art": 2, "PE": 2, "Music": 1, } # The most lessons a teacher gives in a week. MAX_TEACHER_LOAD = 25 def generate(groups: int = 10, rooms: int = 10, seed: int = 0) -> Timetable: """A school week: 5 days × 7 periods, ``rooms`` rooms, ``groups`` student groups with 30 lessons each. Each subject has as many teachers as its load needs; a teacher teaches one subject to several groups.""" rng = random.Random(seed) timeslots = [ Timeslot(day, start, (datetime.combine(ANY_DAY, start) + timedelta(hours=1)).time()) for day in DAYS for start in PERIOD_STARTS ] room_list = [Room(f"Room {chr(ord('A') + i)}") for i in range(rooms)] group_names = [f"{9 + i // 4}{'ABCD'[i % 4]}" for i in range(groups)] lessons: list[Lesson] = [] for subject, per_week in CURRICULUM.items(): groups_per_teacher = max(1, MAX_TEACHER_LOAD // per_week) shuffled = group_names[:] rng.shuffle(shuffled) for g, group in enumerate(shuffled): teacher = f"{subject} teacher {g // groups_per_teacher + 1}" for _ in range(per_week): lessons.append(Lesson(len(lessons), subject, teacher, group)) return Timetable(timeslots, room_list, lessons) # ─── Solving and explaining ───────────────────────────────────────────────── def solve(timetable: Timetable, time_limit: float | None = 30, step_limit: int | None = None, seed: int = 0) -> Timetable: return heusor.solve(timetable, define_constraints, time_limit=time_limit, step_limit=step_limit, seed=seed) def explain(timetable: Timetable) -> None: explanation = heusor.score(timetable, define_constraints) print(f"Score: {explanation.score}") for name, score in explanation.constraints.items(): print(f" {name:32} {score}") # Which lessons cost the most: each lesson's share of every match it is in. blame = {lesson.id: explanation.blame(lesson) for lesson in timetable.lessons} for lesson in sorted(timetable.lessons, key=lambda l: (blame[l.id].hard, blame[l.id].soft))[:3]: print(f" {lesson.subject} for {lesson.student_group} ({lesson.teacher}): {blame[lesson.id]}") def print_group(timetable: Timetable, group: str) -> None: print(f"\nTimetable of group {group}") rows = {(l.timeslot.day_of_week, l.timeslot.start_time): l for l in timetable.lessons if l.student_group == group} for start in PERIOD_STARTS: cells = [rows.get((day, start)) for day in DAYS] print(f" {start:%H:%M} " + " ".join(f"{(c.subject if c else '-'):10}" for c in cells)) # ─── A room closes for maintenance ────────────────────────────────────────── def close_room( solved: Timetable, room_name: str, time_limit: float | None = 10, step_limit: int | None = None, seed: int = 0 ) -> Timetable: """Take a room out of use. Every lesson in another room is pinned where it is; the lessons that were in the closed room are placed again, so the rest of the school's week does not change.""" plan = copy.deepcopy(solved) closed = [r for r in plan.rooms if r.name == room_name] plan.rooms = [r for r in plan.rooms if r not in closed] for lesson in plan.lessons: if lesson.room in closed: lesson.timeslot, lesson.room, lesson.pinned = None, None, False else: lesson.pinned = True # A well-solved week has few free (timeslot, room) cells, and a displaced # lesson fits only where its teacher and group are free too. Moving one # variable at a time cannot get there without a clash on the way, so add # a move that puts a lesson into a free cell — timeslot (variable 0) and # room (variable 1) — in one step. config = heusor.config_for(plan, define_constraints, time_limit=time_limit, step_limit=step_limit, seed=seed) config["phases"][0]["selector"]["children"].append( {"kind": "JointChangeToFree", "ordinals": [0, 1], "order": "Random"} ) return heusor.solve(plan, define_constraints, config=config) if __name__ == "__main__": timetable = solve(generate()) explain(timetable) print_group(timetable, "9A") repaired = close_room(timetable, "Room A") print("\nAfter Room A closes:") explain(repaired)