Digest No. 4 : December 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. 4. This issue is composed of two parts:

1. A call for contributions for a future timetabling repository.
2. Report on WATT Annual Meeting.

1. A FUTURE TIMETABLING REPOSITORY

This year in the Spring, I sent out to the WATT members a mail regarding the idea of creating a unified (and possibly standardized) repository for timetabling benchmarks. A few of you replied positively to that mail pointing me to their data (thanks to them!).

Unfortunately, at that time, I reached the conclusion that there was not enough coherent material to set up a valuable repository at that time.

Nevertheless, I did not give up completely on the idea. Maybe we should have another go at setting this up. It really would provide a very valuable resource for researchers in the field. Therefore, if you have any (new) data sets (in a readable format) that you would like to share with the WATT working group, please send me an email about them.

I really hope to be able to discuss a newly established repository in the next issue of WATT digest!.

2. WATT ANNUAL MEETING

The WATT annual meeting took place in Brussels on July 13th, 1998. It was organized by Jan A.M. Schreuder (University of Twente).

Six papers were presented. The papers were well spread over a range of timetabling topics. They described systems for dealing with high-schools, university courses, university exams, employee shifts (two), and sports league timetabling. The papers also turned out to cover a range of solution techniques, from Integer Programming to Constraint Reasoning, to Agent Technology.

The titles and abstracts of the papers presented in Brussels are listed below.

PAPER 1. Edmund K., Burke, J. P. Newall, "A System for University Examination Timetabling"

The Scheduling of examinations in higher institutions remains a problem to this day. We will present a system for the automated scheduling of such examinations developed as a project funded by Nottingham University. The system comprises of user interface designed to be friendly to the end user and a timetabling engine based on recent research conducted at the Automated Scheduling and Planning group on the timetabling problem. This system should bring efficient scheduling and room/resource allocation to university administrators.

PAPER 2. P., De Causmaecker, M. De Lille, P. De Pauw-Waterschoot, G. Vanden Berghe, A. Van Weert. "Using agent technology in employee timetabling: softening the human interface"

Agent technology offers a model for the development of flexible, dynamically customisable, distributed systems. We discuss the applicability of this technology in the domain of employee timetabling. We demonstrate the usefulness of the technology by showing a planning-system prototype for a specific domain. This domain is the adaptive scheduling of lab sessions in a higher education environment. We stress the importance of communication between the partners involved in the adaptive scheduling process, and we demonstrate how the agents paradigm can contribute to a better support for this communication. We present how additional aspects of the technology can be researched in other domains. We focus on the sample domains of the adaptive scheduling of the activities of a mobile worker and the adaptive rostering of nursing personnel.

PAPER 3. M., Dimopoulou, P., Miliotis, "Implementation of a University Timetabling System"

This paper reports the design and implementation of a PC-based computer system to aid the construction of a University course timetable. The specific difficulties to be faced are the restricted availability of classrooms and the increased flexibility of the students' choices of subjects that make the problem very tight. The system uses an Integer Programming (IP) model that assigns courses to time slots and rooms. The model is coupled with flexible front-end device that generates constraints corresponding to assumptions specified by the user and report writers that facilitate the evaluation of the resulting schedule.
The quality of the schedule produced depends on the relative position of the courses assigned to the available time periods, a condition that the IP model fails to capture. This weakness is faced by constructing groups of courses that are assigned to groups of time periods. Further, the objective function is used in a way that exports the user's experience and knowledge of the problem. The whole system is flexible and allows the easy construction and testing of alternative schedules which are pre-conditioned according to requirements specified by the user. The system has been used with success in the Athens University of Economics and Business.

PAPER 4. Martin, Henz, "Scheduling a Major College Basketball Conference - Revisited"

Nemhauser and Tricker recently presented the problem of finding a timetable for the 1997/98 Atlantic Coast Conference (ACC) in basketball. Their solution, found with a combination of integer programming and exhaustive enumeration, was accepted by the ACC. Constraint programming is another programming technique that can be used for solving combinatorial search problems such as sport timetabling. The goal of this research is to evaluate the potential of constraint programming for a class of sport timetabling problems that contains the ACC 1997/98 problem.
As in many combinatorial search problems, it is crucial to decompose the problem into manageable subproblems. We show that constraint programming allows to naturally implement an alternative problem decomposition. Applied to the ACC 1997/98 problem, this technique is dramatically superior in efficiency to the approach by Nemhauser and Trick. Furthermore, we found a solution that improved the timetable accepted by ACC with respect to five optimization criteria simultaneously.

PAPER 5. Benjamin, Jansen, "Automated rostering for secondary schools in the Netherlands".

Many of the Dutch secondary schools use the package Roosterfact to make their time schedules. Due to mergers of schools and changes in the teaching system, making the rosters is becoming more and more important and difficult. An automated rostering routine was developed and added to the system. It takes into account many of the practical constraints, for instance, that rooms (hence classes and teachers) are scattered over several buildings.

PAPER 6. Jan A.M., Schreuder, "Practical Advantages in using models for staff timetabling"

The assignment of staff or personnel to tasks to perform is a known but hardly satisfactory solved problem. If just qualifications for these tasks to perform are the only criteria, then the problem is easy - in polynomial time - to solve. In real world applications however, many factors have to be included like availability at certain periods, a 'fair' assignment, union rules,minimal due dates etc. In order to tackle these kind of - NP-hard -problems, a lot of OR models and techniques are available which can supply a handsome support and contribute to an increase of the quality of the timetables applied.

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.