Automatic timetable generation - solving the unsolvable?
If you've searched the web for 'school scheduling/timetabling software', 'automatic timetable generator', 'school timetable generation', etc. you probably noticed that there are none of the 'big names', such as Apple, Microsoft, Google, etc. in the search results. Furthermore, school scheduling software cannot be found as part of any larger software package for schools. Neither does it exist in various schedulers, calendars, spreadsheets, etc. Why?
Automatic timetable generation is complicated!
It is complicated to make a machine allocate lessons that certain lecturers are to teach to certain groups of students in certain rooms and certain periods of time... and that all works out well in the end. It is that complicated that, generally, there is no solution. It is that complicated that only enthusiasts working in the field of artificial intelligence have been trying to find a solution to this problem.
PATAT conference to the rescue?
In 1995, the 1st International Conference for the Practice and Theory of Automated Timetabling was held in Napier University, Edinburgh, UK. It was the founding conference with a new one being held every third year and later every other year. So far there has been eight conferences and the ninth one will be held at Son, Norway, from 28th to 31st August, 2012. In order to better understand the complexity of the problem of 'computer-aided timetable generation', you may take a look at the official website of the ninth conference at www.patat2012.com. However, not even a series of conferences presenting the highest academic names from all over the world was enough to cope with such a difficult problem.
International Timetabling Competition
In order to intensify research in this field an 'International Timetabling Competition' was organized in 2002 and held in 2003. The competition was sponsored by PATAT who offered prizes for the winners. From that year on, the competition is traditionally organized every four years. Currently, ITC2011 is being held, and since it is open for all, anyone can submit their work. In the meantime, the prizes have become even more appealing ;).
Euclid's Fifth Postulate of Discrete Mathematics
Even though thousands of different experts have been dealing with the problem of automatic timetabling generation for 17 years, the problem remains unsolved. The only mathematically proven thing is the proof that the problem is unsolvable! Over the past couple of decades, the writer of this blog post has witnessed numerous unsuccessful attempts of creating an exact algorithm for school timetable generation. There are also anecdotes in which a programming teachers would give their ambitious students this problem as homework offering the highest grade as a prize until the end of their schooling. On various forums people desperately search for 'logical model for timetable generation', 'Help! I have to write a timetabling program for tomorrow'... This much resembles an unsuccessful 2000-year-old attempt to prove the parallel postulate using Euclid's first four postulates which was 'proven' by proving it can't be proven.
The question is why organize all the conferences and competitions if the problem is unsolvable? What are we at Prime Timetable actually doing? Are we trying to solve the unsolvable? Have we succeeded? More about that and the parallels with 'parallel postulate' in the future posts...