Multiple Criteria Optimization

Optimisation of Timetabling Problems

Timetabling Problems

Time tables have to be generated in quite different areas, e.g. human ressources, school time tabling etc. Because scheduling is a time consuming task, especially if the context is complex, most time tables are generated by computer programs. We have developed a sophisticated software which enables us to generate optimised time tables using different optimisation algorithms in recent years.The current software is a complete new implementation as the former version of the software showed some design flaws which persuaded us to re-design the architecture.

Erlangen Advanced Time Tabling Software EATTS is the innovative development and production environment to generate optimized time tables.

Resources
Time tabling problems are quite common and come in different versions, among them rosters, schedules and school time tables. They have in common that given resources have to be used as efficient as possible and that this requires planning with respect to the given constraints to obtain a decent plan. When looking at a school time table the events are lessons, to which the resources like teachers, classes ans rooms have to be assigned. All resources are typed. Each type has as many attributes created by the user as required.
Planning a time table usually begins with compiling the resources, either by reading in a file or typing in them manually. The screen shot shows the input dialogue to enter the attribute values for a class. All resources of the type "Class" have to be assigned values for the user defined attributes "name", "size", "grade" and "room".

Results
Time tables are the output of the planning algorithms and can be stored in different file formats and views. The screen shot shows the view of a student, e.g. he sees his personal time table consisting of the lessons he has to attend to. Other views can be created instantly, for a teacher, a headmaster or a caretaker. All users access the EATTS through a browser providing an interface according to the privileges of the user.
A common view indicates which constraints are currently not satisfied naming the events and resources. Based on this information the administrator can decide if he would like to edit the resources, events or constraints or use a different algorithm. The screen shot show time slot clashes and therefore the algorithm should be given more time to find a solution a another algorithm should be given a shot.

Constraints
The specification of constraints is usually more complex than describing resources or events.
On one hand a precise specification is required and one the other hand the current setting should be presented clearly to find gaps and/or inconsistencies, which can't be avoided automatically.
Constraints come in different flavours, therefore a flexible way to specify them is necessary. EATTAS allows to refer to resources, their classes and all attributes. Depending on the type of the attributes, among them are integer, double and string, arithmetic and logical operators can be used to specify the constraint. In addition the parameters of the cost function are set, to compute the correct penalty point if the constraint is violated.
A unique property of EATTS is the option to specify a constraint not only as "has to be fulfilled (hard)" or "should be fulfilled (soft)" but also as "can be violated in exceptional case (soft hard)". This allows to violate constraints when it is acceptable, e.g. a room isn't available due to a broken water pipe, a teacher isn't available due to a traffic jam. In these cases a time table should be created which is similar to the one currently in effect but violates some constraints to minimize changes.

Running Experiments
The algorithms can be executed on a dedicated server or can be distributed over a TCP/IP network on additional computers. The screen shot shows the dialogue where the user can select the experiments and start their execution. The browser contacts the server regularly and updates the status information, including the costs of the best plan found so far and an estimated remaining computation time. At the end of the computation results are stored and the data required for the views are generated. Now the user decided whether the results are satisfactory or additional computations are required.

Results
Time tables are the result of the application of algorithms to the specifies resources, events and constraints. Time tables can be stored and displayed in various formats, enabling the display of different views of the time table.
Users typically access the EATTS via a browser and views are created depending on the users privileges.

Summary
The software is implemented in Java and available for numerous platforms, among them Windows and Linux operating systems.
To run EATTS the following free-ware software products are required:


In 2008 the structure of the algorithms was optimized to enhance their parallel computation. We will look into the use of multi core processor in the near future.
As attempts to install the software by users have shown that this might be too complex a downsized version which does not need a database but uses XML documents to store and exchange data was implemented. In addition a server was set up running on a computer at the University of Erlangen allowing the users to run their experiments on this mashine.
The user interface was reimplemented and is now a web based application.
At CeBIT 2009 the new version of the software has been presented. And it was named EATTS Erlangen Advanced Time tabling System.

In 2010 the EATTS interfaces was improved and the broadband of potential applications was increased. Currently the following tasks are scheduled using EATTS: