PATAT 2012: Practioners Welcome

The PATAT (Practice and Theory of Automated Timetabling) conference officially started today, although there was a social event yesterday.
One of the innovative aspects of PATAT, which is reflected in the conference title, is that it attracts both academics and practitioners.

The 2012 conference (the ninth in the conference series) has probably attracted more practitioners than previous conferences. The practitioners are drawn from people who work in universities who have the unenviable task of actually generating timetables of various types (for example, examination timetable, course timetable etc.) as well as companies that develop software to assist the timetabling community. Whilst not being a complete list, the following companies are present at PATAT 2012.

These three companies are arguably some of the leading software companies in the timetabling sector and it is good to see them interacting with the scientific community.

Given the number of practitioners present at PATAT, the conference program reflects this important element of the conference, with a stream running throughout the conference called Practical University Timetabling where the presentations are given by colleagues who work in timetabling offices or by software vendors.

It is good to see that conferences, such as PATAT, recognise the importance of including the end users and software vendors in helping to direct the research direction which, in my view, can only be a good thing.

If you are interested, more PATAT posts can be seen here.

PATAT 2012 Conference

I am just about to head off to the PATAT 2012 conference. This year it is in Oslo which would normally be a short hop from the UK but when you live in Malaysia it is a 15 hour flight! This is the 9th PATAT (Practice and Theory of Automated Timetabling) conference in the series, which can be traced back to 1997 (see here, and a full list is given at the end of this post).

The venue for this years conference looks superb and although the weather might be a bit cooler than Kuala Lumpur I am looking forward to visiting Oslo and Norway.

The conference oragnisers (this year the conference has been organised by SINTEF), have put together an excellent programme. Underpinning it are three plenary speakers (Gilbert Laporte, Greet Vanden Berghe and Paul McMullan), backed up by keynote talks from Ruth Drysdale and Lee Hollins. The main sessions comprise about 55 talks and a number of software demonstrations.

One of my co-authors is presenting one of our papers.

Jerry Swan, Ender Ozcan and Graham Kendall, Co-evolving add and delete heuristics.

PATAT would not be PATAT with a strong social program, and that is certainly in evidence this time round.

So, it looks like being a good week, once the 14 hour flight is out of the way.

Finally, although this information is given on this page, for ease of reference, here is the complete list of PATAT conferences to date.

  1. The 9th conference will be held at Son, Norway, from 28th to 31st August, 2012.
  2. The 8th conference was held at Queen’s University Belfast, Northern Ireland, from 10th August to 13th August, 2010.
  3. The 7th conference was held at CIRRELT, Universit de Montral, Montreal, Canada from 19th August to 22nd August, 2008.
  4. The 6th conference was held at the Masaryk University, Brno, Czech Republic from 30th August to 1st September 2006.
  5. The 5th conference was held at Sheraton Station Square, Pittsburg PA, U.S.A. in August 2004.
  6. The 4th conference was held at KaHo St.-Lieven, Gent, Belgium in August 2002.
  7. The 3rd conference was held at Fachhochschule Konstanz – University of Applied Sciences, Constance, Germany in August 2000.
  8. The 2nd conference was held at the University of Toronto, Canada in August 1997.
  9. The 1st conference was held at Napier University, Edinburgh, Scotland in September 1995.

PATAT 2010: Googlemaps and Multimaps

In an earlier PATAT conference blog I described the multi-objective methodology that I used. I finished by saying that in basing any methodology on travel distances between football clubs you have to somehow calcuate the distances between all the clubs (or at least those in the same division).

When I first started collecting all this data I decided to use one of the motoring organisation web sites. The three main contenders were the AA, the RAC and Green Flag. All of these web sites enable you to enter a start and end postcode (zip code if you are stateside) and they return various information such as a map of the route, the distance and the estimated time that it will take you to drive between the two locations. Of course, I was particularly interested in the distance.

To collect all the data I finally decided to use Green Flag. This was simply because when you enter the two postcodes and hit the “Find Route” button this information is stored in the URL that is shown in the address bar. The other two (the AA and RAC) did not do this. As none of these services had an API, being able to use a URL that contains this information was very useful, else collecting the data would have been even more labourious than it was (even so, it was still labour intensive). Being able to use the URL meant that you could build up the URL using something like Excel (which is what I did) and then upload that to a web site. It was now a case of simply clicking each link and recording the information. It was still a very long process, but not as long as having to type in each postcode separately.

I needed a better method, especially as I wanted to collect data each season and as the current (very manual) process takes me many hours I typically delayed doing it.

The candidates were essentially googlemaps or multimap (which loos like they have now been taken over by Bing); at least they offered both and API and are free. Of course, there are many paid services around but they tend to be very expensive.

In a future blog(s), I’ll let you know how these work and what use I made of them.

Other posts about PATAT can be seen here.

PATAT 2010: Multi-objective Sports (Football) Scheduling


At the recent PATAT (8th International Conference on the Practice and Theory of Automated Timetabling) conference I was fortunate enough to be invited to give a plenary presentation.

My talk focussed on sports scheduling. Indeed, the title was “Scheduling Football (Soccer) Fixtures: Progress Made to Date and Future Challenges“. I focussed on the conflicting objectives when trying to minimise travel distances, whilst also trying to reduce pair clashes (which can be considered as local derbies for the sake of this discussion).

This is a classic case of a multi-objective problem where minimising one objective causes the other to increase and vice versa. It is not (usually) possible to minimise both objectives, instead you are looking for a trade off. These are plotted on a pareto front where a user would then decide which trade off solution is the best.

In the plenary talk, I showed that it was possible to reduce both the distance and the pair clashes such that (sometimes) the distance did not significantly increase. This is a potentially useful result as it means that supporters do not have to travel any further (statistically) and the policing costs are reduced as they do not have to police so many local derbies.

I should say that this result is only work in progress at the moment in that it has not been verified by the football authorities or the police, but I would hope that it would be of interest to them.

In the same talk, I also discussed how I collected the data for this work (which essentially is the various distances between football clubs). This involved using Google maps and Multimap APIs. I’ll talk about this in the next blog. I’ll also provide a link to the paper (as I don’t have it to hand at the moment). But, if you are interested the reference is:

Kendall G., McCollum B., Cruz F. and McMullan P. (2010) Scheduling English Football Fixtures: Consideration of Two Conflicting Objectives. In proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2010), 11-13 August 2010, Queen’s University, Belfast, UK, pp 1-15

and you can access the paper here.

Other PATAT posts can be seen here.

Summer Conferences

It’s been a busy couple of weeks as I have been attending two scientific conferences. Last week I was at the PATAT (Practise and Theory of Automated Timetabling) conference in Belfast and I have just returned from the IEEE Conference on Computational Inetlligence in Games (CIG 2010) in Copenhagen.

Both conferences consider very different areas (not surprisingly one is about timetabling and the other is about computer games).

I’ll report more on each conference in blogs in the next few days.

Bin Packing Made Easier?

I have always found the following example interesting. I remember that it was Peter Ross who first showed me this during a presentation at a conferenec we were both attending.

The example demonstrates that an algorithm can act in an unexpected way when you make a very small change to the input data.

The example is drawn from bin packing. In this problem, you are given a number of items, all of which have a weight. Let’s assume that we have the following 33 items.

442, 252, 127, 106, 37, 10, 10, 252, 252, 127, 106, 37, 10, 9, 252, 252, 127, 85, 12, 10, 9, 252, 127, 106, 84, 12, 10, 252, 127, 106, 46, 12, 10

We are also given an infinite number of bins, each one having a certain capacity. Let’s assume that the capacity of our bins is 524.

The aim is to pack all 33 items into as few bins as possible.

How would you do it? What algorithm would you use?

One possible algorithm is as follows:

1) Sort the items into descending order of size, thus:

442, 252, 252, 252, 252, 252, 252, 252, 127, 127, 127, 127, 127, 106, 106, 106, 106, 85, 84, 46, 37, 37, 12, 12, 12, 10, 10, 10, 10, 10, 10, 9, 9

2) Take each item in turn and place it into the first bin that will accommodate it. The bins are also considered in the order they were first used.
So, to start we have no bins available, so we open one. We take the first item (442) and place it in that bin. Now we take the next item (252). We cannot fit this into the bin we have just opened (as 442+252 > 524) so we open another bin.
The next item (252) will be placed in the second bin. The next item (252) will have to open a third bin.

… and so on.

If you apply this algorithm, you will get this solution

Bin 1: 442, 46, 12, 12, 12 = 524
Bin 2: 252, 252, 10, 10 = 524
Bin 3: 252, 252, 10, 10 = 524
Bin 4: 252, 252, 10, 10 = 524
Bin 5: 252, 127, 127, 9, 9 = 524
Bin 6: 127, 127, 127, 106, 37 = 524
Bin 7: 106, 106, 106, 85, 84, 37 = 524

You’ll notice that we have a solution that requires 7 bins and, moreoever, each bin is completely full. Therefore, we know we have found an optimal solution.

As an aside, what we have just done is used a heuristic (a rule of thumb). This one is known as Largest Fit, First Fit. We could come up with many more. For example, we could sort the pieces in different ways, we could consider all the open bins before deciding which one to use etc.

The question now arises, is the largest fit, first fit heuristic always the best heuristic to use for the bin packing problem?

Let’s see.

Take our list of sorted items again. That is:

442, 252, 252, 252, 252, 252, 252, 252, 127, 127, 127, 127, 127, 106, 106, 106, 106, 85, 84, 37, 37, 12, 12, 12, 10, 10, 10, 10, 10, 10, 9, 9

But this time remove an item (say 46 – which has been removed from the list above).
We know that we can use seven bins to pack these items, and have 46 units left over.

So, let’s apply the largest fit, first fit heuristic and see what happens.

This is the result.

Bin 1: 442, 37, 37 = 516
Bin 2: 252, 252, 12 = 516
Bin 3: 252, 252, 12 = 516
Bin 4: 252, 252, 12 = 516
Bin 5: 252, 127, 127, 10 = 516
Bin 6: 127, 127, 127, 106, 10, 10, 10 = 517
Bin 7: 106, 106, 106, 85, 84, 10, 10, 9 = 516
Bin 8: 9 = 9

This is quite surprising (well, it is to me). We have removed an item, but had to use an extra bin.

Of course, we could develop another heuristic that only used 7 bins, but would that heuristic work well on other problem instances? Or, to put it another way, if you were presented with an instance of a problem you had not seen which heuristic would you use?

There is some work being done in an area termed hyper-heuristics (which I’ll blog more about in the future) which is trying to address problems such as those described above.

If you are interested in reading more about hyper-heuristics, you might like to visit my publications page (http://www.cs.nott.ac.uk/~gxk/gxk1/publications.html).

Good introductory articles are:

  1. Cowling P., Kendall G., Soubeiga E.A Hyperheuristic Approach to Scheduling a Sales Summit. In LNCS 2079, Practice and Theory of Automated Timetabling III : Third International Conference, PATAT 2000, Konstanz, Germany, August 2000, selected papers (eds Burke E.K. and Erben W), Springer-Verlag, pp 176-190, ISBN : 3-540-42421-0
  2. Burke E.K., Kendall G. and Soubeiga E. (2003) A Tabu-Search Hyper-Heuristic for Timetabling and Rostering. Journal of Heuristics , 9(6), 451-470, 2003
  3. Burke E., Hart E., Kendall G., Newall J., Ross P. and Schulenburg S. (2003) Hyper-Heuristics: An Emerging Direction in Modern Search Technology. Handbook of Meta-Heuristics (Glover F., ed), pp 457 – 474, Kluwer