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)

4 comments:

Sergey Zaikin said...

Good afternoon.

At work, I faced a similar task (it is necessary to integrate
the work schedule of employees in the application I am developing).

Up to this point, I have not had to deal with such problems (with
complex mathematical calculations) and I would like to understand,
at least in general terms, how this can be done.

If it does not bother you, could you please put the archive, links
to which you gave in this post, to some other resource?

For some reason, the AutomatedTimetable.zip archive does
not download from the box.net resource.

Ciprian said...

Hi Sergey. I think than now box.com requires the creation of a free account to allow downloads. I didn't do this when I originally used it to store the files. I can e-mail you the .zip file if this is more convenient.

Sergey Zaikin said...

Hi, Ciprian.

Thanks for the answer. As a result, I managed to download the
AutomatedTimetable.zip myself via the mobile site interface
box.net (here's the link:
m.box.com/shared_item/https%3A%2F%2Fwww.box.com%2Fs%2F1liryjdec7).

However, I couldn't make the app work - after launching
AutomatedTimetable.exe the message "Exception EOleSysError
in module AutomatedTimetable.exe at 00097E19. Class not registered.".

As far as I understand - something missing in the system on my side.

I will continue to search for options (how to implement the schedule
algorithm).

Thank you very much for your time.

Ciprian said...

Hi Sergey. I'm very sorry the app didn't work for you. I tested it up til Win 8.1 and it requires Java and a .pdf viewer (tested with Acrobat Reader) to be installed as well. Keep looking for university course timetabling software and your are bound to discover something newer and hopefully better :).