As we move into the later period of August, the many adverts around for new uniforms and books tell us that schools are about to restart.
One of the new term activities that may not be quite so visible is the work that is being undertaken in every secondary school up and down the country to set the timetable. This is one of the more complex activities that has to be done in the school year, and recently caused an assistant headteacher to remark “Timetabling is an absolute nightmare. It is one of the most difficult jobs that is done during the summer holidays and it is almost impossible to get a good solution”
This activity could soon become easier after some work that has been undertaken by a team in Greece who have developed a Genetic Algorithm to solve the problem. This approach is outlined in their paper in the Journal of the Operational Research Society (JORS) and is titled “A genetic algorithm approach to school timetabling” (GN Beligiannis, C Moschopoulos and SD Likothanassis).
The timetabling problem is one member of classic scheduling problems. Although they seem simple they are actually very complex. The categorisation for algorithms is based on how long they take to solve given the size of the inputs, and this problem is categorised as “NP-Complete” – which takes the longest to solve.
In this case what we need to do is to create a weekly schedule for classes and teachers so that each class has a teacher for each available period. There are a set of hard constraints that also apply, for example each teacher can only be teaching one class at a time. There may also be soft constraints, for example pupils should not have all of their PE lessons on the same day.
There are a number of potential outcomes for such an algorithm.
It is possible that there is no exact solution to the problem – i.e. no conjunction of staff and pupils that meets all of the criteria. In this case we need to understand which of the constraints is causing the problem, and then we can decide how we can change it. For example it may be that there is not enough teaching capacity to teach PE. In this case we could consider reducing the requirement for PE on pupils, or increasing the number of teachers and PE rooms.
It is also possible that there are many solutions, in which case we need to be searching for the best solution of those available. Criteria for good solutions could include a good spread of subjects for pupils throughout the week, or an even balance of teacher workload.
In their paper, the authors chose to use a Genetic Algorithm to solve this problem. Genetic Algorithms are a set of techniques that mimic the way that nature evolves to answer a problem over time. The idea is that just as nature creates an ideal solution, so does the Genetic Algorithm.
The way that the technique works is to create a coding structure for possible solutions. This coding structure can be loosely thought of as being similar to a string of DNA. Given this ‘DNA’ then a series of possible solutions can be created. Two of the best solutions are chosen (with a degree of randomness) and then ‘mated’ to produce a new solution.
This technique in itself is not quite enough as it can fall prey to a problem called local optima, in which the technique becomes fixated around a sub-optimal solution and cannot see the bigger picture. An example of a local optima is shown in this diagram: -
The way to solve this is to randomly ‘mutate’ the solution.
The combination of mating and mutations will eventually settle down to a good solution which should after a reasonable period of time be fairly optimal.
In this particular case, the team from the University of Ionnina in Greece applied this technique to a number of schools. For each of the schools that the approach was tried on, the algorithm produced a better solution in 30 minutes than the schools themselves were using. In addition to providing a fairly quick and cost effective solution, they managed to solve one of the biggest problems in Greek schools – arguments between teachers who feel that the timetable is not suitable for them!
If you want to see a full copy of the paper that is referred to in this Figure it out, you can find it in the Journal of the Operational Research Society (vol 60, number 1, January 2009) in the Capgemini Consulting Library…