Digest No. 3 : June 1998

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

Welcome to the WATT Digest no. 3. In this issue we discuss the following two topics:

1. A brief outline of the journal papers that have appeared during 1997 on the timetabling field.
2. Some general considerations about journals that publish timetabling-related papers.

1. Timetabling-related journal papers published in 1997

To my knowledge, not many journal papers have been published in the last year about timetabling. There are, of course, all the PATAT'97 papers.

The following three papers by D. de Werra are on the graph-theoretic side of things.

1. The combinatorics of timetabling, D. de Werra. European Journal of Operational Research 96, 504--513, 1997.
2. Preassignment requirements in chromatic scheduling, D. de Werra and N.V.R. Mahadev. Discrete Applied Mathematics 76, 93--101, 1997.
3. Restricted Coloring Models for Timetabling, D. de Werra. Discrete Mathematics 165, 161--170, 1997.

All three of them deal with the relation between timetabling and graph-coloring and they identify some subclass of problems which can be solved in polynomial time.

The following paper describes a less well-known (and less investigated) relationship for timetabling. That is, it describes a formulation of a teacher/subject assignment problem as a "charge transportation problem".

• The teacher assignment problem: A special case of the fixed charge transportation problem, Tim H. Hultberg and Domingos M. Cardoso. European Journal of Operational Research 101, 463--473, 1997.

The cited paper proposes not only a correspondence between the two problems, but also a solution algorithm based on branch and bound.

Finally, we have a paper on the use of genetic algorithms for an employee timetabling problem. Specifically, the following paper deals with a doctor scheduling problem, and it combines genetic algorithm with constraint satisfaction and hill climbing techniques.

• Solving a Timetabling Problem using Hybrid Genetic Algorithms, Lars V. Kragelund. Software---Practice and Experience 27(10), 1121--1134, 1997.

Regarding evolutionary techniques, I would like to mention also two papers by D. Corne and by B.C.H. Turton that have been presented at ICANNGA'97 (Int. Conf. on Artificial Neural Networks and Genetic Algorithms). This shows that the evolutionary technique community is very active in our field.

I am not aware of other journal papers in the field. If you know of any of them, please let me know, and I will post them in future issues together with the papers published in the new year.

2. Journals that publish timetabling-related papers

Now, I would like to draw a picture about the current status of journals that regularly accept and publish papers on timetabling. It is not my intention to discuss the quality of such journals. If somebody wants to express her/his opinions about some specific journals (or papers), such opinions are extremely welcome in future issues of this digest.

The journal that, by far, has recently published most timetabling papers is the "European Journal of Operational Research". This is also due to the fact that this journal actually publishes several issues per month and therefore it publishes a large number of papers in general. In any case, there is a clear evidence that papers on timetabling are welcome in this journal.

Timetabling is quite well represented also in the "Journal of the Operational Research Society", "Operations Research", and "Discrete Applied Mathematics". The latter even dedicated a special issue to timetabling in 1992. Still on the Operations Research side, a few papers have found a place in "Computers and Operational Research", "Management Science", "INFOR", and other journals.

Unfortunately, on the Artificial Intelligence side, many less papers have appeared. Anyway, they showed up mostly in "IEEE Expert", "IEEE Transactions on Knowledge and Data Engineering", and a few others.

Many papers have appeared in journals which cover a large spectrum of computer science topics, like "The Computer Journal", "Interfaces", and "Software---Practice and Experience".

The set of journals mentioned so far should give a brief overview of the possible "targets" for our future submissions. However, to this list I would like to add the newly-created Journal of Scheduling which welcomes papers about timetabling, and could actually become the "landmark" for our field.

If you have some other journal to propose, please feel free to write to me about it, and add them to the discussion. It will be very useful for all WATT members, if we keep a list of suitable journals.

It might also be a very good idea, if we were to keep a similar list for suitable conferences being held in the near future. This may be the topic of a futur issue of the WATT Digest. Please send me any information that you have.

That's it for this issue. Next one will be in August/September 1998. Please send me (Andrea Schaerf) contributions/comments/suggestions so as to make WATT Digest as valuable and useful as possible. I look forward to seeing your contributions.