WATT Digests

 WATT Logo

Digest No. 2 : September 1997

Editor: Andrea Schaerf

Please send material/submissions/comments for the WATT Digest to aschaerf@dis.uniroma1.it. WATT Digests are emailed monthly to WATT members and also appear here.

Contents

This issue, prepared following the 2nd PATAT conference, is devoted to an appreciation of the events and presentations at PATAT '97.

Let us start with the conference numbers: The participants in the conference were 99 (whereas there were 69 at the first conference in Edinburgh two years ago). The presentations scheduled were 51 divided in four classes: 3 invited lectures, 17 full papers, 22 abstracts, and 9 vendor presentations.

Now some general comments: The conference was really perfectly organised by Mike Carter and his staff (many thanks to them). In particular, The conference location was comfortable and the social programme was very enjoyable. In general, the audience seemed to be very interested to the talks and there was a good interaction among participants. The delegates tended to split quite evenly among the three parallel sessions.

More technically, the conference gives us a chance to draw an accurate picture of the status of the research in automated timetabling and its research trends. To this aim, we can make some classification and statistics on the papers presented at the conference. Needless to say, the following discussion is rather subjective, and reflects my personal perspective. I would be very glad to hear different opinions from other members.

In details, I classified the papers presented at PATAT-97 (leaving out the invited lectures) based on the following three points:

  1. What is the main focus in the paper.
  2. What type of problem the paper tackles.
  3. What solution technique is employed in the work described.

Regarding point 1, my results are as follows:

  • Complexity issues: 1
  • Distributed timetabling systems: 1
  • Experiences: 4
  • Implementations: 2
  • Package general features: 7
  • Interactive vs. batch timetabling: 0
  • Relationship with other scheduling problems: 0
  • Solution Techniques: 26
  • Problem specification and modelling: 4
  • Survey: 3

These results show that most of the work is focussed on the solution techniques. My interpretation of this fact is that people believe that there is still a lot to do on this side, before moving to more advanced topics such as parallelism or interactivity.

Regarding point 2, the situation is the following:

  • University course scheduling: 14
  • University exam scheduling: 7
  • Group sectioning: 1
  • Room Assignment: 1
  • High school scheduling: 5
  • Sport scheduling: 3
  • Employee timetabling (Workforce scheduling): 5
  • Scheduling (in general): 1

These numbers show that most of the work considers university timetabling (either exams or courses). My explanation for this phenomenon is that researchers are more inclined to work on a problem in which they are more personally involved and that they know better. Working on university problems also simplifies the relationship with the end-user.

An alternative point of view is that universities usually have more money to spend for software than schools and other institutions, and therefore they represent a more interesting market for timetabling packages.

Regarding the solution techniques (point 3), this is my classification:

  • Direct heuristics: 4
  • Constraint programming
    • CLP systems: 1
    • Specialised constraint solvers: 4
    • Constraint-based assignment + local repair: 4
  • Evolutionary methods
    • Genetic algorithms: 6
    • Memetic algorithms: 1
  • Graph colouring heuristics: 1
  • Expert Systems (Knowledge-based systems): 0
  • Integer programming: 4
  • Local search
    • Simulated Annealing: 2
    • Tabu-search: 2
  • Ant colony: 1
  • Combination of different techniques: 2

These numbers show that so far there is no "winning" technique for timetabling. On the contrary, the research is quite well spread across many fields.

I let you to draw your own additional conclusions from these figures. I want to stress instead another specific aspect of the field that emerges from the analysis of the papers presented at the conference. This aspect concerns the "cohesion" of the community. Looking throughout the proceedings I found out that in timetabling. On the contrary, the research is quite well spread across many fields.

I let you to draw your own additional conclusions from these figures. I want to stress instead another specific aspect of the field that emerges from the analysis of the papers presented at the conference. This aspect concerns the "cohesion" of the community. Looking throughout the proceedings I found out that in only very few cases different techniques are compared among themselves. Further in no paper at all were the obtained results compared with previously published results or with established benchmarks.

This fact shows that current research is mostly based on isolated efforts, and that the timetabling community is not yet sharing data and ideas as much as it should. There is still a long way to go before research in this field becomes a real cooperative effort.

I believe that it is exactly through conferences like the PATAT series that such cooperation could be established. Therefore, I am already looking forward (and working) for the next PATAT. In the mean time, I hope that other means of communication, like this EURO working group, could help as well.

That's it for this issue. Next one will be in December 1997. PLEASE send me (Andrea Schaerf aschaerf@dis.uniroma1.it) contributions/comments/suggestions so as to make WATT Digest as valuable and useful as possible. It simply will not work unless you, the members of WATT, contribute. I look forward to seeing your contributions. Some of what I said above might be considered to be controversial. If you disagree with me, you are strongly encouraged to send a contribution to the next issue.