How an automatic timetable generator actually works

4 min read

Press "generate", wait a minute, and a complete timetable appears. It can feel like magic, but what goes on inside an automatic timetable generator is a well-understood piece of computer science. Knowing roughly how it works helps you give it better inputs and make sense of what comes out.

The timetable as a set of decisions

A generator starts by turning the timetable into a list of decisions. For every lesson that needs to happen, it has to choose:

  • When: which day and period it starts
  • Who: which qualified teacher takes it
  • Where: which room it goes in

Each of those choices has a set of possible values. A Year 10 chemistry lesson might start in any of 25 periods, be taught by any of four chemistry teachers and go in either of two labs. That's 200 possibilities for one lesson. A secondary school has hundreds of lessons, so the number of possible timetables is far larger than anything you could check one by one.

Rules cut the possibilities down

The generator doesn't try every combination. It uses the rules to rule options out before it ever tries them, a process called constraint propagation.

A small example shows how. Suppose Ms Patel teaches Year 9 maths, and Year 9 maths has to happen on Monday period 1 because the whole year group is set together. Then:

  1. Ms Patel can't teach anything else on Monday period 1, so that period disappears from every other lesson she could take.
  2. Year 9 students can't be anywhere else on Monday period 1, so it disappears from every other Year 9 lesson too.
  3. If Ms Patel only works Monday to Wednesday, her remaining lessons now have fewer slots left, which may force one of them into a particular period, which removes more options elsewhere.

One decision ripples through the whole problem. Good solvers do this reasoning thousands of times a second, and it's why they can handle problems that look hopelessly large.

Search fills in the rest

Propagation alone rarely finishes the job. At some point the generator has to make a choice: put this lesson here and see what follows. If the choice leads to a dead end, where some lesson has no valid slot left, it backs up and tries something else.

Modern solvers are clever about the order they make choices in. They tend to start with the most constrained lessons, the ones with the fewest options left, for the same reason an experienced timetabler places whole-year setting before anything else: leave the hardest pieces until last and they won't fit.

Scoring the timetables that work

Most timetabling problems have many valid answers. Once the generator has found one, it keeps looking for better ones, scored against your goals:

  • How many free periods are stranded in the middle of students' days
  • How spread out or bunched each teacher's day is
  • How many students are at lunch at the same time

Each time it finds a valid timetable with a better score, it keeps it. This is why most generators let you set a time limit: more time means more of the search space explored, and usually a better result, with diminishing returns.

Why results can differ between runs

Change one input, or even give the solver a few more seconds, and you may get a noticeably different timetable with a similar score. That's normal. There are usually many timetables that are about equally good, and the solver finds one of them. If you need a lesson to stay put, make that an explicit rule rather than relying on it landing in the same place twice.

What this means for you

A few practical lessons follow from how generators work:

  • Clean data matters more than clever settings. A teacher missing from a subject, or a room with the wrong capacity, changes what's possible.
  • Hard rules should be genuinely hard. Every unnecessary hard rule removes options and slows the search, and can make the problem impossible. See hard and soft constraints.
  • "No solution" is an answer. If the generator can't find a valid timetable, it's telling you something about your staff, rooms or rules. We cover what to do in why is my timetable impossible?

How Timez does it

Timez uses a constraint solver of the kind described here. It treats every hard rule as exact, searches for the timetable that best meets your goals, and stops at the time limit you set, from 10 seconds to 5 minutes. You can watch its progress as it runs. If no valid timetable exists, it says so.

For why a chatbot can't do the same job, see can ChatGPT make a school timetable?

More from the blog