A gentle introduction.

Timetables, although they seem straightforward can become extremely complex very quickly.

Scenario 1.

A simple example, 1 Teacher, the same subject with 2 Classes, you would need 2 periods.

As you can see, same teacher with 2 classes can have only 2 possible outcomes for when each class goes to their period.

If you had 3 classes, but with the same teacher, 3 periods are now required the calculation would be 3! or (3 2 1) = 6 different permutations,

Scenario 2.

Now if you have 2 Teachers for the same subject with 2 Classes, you simply need 1 period, but there are still 2 possible outcomes.

Making it more complicated.

Let us further complicate the matter and take scenario 1, same teacher, but each class now has 2 subjects. We would need 2 periods now for each class, a total of 4 periods, which can be arranged in multiple ways.

Taking the class as 1 or 2, and the subject as x or y, leaving the teacher A out so the table does not seem overly cluttered we get:

Prd \ Cmb123456789101112131415161718192021222324
11x1x1x1x1x1x1y1y1y1y1y1y2x2x2x2x2x2x2y2y2y2y2y2y
21y1y2x2x2y2y1x1x2y2y2x2x2y2y1x1x1y1y2x2x1y1y1x1x
32x2y1y2y1y2x2y2x1x2x1x2y1x1y2y1y2y1x1y1x2x1x2x1y
42y2x2y1y2x1y2x2y2x1x2y1x1y1x1y2y1x2y1x1y1x2x1y2x

We have 4!/(4-4)! = 24 permutations or possible ways to place them.

We have one problem though, while Teacher A, is teaching the one class, the other class is sitting idly by wasting their time.

Effectively we would then need another teacher B, which would bring us to scenario 2 with the assuming that both the teachers are able to teach both subjects, x and y, we would now only need 2 periods. While teacher A is teaching class 1, teacher b is able to teach class 2. Once again, who is going to teach which subject to which class, and in what order.

If we break out the possible patterns that the teacher, class and subject can be associated, we get.

NumberPattern
1A1x
2A1y
3A2x
4A2y
5B1x
6B1y
7B2x
8B2y

As each class needs 2 periods now only, but we have 2 classes, we are still looking at 4 periods that need to be filled.

Our calculation is now 8!/(8-4)! = 1680 different ways that this can be done.

However!!! We cannot use number 1 and 5 together, as this would cause a clash with both the subject and the class being taught simultaneously by the 2 different teachers A, and B.

So of these 1680 different ways, we have to ensure that these clashes do not occur thus our large choice of 1680 is reduced to only certain combinations that we can use:

Our calculation would become 8!/(4!*(8-4)! = 70.

So to create an effective timetable, we would have to ensure that be search only for one of the 70 possibilities, and ignore any of the other 1610 suggestions that we might get.

Something like this can be done via brute force on a computer because of its speed,it is easily able to do a menial task like this.

As so see, simply adding another subject, or teacher to the mix expands our search area quite dramatically.

We quickly realise our headache one we have to deal with 20+ teachers, 10+ classes, 15+ subjects of which, based on the teacher’s ability/qualifications, they would be able to teach a subset of these subjects, as well as the grade levels that they are able to teach.

Let us be even more of a doom-sayer, and include the possibility of some rooms that might need to be shared, some subjects can be taught simultaneously to different classes by different teachers, and the cherry on top, some of the classes are essentially broken down and reconstituted, based on their subject stream, for their periods, making the classes, the teachers, and possibly the rooms, all needed simultaneously for those periods.

Looking at this, these is essentially only a few solutions in a gazillions of possibilities. This is now literally the few needles in the proverbial haystack. As it is usually referred to as an NP-Complete problem. This implies that finding a solution may take time, but proving the solution is quick. A summary of these problem types:

The P standing for Polynomial Time, and the N standing for Non-deterministic.

But wait, there’s more…

There are some teachers that may not available at certain times or have a limited number of periods that they are able to teach within a cycle.

Possibly some subjects where it’s preferable not to teach them at certain times, e.g. Mathematics, first thing in the morning when the children are not fully alert, or Physical Education is preferred just before breaks or home time so that the student has time to shower etc. and does not encroach on the next period’s time.

Some grades, with less periods, or even their breaks at different times to other grades.

These can be broken down to hard constraints, or soft constraints, the need to have vs. the nice to have.

TimeDesign is aimed at assisting you with all of these requirements, and more.

To be continued…