School timetabling¶

Give every lesson of a school week 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.

python school_timetabling.py

The script generates a week, solves it for 30 seconds, explains the score, prints one group's timetable, then closes a room and repairs the week.

The model¶

A lesson is the planning entity: the solver chooses its timeslot and its room. pinned is used by the room-closure scenario below.

@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¶

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"),

The other five follow the same pattern; see school_timetabling.py. Heusor compiles each lambda and within_30_minutes once, before solving. Python does not run while the solver searches.

The constraint set is the one of the Timefold school-timetabling quickstart, constraint for constraint:

Constraint	Level	What one match is	Reference constraint
Room conflict	hard	two lessons in the same room at the same timeslot: −1	`roomConflict`
Teacher conflict	hard	two lessons of the same teacher at the same timeslot: −1	`teacherConflict`
Student group conflict	hard	two lessons of the same group at the same timeslot: −1	`studentGroupConflict`
Teacher room stability	soft	two lessons of the same teacher in different rooms: −1	`teacherRoomStability`
Teacher time efficiency	soft	a teacher's lesson that starts 0–30 minutes after another of theirs ends, on the same day: +1	`teacherTimeEfficiency`
Student group subject variety	soft	a group's lesson of a subject that starts 0–30 minutes after its previous lesson of that subject ends, on the same day: −1	`studentGroupSubjectVariety`

A lesson without a timeslot or a room is in no match.

The data¶

generate() makes a week of 5 days × 7 one-hour periods (35 timeslots), with lunch between the fourth and fifth period, and 10 rooms. Each of 10 student groups has 30 lessons a week across 11 subjects: 300 lessons. A teacher teaches one subject, to no more than 25 lessons a week; 17 teachers in all. The generator is this example's own.

The explanation¶

heusor.score returns each constraint's share of the score and, for each lesson, the cost of the matches it is in. From one run (30 s, release build, an Intel i7-1255U):

Score: HardSoftScore(hard=0, soft=-140)
  Room conflict                    HardSoftScore(hard=0, soft=0)
  Teacher conflict                 HardSoftScore(hard=0, soft=0)
  Student group conflict           HardSoftScore(hard=0, soft=0)
  Teacher room stability           HardSoftScore(hard=0, soft=-339)
  Teacher time efficiency          HardSoftScore(hard=0, soft=201)
  Student group subject variety    HardSoftScore(hard=0, soft=-2)
  Math for 11B (Math teacher 2): HardSoftScore(hard=0, soft=-22)
  English for 9B (English teacher 1): HardSoftScore(hard=0, soft=-22)
  Math for 9A (Math teacher 2): HardSoftScore(hard=0, soft=-21)

A lesson's figure counts every match it is in, and a pair's cost is charged to both of its lessons. So the per-lesson figures do not add up to the score.

A room closes¶

A room is out of use for the rest of the term. Re-solving the whole week would move lessons that teachers and students already know. Instead, every lesson outside that room is pinned (PlanningPin), so the solver keeps it exactly where it is, and only the closed room's lessons are placed again.

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)

After 30 s of solving, Room A holds 35 lessons, and the other nine rooms have 50 free cells between them. Few of those cells are at a time when the displaced lesson's teacher and group are both free, so the repair is a tight puzzle. With the default moves, which change one variable at a time, the search stops at one or two room clashes: hard −1 or −2 on 3 of 3 seeds, and the hard score does not change between 1 s and 60 s. With the free-cell move it is feasible on 3 of 3 seeds (10 s). In the run above:

After Room A closes:
Score: HardSoftScore(hard=0, soft=-330)
  Room conflict                    HardSoftScore(hard=0, soft=0)
  Teacher conflict                 HardSoftScore(hard=0, soft=0)
  Student group conflict           HardSoftScore(hard=0, soft=0)
  Teacher room stability           HardSoftScore(hard=0, soft=-525)
  Teacher time efficiency          HardSoftScore(hard=0, soft=198)
  Student group subject variety    HardSoftScore(hard=0, soft=-3)

The soft score falls from −140 to −330 because the 35 lessons go where there is space, not where their teachers usually are. That is the price of not moving anything else.

The default moves are not changed for every problem. Added to the full 30 s solve of this week, the free-cell move made the result worse on 3 of 3 seeds (soft −177 to −193, against −132 to −150).

How it is verified¶

test_school_timetabling_example.py holds the example to what this page says:

An independent scorer. A plain-Python scorer, written from the table above, shares no code with Heusor and does its own time arithmetic. For random weeks, for crowded weeks (all 300 lessons on one day), for weeks with a fifth of the variables unassigned, and for the solved week, Heusor's score, each constraint's share and each lesson's matches and cost are equal to it.
The data is the size stated under The data.
The room closure moves no pinned lesson, uses no closed room, leaves no lesson unplaced, and changes nothing in the week it was given. On a frozen packed week (packed_week.json, the 30 s result above) it ends feasible.
This page. Every python block here is a verbatim part of school_timetabling.py, and the table names exactly the constraints that the code defines, in their order.

Measured on one machine¶

Release build, Intel i7-1255U, seed 0. These are single runs, not benchmarks:

Solve time	Score
construction and one step	0hard/−598soft (0.37 s)
5 s	0hard/−387soft
30 s	0hard/−140soft