Scientific researches of the timetabling problem
A historical note
The timetabling generates globally a huge cost of work of the timetable managers. That is why many researchers are interested in timetable optimization. They develop universal methods that allow more efficient timetabling and a multiple timetable updating.
In the year 1967 a one of the first examination planning systems based on sequence method had been created at the Nottingham University. Next the Nottingham University became the timetabling research center and there was created a research group leaded by prof. E.K. Burke.
In the next years many publications about timetabling solutions (such as simulated heating, genetic algorithms) had been created. In the nineties the new methods for timetabling solutions had been applied. These methods are called the Constraint Programming.
Many reports on timetabling (especially artificial intelligence and operation researches) had been lectured at different conferences. That is why Professor Burke decided to organize the first PATAT conference (Practice and Theory of Automated Timetabling). The conference has had four editions. The last one in 2002 gathered over hundred scientists. The best articles are published by the important Springer publishing house.
The above referred facts show that the timetabling is not an easy problem that can be solved by a one secretary. It is often a complicated combination problem that is solved by a few research centers and many scientists groups.
In the 70s in Poland, at the Silesian University of Technology the rector professor Antoni Niederliński persuaded to treat the timetabling as a scientific problem. The advantage of this change was easiness of research workers engaging. They avoided the laborious office work as a fire; the scientific problem was more interesting. It is certain that the workers that solve a scientific problem do their job with pleasure and the dreams of a good lesson schedules can become true then. In the 70s the ODRA computers and an available COBOL compiler for programs encoded on perforated cards had been used for solving the timetabling problem. The main approach was to apply the methods connected with graph coloring. It appeared that the problem was too complicated to solve using available computers in the 70s.
Professor Niederliński believed still that the computer application would improve the timetabling and after 20 years he returned to this problem when the computer and programming languages development allowed dealing with such complicated problems. Professor Niederliński was interested then in Constraint Logic Programming that is a developed Logic Programming using Prolog language. The first Professor's students used then CHIP language (Constraint Handling in Prolog) as a tool for Constraint Logic Programming. The researches have begun to develop fast when Wojciech Legierski began to deal with the timetabling problem as a part of his doctor thesis. He has won four times the dean prize for the best student of Automatics and Robotics field of study.
The doctor thesis researches began in the year 2001 and were subsidized by Fundacja Nauki Polskiej (The polish science foundation). In the next year the research results were published at PATAT'02 conference and the article was treated as an important report and published by Springer publishing house. It is an important fact that a few research centers deal with timetabling problem in Poland but only the Silesian University of Technology has made such a success.
ATS4 solver module methods
The timetabling procedures use the Constraint Programming methods that are different from classical logic and Prolog language connected with classical logic. That is why the automat could take into account the weak constraints and it has also a special system for solution searching based on Local Search. The matter is that if the weak constraints (they should be but not have to be fulfilled) are taken into account there will appear the optimization problem. This problem can be solved by a local search that consists in finding the better results by the following small changes.
The automatic timetabling procedures applied currently in ATS4 project use also interesting research results of the skilled student from Warsaw University - Paweł Parys. It should be mentioned that after school-leaving examinations he won the first prize in the informatics competition and next he won the second prize in an international competition. He has won also the polish mathematics competition.
In this way the best polish scientists were involved in this project and that is why there is a chance that the difficult timetabling problem will be solved as efficient as it is possible.
ATS4 as a co-operation platform
The timetabling problem is very complicated and there are still many problems that require an accurate analysis and researches. That is why the automat procedure is separated from the whole system and its sources are available for non-commercial applications and other scientists who can use the research results. The data that are exchanged with ATS4 planner program are based on XML format that was taken from Tomas Muller. The base format was modified for taking into account a few additional constraints. The ATS4 system enables also the data collecting that are the description of real school problems. They are used for automatic procedures improvement.
Many problems connected with timetabling have not been solved yet. ATS4 scientists deal still with these following problems:
We offer co-operation in the above mentioned fields as part of ATS4 project.