Assignment Algorithms to improve Perfomance of Automated Timetabling

Update: Was reblogged at dzone.com

Last two days I’ve read the old Java code of a board game. Although the game still compiles and works (it even works on a Zaurus device) the code itself is horrible: no unit tests, thread issues, a lot of static usages and mixed responsibilities. But then I ‘rediscovered’ my old TimeFinder project, which is a lot better – at least it has several unit tests! Then I saw that I even wanted to publish a paper regarding a nice finding I made 3 years ago. But I never published it as the results were too disappointing to me at that time.

Nevertheless I think the idea is still worth to be spread around (you are free to avoid usage ;)). BTW: now you know why my blog starts with “Find Time …” and why my twitter nick name is called timetabling – its all about history.

My Draft of a paper

So here is my “paper” ‘Optimizing Educational Schedules Using Hungarian Algorithm and Iterated Local Search‘ with the following main result:

The algorithm is bad when it comes to softconstraint optimizations (it wasn’t designed for this though) but it really shines to reduce hard constraints of timetabling problems. E.g. it was an order of magnitude faster than the 5th place (Mueller with UniTime) of the International Timetabling Competition 2007. Of course, I didn’t compare the latest version of UniTtime with TimeFinder yet.

Let me know what you think!

Now I would like to talk a bit about how one could in general use assigment algorithms in timetabling.

Using Assignment Algorithms in Timetabling

In this paper a technic is shown how assignment algorithms could be applied in timetabling. Only a few papers are known to us which uses assignment algorithms based on graph theory [Kin05, Bah04, MD77, TM02].
An assignment algorithm can be used as a subprocedure of a heuristic as it is done in the open source timetabling application called TimeFinder [Kar08]. TimeFinder uses an Hungarian algorithm only to assign a location to an event, where the solution itself is improved with a heuristic based on iterated local search [SLM03], we called this heuristic NoCollisionPrinciple.
Another possibility is to use an assignment algorithms as the ’backbone’ of a heuristic as it is done in [Bah04], where the Hungarian Algorithm is modified to act as a timetabling optimization algorithm.A third approach is to use an assignment algorithm as a pre-solver of another algorithm. This is planed for the TimeFinder project: before using the constraint based algorithm of UniTime an assignment algorithm will be used to give a good and fast starting point where all hard constraints are valid.

In all cases the good performance and optimal results of a mathmatically founded technic are the reason they are choosen and promise a good performing algorithm.

The heuristic tries to add and remove events to specific timeslots very often. So, the check if there is a room available for event E1 in a timeslot has to be very fast. But if there are already a lot of rooms and events in this timeslot it is difficult to test with a simple method if a valid room for E1 exists. Here the assignment algorithms came to my rescue. Other algorithms like the auction algorithm could solve the assignment problem, too, but are not discussed here.

An example for one cost matrix, where we want to calculate the minimal weighted matching (“best assignment”) later, could be the following:

Rooms \ Events | E1    E2
------------------------
R1             | 12    10
R2             | 16    3

The entries of the matrix are the difference of the seats to the visitors. E.g. (E2,R2)=3 means there will be 3 free seats which is better than (E2,R1)=10 free seats.

To optimize room-to-event-assignments it is necessary that the assigned room has nearly the same or slightly more seats as event E1 has visitors. The difference shouldn’t be too large, so that no seats will be ‘wasted’ (and an event with more visitors could be assigned later)

Of course, it could be that an entry is not valid (e.g. too many visitors) then the value in the matrix is +infinity.

The best solution (minimal sum) here would be E1,R1 and E2, R2 with a total sum of 15.

Some informations about the words in graph theory: this cost matrix is equivalent to a weighted, undirected, bi-partitioned, complete graph G. Weighted means with numbers instead of booleans; undirected means the same value for (Ex,Ry) and (Ry,Ex); bi-partitioned means the graph can be divided in two sets A and B where “A and B = empty” and “A or B = G”; complete means the cost matrix has the same number of rows and columns, you can always force this with +infinity values.

Assignment Algorithms

The easiest way to solve an assignment problem correctly is a brute force algorithm, which is very slow for big n: O(n!).
(Okay, it is even slow for small n=10: 10!=3628800)
Where n is in my case the number of rooms available in one timeslot. But this algorithm is always correct, because it tries all combinations of assignments and picks the the one with the minimal total sum. I used this algorithm to check the correctness of other assignment algorithms I implemented later.

Now it is great to know that there is another very fast and correct algorithm which is called Kuhn-Munkres [1] or Hungarian algorithm. The running time is O(n³) (10³=1000) and the ideas used in this algorithm are based on graph theory. Another optimization which one could use only in special cases is the incremental assignment algorithm with O(n²) (E.g. for “add one assignment” or “remove one assignment”)

And there are even faster algorithms such as the algorithm from Edmons and Carp [2]. For bi-partite graphs it runs in O(m n log n).

An interesting approach are the approximation assignment algorithms which can be a lot faster: O(n²) with a small constant. But the resulting assignments are not the best in every case.
A well known and easy to implemented algorithm the path growing algorithm from Drake and Hougardy [3] which works as follows:

currentMatching = matching0 = empty
matching1 = empty
while edges are not empty
   choose a node x from all nodes which has at least one neighbor
   while x has a neighbor
       find the heaviest edge e={x,y} incident to x
       add it to the currentMatching
       if(currentMatching == matching1) currentMatching = matching0
       else currentMatching = matching1
       remove x from the graph
       x:=y
   end
end

The good thing of this algorithm is that you can say sth. about the resulting assignment: the total sum is maximal twice times higher then the sum gained with an optimal algorithm. There are even better guarantees e.g. the one of Pettie and Sanders (~ maximal 3/2 times higher):

matching is empty
repeat k times
  choose a node x from all nodes at random
  matching := matching (+) aug(x)
end
return matching

Resources

You can grab the source of TimeFinder (Apache2 licensed) via svn:

svn checkout https://timefinder.svn.sourceforge.net/svnroot/timefinder/trunk timefinder

Then look in the package

timefinder-core/src/main/java/de/timefinder/core/algo/

To build it you have to use maven.

And finally here is the paper where the idea of a maximum network flow was already presented:
John van den Broek, Cor A. J. Hurkens, and Gerhard J. Woeginger. Timetabling problems at the TU Eindhoven. Electronic Notes in Discrete Mathematics, 25:27–28, 2006.

References

[1] Kuhn Munkres, “Algorithms for the Assignment and Transportation Problems”
[2] Edmonds and Karp, Theoretical improvements in algorithmic efficiency for network flow problems“.
[3] Drake and Hougardy, A Simple Approximation Algorithm for the Weighted Matching Problem, 2002
[4] Pettie and Sanders, A Simpler Linear Time 2/3 – epsilon Approximation for Maximum Weight Matching, Inf. Process. Lett. Vol 91, No. 6, 2004

TimeFinder-Planner a Primitive MigCalendar Alternative?

Yesterday I annouced a new version of TimeFinder. With that version a new and very simple component called TimeFinder Planner is included and can be easily integrated into an existing Swing or Spring RC project. It is already mavenized but I can deploy a full jar if necessary.

Of course it is not as feature reach as MigCalendar, but  you can use it as a read only calendar component in you own apps – it is Open Source (Apache License 2), small (<30KB) and has only relative few dependencies (~1MB). It supports ‘conflicting’ events, i.e. if events would be at the same time.

Look here for some screenshots in my TimeFinder application:

At the same time you can ‘zoom’ into one event simply via the “mouse over” action. And it should be able to handle any possibility of conflicts (overlapping events):

The performance should be also good even for a lot of events per week (independent from all events!). This cannot be seen in a screenshot but you can try TimeFinder and import the data of JavaOne 2009 via the ‘File’ menu item. Look here for the video explanation.

TimeFinder v4 Released – Automatic Educational Scheduling

Today the TimeFinder Team (its me ;-))
announces the availability of TimeFinder v4!

TimeFinder allows universities and schools to reduce and even avoid conflicts in the timetable! TimeFinder will improve the work of the human timetabler at the institute. A lot of work which would be done by hand to create the educational schedule could be done with TimeFinder.

TimeFinder is completely free and independent of the operating system (via Java 6). The power of TimeFinder is its algorithm. It eliminates the hard-conflicts of nearly all datasets of the International Timetabling Competition 08 in under 20 seconds on a normal laptop. And it can be applied on real data like the one from University of Bayreuth.

Pictures tells a lot more than 1000 words, so here is a video as introduction

and here are some screenshots:

The first screenshot is how editing of events works

  1. create a new event
  2. then set the name
  3. and specify the start and duration
  4. after this you can add some visitors under Event Table->Persons

edit-events

And here you see how TimeFinder optimized an instance of the International Timetabling Competition 08:

after-optimization

See some more screenshots and look again here for the video documentation.

Start TimeFinder right now via WebStart! Or download the jar which is faster!

New Features

The TimeFinder Team worked hard to add the following features in this version for you:

  1. Events with any duration are now possible – without performance losings! (before only duration=1 was possible)
  2. A more robust and lightweight Swing component the TimeFinderPlanner to display the schedule/timetable of all locations and persons was implemented and replaces the JavaFX component hassle. This component is small (<30KB) and but has some dependencies (1MB). It has the same purpose as MigCalendar, but is of course not as powerful as this.
  3. Import of text files (tab separated, comma separated data). XML was already supported in previous versions
  4. Auto-import for the last imported file
  5. Cloning entities is now possible
  6. Anonymize data, so that institutes could give away its data for performance-tests and other research projects.
  7. Import of the data for University of Bayreuth (Germany) and the possibility to optimize this data set with >1500 events; >100 locations; >600 resources (persons/course of studies) is now possible and shows how other institutes could use its existing data with TimeFinder.
  8. Removed a lot of deprecated classes and removed unused dependencies (now ~11MB)
  9. Now the English TimeFinder is fully translated into German too. Translation is now simplified with a small tool.
  10. A new maven module called algo was created (~3MB), to reduce coupling of the algorithm to the GUI. Now it is theoretically possible to deploy the algorithm without the spring dependency e.g. to an optimization server.

Support

No software is complete or bug-free, and so is TimeFinder which is beta software at the moment. You are free to support TimeFinder with your constructive critique, blog posts or even money if you like to make it better. Feel free to contact me or raise an issue if you find a bug.

Check the documentation or watch an introductive video to get an overview. Keep in mind that updating documentation is still work in progress.

You can win

If you know some Java and like coding GUIs, databases or algorithms you can contact me and win experiences via joining the project!

Especially the calendar component TimeFinderPlanner could be alluring for people with Java2d experiences or interests in this area.

Thanks!

This application wouldn’t be the same without the following nice open source projects:

… and last but not least thanks to NetBeans – the only IDE you need
and Yourkit profiler, which offers open source projects a free license!

TimeFinder – Powerful Optimization Algorithm, RIA and more

TimeFinder is an Open Source Timetable Optimizer for universities and schools, which uses the Spring Rich Client project to create an easy to use application with a nice user interface, a database and … more bla bla …

ok, it is a bit dingy headline and a more dingy introduction, but I would like to invite you to test the latest development version v4 of TimeFinder now! And without such a headline you woudn’t have read this. And I feel that I would like to release TimeFinder in the next weeks, so I need some beta testers. Go here to see some screenshots.

Get the dev version of TimeFinder here, double click the jar (optionally read the documentation for v1) and tell me:

  1. If you understand the purpose of TimeFinder from the website
  2. If you understand the user interface and how you can insert data
  3. If you find a bug
  4. If you need other features

Any feedback is welcome! Please contact me at peathal AT yahoo |dot| de, post an email to the mailing list or simply leave a comment here.