Forget all that geeky maths – I’ve been timetabling for the last 20 years and don’t need some maths formula to tell me it’s difficult!

In the previous articles I’ve in essence said that the biggest challenge in timetabling software is generating acceptable solutions in a sensible timeframe.

Let’s go back to a simple example:

School operates a 5-day timetable and has 6 period in a day.

Let’s really simplify things – class 7A go round school together and never mix with any other students and let’s pretend their curriculum is:

Question – How many ways (combinations) can you place those lessons into the periods (forget about one per day rules etc)

Answer – Factorial 30 (30!)

Scheduling that should be a relatively straight forward task for us as a human and a quick task for the computer. Although there might be a vast array of solutions, how many are acceptable solutions? Let’s take one solution below; wouldn’t have thought this was an acceptable solution!

Now let’s consider class 7B, they also have 30 periods, so the 7A and 7B curriculum is:

Question – If you schedule 7A and 7B how many solutions/combinations are there?

Answer – (30!)^2 i.e Factorial 30 squared

Extension question – Let’s say Year 7, 8 and 9 are all 2 fe entry

Answer – (30!)^6   ~= 3 x 10^194

But out of this number how many form a good timetable?  The true number will be less (reasons below) but even though it will be less it’s still a huge number!  As mentioned previously I’m no Mathematician, so thanks to Keith Johnson for checking/correcting my work.

Conclusion

Wow, I never realised there were so many combinations to be had! On one hand this is true but in our simple curriculum, there is no blocking, and no teachers were considered, lesson spread, doubles and singles etc weren’t considered either. So, the million-dollar question is how many of those combinations are valid? I don’t know is the answer. Then even out of all the valid combinations the computer can’t go through them all in any sensible timeframe!

For the mathematicians out there – Timetabling is ‘NP Complete’, as so far, no polynomial algorithm is known for solving the problem.

So, can a computer create a timetable? Yes, it can, but as the software is dependent on its algorithms and not being able to look at every combination, given your timetable constraints finding an acceptable solution in any sensible time might not be possible.

Then what happens when the parameters are changed? For example, the curriculum allocation is changed, staffing is changed, or a part-time constraint is changed. One simple answer is you might need to start again or as a minimum review whether your current solution is an acceptable one given the new parameters.

Every day I say I can’t do the job I do without the software solutions available to schools, but they still need me! As years go on and the algorithms get better/reduce time (and if anyone can say P=NP then my role will change). But until then in my opinion the human is still required as we have the working knowledge of what is an acceptable solution, not just whether something clashes or doesn’t!

With this said future articles are going to be:

1. What makes a good timetable?
2. Is scheduling without staff a good idea?
3. Are split groups a bad thing?
4. Changing school week
5. Part-time staff
6. Rules for scheduling
7. Degree of freedom
8. Order of scheduling (strategy)
9. Grade only teachers
10. Drawing a curriculum diagram
11. Option structures – heterogeneous, homogeneous blocks and course structure
12. How many option groups should I have?
13. Calculating curriculum demand
14. Teacher teams
15. Compatibility of time
16. Conflict matrix
17. Rooming fractions

All with the idea that you take ideas away that will help you formulate a timetabling strategy (what are your boulders, stones, and sand) that allows you success and you and your software work in partnership. Don’t just rely on the big ‘Schedule’ button!

Still to this day I remember running a scheduling course and the training data was designed so that it wouldn’t schedule. When this gentleman’s computer stopped scheduling his question was where is the bigger ‘Schedule’ button!  He was horrified that intervention or compromise was required!

Any questions please just ask or more information about the services we offer please click your software solution below.