Posts tagged automatic timetable generator
For the last 4 years our unique automatic school timetable generator has been the only one in the market that works in your browser of choice on both Mac OS and Windows, and all that without sacrificing its performance. Isn’t that great? We’ve had great feedback from you, but we didn’t stop there, because there is always room for improvement. We have done a lot of research in the field of automatic timetabling algorithms in order to further improve our generator’s performances. Today, we are very pleased to announce the results of this multi-year work:
Generating complex timetables 5-10 times faster
Automatic timetable generator has been rewritten from scratch to serve you better. The main focus was resolving requirements of complex timetables faster. For instance, if you used to wait a couple of minutes for automatic timetable generation to finish, you will be pleasantly surprised to see that now the timetable will be generated in the matter of seconds and you will get the job done with a single click of . Give it a try and let us know how it works for you.
However, if there is no improvement for a couple of minutes, you should stop the generator and check if your data is properly entered or try to remove some constraints and then try again. The owl will hoot helpful advice along the way.
Also, while improving, automatic timetable generator will try to move only a limited number of cards. In some cases, you can spot the “problematic card(s)”, manually move them to another position, fix them using and then click once again.
New generator => new features
The new generator is much more flexible than the old one. It allows us to easily introduce new features such as multiple rooms and lessons without teachers or classes, and this is only the beginning. You can expect much more in the future.
New automatic timetable generator in action
Single play icon which improves timetable
In the old version, whenever was clicked, the timetable was generated from the beginning (all cards were first removed), while when was clicked, the current timetable state and its imperfections were improved. We have decided to remove and use instead.
If for some reason you still want to generate a timetable from the beginning click with Shift key pressed or just click to remove parts of the timetable you are not satisfied with.
What happened with the old generator?
It’s still there just in case. If you need it let us know, and we will enable it for you. Bare in mind that the old generator can’t be used for the new features, such as multiple rooms and lessons without a teacher or class.
In the new Prime Timetable 6.0 it is possible to enter lessons without teacher and/or class. For instance, now you can add “Teachers’ meeting” as a lesson without specifying the class, or you can add “Break” for a specific class without setting the teacher.
Lesson without specified teacher or class
A lesson without a teacher will not be visible in the master teacher view, whereas a lesson without a class will not be visible in the class view. If there is a card which should display the class and there is no specified class, that card will have no text and will be in gray.
The only requirement for adding a lesson is to set its subject (activity). Teacher(s), class(es) and room(s) are optional.
In the previous version when a lesson is created without specifying the teacher or class, the application added what we called “fake” teacher or “fake” class. Since this was confusing it is now completely removed and automatic timetable generator has been updated to “understand” these types of lessons.
One of the main purposes of school scheduling/timetabling software is to help schools with automatic timetable generation and validation. In order to use automatic generator and validator you should follow the basic timetabling rule which says:
One school resource during one school period can be scheduled in only one lesson. Otherwise, there is a conflict.
In the Prime Timetable, the conflicted cards are rotated so you can easily spot and fix them. There are two common approaches to fixing conflicts:
- Add more than one teacher or class/group in the lesson or remove redundant lessons/cards.
- Just ignore conflicted cards.
Add more than one teacher or class/group
If there is more than one teacher or more than one class/group attending a lesson, you should not create more than one lesson for it. The example is in the screenshot below. Teachers John and Jim are giving lectures for two classes/grades 7A and 7B at the same time.
When adding a new lesson (Manage > Lessons > Add) just add another teacher or class/group to it. Thus, you’ve created only 1 lesson/card and therefore there are no conflicts/rotation and automatic timetable generation and validation will work as expected.
If for some reason you want to keep the position of conflicted cards and still take advantage of automatic timetable generation and validation, you might want to ignore them.
In this screenshot there are lots of classes/grades using the Fellowship Hall/Gym at the same time, which creates many conflicts in the room view. Nevertheless, you can create only one lesson and include all those classes or just ignore the Gym.
In order to ignore cards, do the following:
- Set “-” (without quotes) as a short name for any school resource which is part of the lesson/card you want to ignore. For instance, you can set short name to “-” for subject Lunch or for Gym room.
- Check Help > Options > Exclude fake lessons while generating timetable.
- Click Ok.
And that’s all you need to do. Automatic timetable generator will just ignore those cards and treat them as if they are not part of the timetable.
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 (PATAT) 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…