November 17, 2008

Project: AutomatedTimetable

This project is the result of a university team-assignment me and my colleagues signed up for in the spring of 2008. The goal was to build an automated timetabling solution that would aid in the generation of our department's timetable.
.
The application had to implement the following features:
- it should allow the user to specify the general planning context (the number of professors, the student groups, the number of lectures, the type of a given lecture, available classrooms, etc.);
- it should enable the user to specify a certain constraints (some lectures are to be held in a particular classroom, some professors are available only in some time periods, etc.);
- it should automatically generate in a reasonable amount of time "the best" timetable in accordance to the given planning context and the constraints that must be enforced (given that a solution to the planning problem exists);
- it must export timetables for each student group, professor and classroom in both a .pdf and .xml format;
As the problem at hand was fairly complex, the workload for this project was clearly divided between the 4 team members:
- Andrei Niciu was in charge of developing the main Delphi application which, besides integrating all other parts of the project, offers custom made, smart and extremly user friendly tools for manipulating planning contexts and related constraints;
- Alexandra Kulcsar developed the Java export module that generates the beautifully looking .pdf files that represent the solution of the given timetabling problem;
- Mihaela Radescu worked on the comunication protocol between the different modules of the application, providing valuable means of data conversion and storage.
- I worked on finding adapting and implementing the automated timetabling algorithm employed in the project. This type of scheduling problem has been proved to be NP-complete so the search for a good heuristic or metaheuristic was on.

This scheduling algorithm is derived from the one proposed by M. Chiarandini, M Birattari, K. Socha and O. Rossi-Doria in their 2006 article in the Springer Journal of Scheduling. It is based on construction heuristics and metaheuristics (local search, tabu search, simulated annealing). The proposed algorithm also tries to divide the general timetabling problem into two smaller ones that are resolved sequentially:
1. an existential problem (try to find a scheduling configuration that doesn't break any hard constraints);
2. an optimization problem (take a solution to the existential problem and improve it so that it breaks the fewest number of soft constraints);

After finishing my work on the AutomatedTimetable application, I've continued experimenting with various scheduling methods and my Bachelor's Thesis presents my version of a lightweight scheduling algorithm inspired by the works of M. Chiarandini & Co. I've also rewritten the original Delphi Component used by the AutomatedTimetable such as to employ the new algorithm and thus benefit from its improvements (new structure for the soft constraint optimizer, multithreading and thread trimming stages).

You can download a fully working version of the AutomatedTimetable application by clicking here or from the Downloads box (AutomatedTimetable.zip). Unfortunately, for now, the application does not have any help files. If you have any questions regarding how to use it, please don't hesitate to ask. Here are some screenshots:
 


Application platform: Win32 + Java (JRE)

No comments: