Principles of timetable optimisation

Fitness-based optimisation

Timetabling problem in a nutshell

Creating a timetable means fitting a number of lessons into a number of time slots (and rooms) while observing constraints, such as a teacher not being able to teach two lessons at the same time. Important constraints like this are usually considered hard, meaning they must be satisfied. Requests such as an afternoon off for a teacher might be considered soft constraints.

Skolaris handles both hard and soft constraints with ease.

Traditional Approach

Other timetabling software usually simulates the human approach to the problem, trying to fit lessons into time slots one by one as far as possible without breaking a hard constraint and going back a step or a few (or many) when stuck, with a few tweaks here and there.

This traditional approach is weak when soft constraints need to be considered because it is difficult to decide when to back-track based on just a soft constraint being broken. It also staggers when faced with heavily-constrained problems.

Another disadvantage lies in the verified fact that even if the first 95 percent of the timetable can be filled (very) quickly, the remaining lessons are exceedingly hard to schedule and the programs tend to leave this, most difficult, part up to the users.

The Skolaris way

Skolaris is inspired by prof. Andrea Schaerf 's paper on high-school timetabling techniques. It optimises timetables based on fitness, not caring about hardness or softness of the constraints along the way.

This allows it to explore the solution space globally and gradually make its way towards a good timetable.

Optimisation beyond feasibility

Other timetabling software usually stops if a feasible timetable is found. Skolaris, on the other hand, strives for the best possible fitness even after it has reached feasibility. So unless the fitness is 100 per cent it will continue trying to improve it.

However, the soft constraints usually contradict each other (a good example is all the teachers asking for a Friday afternoon off), so the perfect fitness is simply not achievable. Skolaris does allow you to get the best results with weighting system for requests so that when two or more contradict each other, the solution satisfying the more important one will have a higher fitness and thus will be considered better.

Staff needs are important...

The requirements on the timetable from the point of view of pupils or students in class groups stay more or less the same – no gaps, balanced distribution of hours during the week, few early and late sessions to name a few.

But staff needs are also important. The headmaster can only be available to teach at certain times, teachers may prefer a “dense" timetable with busy but short schedules when they're present at school, certain half-days off etc.

Skolaris provides constraints, weighted availability configuration and more to accommodate for these requirements.

...sometimes even more important

If a certain requirement (constraint) becomes more important than others, with Skolaris's penalty weighting system it's easy to quantify such need and let the system optimise the timetable with the emphasis in the right direction.

Which constraint is soft and which is hard is entirely up to the user, Skolaris is indifferent. Skolaris does what it's told to do and does it well.