Assignment Algorithms to improve Perfomance of Automated Timetabling

Update: Was reblogged at

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

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)
return matching


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

svn checkout timefinder

Then look in the package


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.


[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 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


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


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.


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.


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.

JavaOne Schedule is out – create your own with TimeFinder

Today I realized that the schedule for the JavaOne 2009 is out (4 days starting from June 2nd). So I grabbed the data from this table and created a new menu entry in my TimeFinder application to import all the talks and get a feeling of how the overall timetable would look. If you build the latest version from source you can create your own schedule for JavaOne – contact me if you need assistance.

Update: Start TimeFinder here. This an alpha version where the JavaOne Import is included.

Update: Click here for a flash video.

If I would be the host I would let the people pre-enrol them before the conference starts. So that the schedule could be optimized with TimeFinder. Then a lot more people could attend what they like.

I do not attend the conference (although I would like) but this could be my schedule (a lot of conflicts, uhm):


Another cool thing about TimeFinder is that you can see easily the timetable of a lot persons or rooms. E.g. in the JavaOne example you can see which other talks one speaker has – e.g. Sean Brydon from Sun Microsystems, Inc. has the following timetable:


Update: I really forgot to publish the javaOne ‘overview’ ;-):





TimeFinder Documentation 2009-v1


To run TimeFinder Java1.6 is necessary. If you not already have it then get it from here.

To download and install TimeFinder click on this link. The java web-start engine downloads now the necessary jar files (21MB). After this was successful (it should be ;-)) you have to confirm the execution.

Another option is to download the zip bundle from here. Then unzip the file and double click on the run.bat file if you are on Windows or click on the file if you are on linux or mac.

While starting TimeFinder the splash-screen should appear:


You have to accept the Apache License, Version 2.0


and click ‘Start TimeFinder’ which will show the main TimeFinder window (without any view).

Manual Timetabling

Person Table View

To see something useful go to the menu entry Window->Show Views->Person table and e.g. create a new person:


TimeFinder marks your input red if it failed to validate it. See the small red cross-icon on the bottom of the input field for the detailed reason.

How you can import a junk of data is described in the import sample data section.

Be sure that you defined at least one person now. So that we can assign persons to an event in one of the following chapters.

You can sort via clicking on one of the table headers or filter persons agains their names within the filter-textfield.

Event Table View

Here you can define events and its visitors. For example if you want that all persons of a class should attend Mathmatics then do the following:

  1. Create an event with the ‘new event’ button. Set the properties e.g. the name to ‘Mathmatics’:event-table-2009-v1
  2. You should have defined some persons one chapter before. Go to the persons-tab and you should see:event-table-persons-tab-2009-v1
    Add all necessary person (of the class) via the '>' button.
  3. You can add features if Mathmatics requires one room:event-table-features-tab-2009-v1
  4. Click Save. Then a new event should be listed in the table

Location Table View

Within the location table you can define your rooms or places with the specific capacity and features (e.g. only some rooms have a blackboard or a video installation).

Feature Table View

Here you can define features which are required from some events. And only some rooms offer them.

Import Sample Data

Download sample data from here. Unzip the file e.g. in your documents folder. Then click File->Import tim File from within timefinder. Now it will warn you that the settings will be changed. Click okay and select a .tim file from that zip archive.

Now the progressbar at the bottom right side indicates the status of the import action. After this several persons, events etc. should be listed in the tables.

You can also import from xml files if you have exported one before.

Save Changes

To save all changes (including the start times of the events gained from the optimization or from manual editing) go to the File menu and click Export Xml.

Automatic Timetabling

If you have some data (at least some persons, events and rooms) you can optimize the start time and room assignment of all events automagically.

Go to the menu Timetabling and click Start Optimization.

After finishing or stopping (see the progressbar at the bottom-right side) the optimization the start times and locations should have changed. To convince yourself that all persons have no clashing events you can go to the TimeFinder Planner in the Windows menu. All events should be scheduled in the first week:


TimeFinder released – An open source timetabler

This week I released the first public version (2009-v1) of my open source project called TimeFinder.

Although it is an alpha quality software it could be useful for schools (and universities). There are limitations! But today I will list the features only ;-)

All interested users can try it out, comment the functionality and provide feedback what they don’t understand or if they want a new feature (e.g. import/export from a special dataformat). Please contact me under peathal at yahoo . de


More detailed documentation can be found here.

Manual Timetabling

With TimeFinder you can create your timetable from scratch:

  1. Manually manage persons, events and locations
  2. Assign persons to events and a room to an event
  3. Required features for events can be defined. E.g. chemistry should only be scheduled in rooms with the feature ‘lab-suppport’.

Automatic Timetabling

Probably the most important feature of TimeFinder is its automatic timetabling engine. With that engine started (one single click after defining the data) you can optimize even difficult timetables within a few minutes or seconds. The algorithm was developed for the International Timetabling Competition 2007/08; it solved (no hard constraint conflicts) all problem sets in the given time.
The application is not limited to school or university timetable: for example it can be used for a JavaOne timetable, because it is nearly the same task: no person can attend more than one event at a time. And timefinder simply minimizes the conflicts for all attendees.

Visual Planner

Special thanks goes to Vijay Nathani for his work on the visual planner component, where he combines Java with JavaFX. The component is read-only at the moment and shows a list of all resources (e.g. persons) with its assigned events. Later on we will implement drag and drop functionality to change e.g. the start time of events visually.

Download & More Details

You can start TimeFinder as webstart application from here (21MB) or get the zip bundle (17MB). Java1.6 is required. The software stands under the Apache License, Version 2.0 – this is a very commercial friendly license – so, you can use the TimeFinder’s UI and the engine in nearly all (good!) applications.

The data storage of TimeFinder is currently file-based (xml) – a database storage will follow some day.

With MyDoggy the application supports drag and drop of the windows – so you can align and manage them as you like.

Further Thanks

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