WATT Group: Events - Abstracts 4th WATT Workshop

4th WATT Workshop

Presentations of the 4th WATT Workshop at the EURO XVIII
The Working Group on Automated Timetabling
Sanja Petrovic: Workshop Co-ordinator

Abstracts

Invited Talks

Global Constraints for Round Robin Tournament Scheduling
M. Henz, T. Mueller, S. Thiel, M. Van Brandenburg

In the presence of side-constraints and optimization criteria, round robin tournament problems are hard combinatorial problems, commonly tackled with tree search and branch-and-bound optimization. Recent results indicate that constraint-based tree search has crucial advantages over integer programming-based tree search for this problem domain by exploiting global constraint propagation algorithms during search. In this paper, we analyze arc-consistent propagation algorithms for the global constraints ``all-different'' and ``one-factor'' in the domain of round robin tournaments. The best propagation algorithms allow us to compute all feasible perfectly mirrored pattern sets with minimal breaks for intermural tournaments of realistic size, and to improve known lower bounds for intramural tournaments balanced with respect to carry-over effects.

ILP Models for Constructing Meeting Schedules for Professional Football Leagues
Jan Schreuder, David M. Panton

The object of the resarch into the scheduling of the Dutch Professional Football (soccer) League was to model and execute integer linear programming representations with standard commercial solvers. Because this scheduling is known to be complex, the approach is divided into the following steps. Firstly, a number of possible Home-And-Away pattern sets are constructed. To those stets matches are assigned such that Basic Match Timetables are formed. Finally, assigning teams to those timetables gives the required schedules. Due to practical considerations the research could be restricted to the compact and complete version of the Round Robin Tournament. The resulting models of the research proved to be tight giving a further improvement of the League Schedule. Still a lot of research questions remain to be answered like the necessary and sufficient conditions for Home-Away patterns to generate at least one Basic Match Schedule timetable.

Structured Cases in Case-Based Reasoning for Course Timetabling Problems
Edmund K. Burke, Bart Maccarthy, Sanja Petrovic, Rong Qu

We present a case-based reasoning system for educational timetabling problems where the problems are modelled structurally into attribute graphs. These graphs represent the source cases and give important information about the constraints and requirements of the problems. They are organised hierarchically with their solutions (timetables) as a decision tree. Structurally similar source cases are retrieved from the decision tree and adapted by a heuristic method employing domain knowledge to solve the target timetabling problems. The similarity measure takes into account the substitution, insertion and deletion of the vertices and edges between the attribute graphs of source cases and target cases. When the target case is larger than the source cases, it can be partitioned by the decision tree and solved by a multi-retrieval approach in which each retrieval searches for a partial solution for a sub-problem. A large number of systematically designed experiments are performed with different timetabling problems in the case bases. The results indicate that the structurally similar source cases retrieved can provide good quality timetables for target timetabling problems.

Assigning Magistrates to Sessions of the Amsterdan Criminal Court
Jan Schreuder

In the criminal court (Arrondissements rechtbank, sector strafrecht) of Amsterdam the assignment of magistrates (judges, officers, etc) to sessions needed to handle the cases presented, has become a problem last years mainly caused by the increase of so called mega-sessions. The assignment takes a period of 4 weeks at a time. The objective was to develop an optimal support system with which the scheduler could make the assignments in a shorter timeperiod, more reliable and at least the same quality. In order to reach to an optimal mix of support we used EXCEL for the more administration-data-representation parts and FORTRAN for the combinatorial parts. The approach followed in this applied research is based on three main steps after the input of the relevant data, which was quite a problem in itself. Firstly, a so-called Division Matrix is developed which indicates which magistrates can be assigned to which sessions, individual based. Next, in order to take into account the team assignment and the working conditions, a Combination Matrix is constructed indicating to which sessions in the week the magistrates can be assigned to. Finally, the Overall Schedule is constructed giving a minimal difference between the available working hours and the assigned ones. A basic problem is that the actual names and dates have to be incorporated from the beginning. Another problem is caused by the introduction of fixed teams of magistrates. Also incorporating Windows was not the easiest part.

A Tabu Search Approach to a Nurse Rostering Problem
F. Della Croce, F.S. Bellanti, G. Carello, R. Tadei

We consider a practical nurse rostering problem which arises at a ward of a hospital located in Torino. The nurse rostering problem is a typical employee timetabling problem where it is required each month to generate the nursing staff shifts with respect to various contractual and operational requirements. These requirements may be in conflict especially in those months in which manpower is reduced because several nurses are on holiday such as July or August. In this problem, it is required to consider both holidays planning and parametric contractual constraints, but no cyclic schedules and correspondingly weekly patterns. We propose a tabu search approach based on neighborhood which operates on partial solutions in order to avoid the generation of unfeasible neighbors. The solutions computed by the proposed procedure compare favorably with the ones obtained by the nurse in charge of the ward: the proposed procedure is now used in the hospital ward.

Integer Programming for University Timatabling
T. Birbas, S. Daskalaki, E. Housos

Despite all efforts on solving the University Timetabling, the problem still attracts the interest of many researchers. The main difficulty is lack of unified procedures that come up with optimal solutions with in a reasonable amount of time. The problem is combinatorial by nature and the number of feasible solutions is extremely large. As a result, the definition of the objective function plays an important role for the extraction of the optimal solution. In this paper, the problem of University Timetabling is solved for a Greek University. The problem is formulated as an Integer Programming Problem and takes into account hard constraints that organizational functions impose and soft constraints that good educational practices desire. Two sets of 0-1 variables are adopted, one set to take care of the assignment of courses to time periods and the other to take care of the course requirements for multiple time periods and repetitions of the same courses to different teams of students. The problem is solved separately for each department and schedules obligatory and optional courses that may require three types of teaching periods: lectures, recitations and laboratories. Each type caries its own characteristics as far as time requirements, number of students, and classroom specifications. The objective of the problem has evolved to be the compromise between desires of the educators and ease of students.

Solving Employee Timetabling Problems by Combining Restart Techniques with Machine Learning
E. Kaplansky, A. Meisels

An adaptation of a recent stochastic search technique for solving GSATs and combinatorial problems [Gomes, Selman and Kautz 1998], to searching random constraint networks (CNs) is presented. The "cutoff and restart" technique of Gomes et. al. improves the performance of the forward checking (FC) algorithm by more than an order of magnitude for some very hard problems. According to our preliminary experiments on random CNs, for random restarts to work with the FC algorithm, our proposed order of values has to be applied. In order for the proposed method to solve hard employee timetabling problems (ETPs), we investigate its integration with machine learning techniques. We use a recently proposed ETP model [Meisels and Schaerf 1999] for our experimentation with the algorithm. The proposed method automatically adapts the search algorithms to specific features of the problem at hand. Thus, the performance of the algorithm improves with experience. Our learning paradigm monitors the search pattern of the CN solver and records the two specific parameters: The number of constraints checks the solver executes before restarting and how many times to restart before we double the cutoff parameter. Learning repeated patterns of success, the algorithm sets the parameters of the solver and demonstrated a fast learning curve for a family of randomized real world ETPs.

Tess - A Computer-Based Support System for Timetabling Prcatitioners
Wai-Yin Ng

We approach school timetabling with a keen concern for the needs of the practitioner. Two important observations are made. First, the problem of timetabling is not that solutions may not be found soon enough. Rather, it is the continual toil the practitioner suffers. Second, the development and use of ad hoc procedures and tactics is the mark of an experienced practitioner. Such procedures and tactics are highly situational, varying widely according to a school's particular composition and relative importance of resources, goals and constraints. Such a perspective to the timetabling problem has led us away from automated timetabling. The ideal of automated timetabling implies receiving a problem specification in the start and removing the practition "from the loop" thereafter, which we do not consider a commediable thing to do. Timetabling in practice is not about synthesizing solutions for an explicit and static problem. On the contrary, the problem the practitioner receives, often overconstrained with a confluence of requirements from the many parties concerned, is subject to contingent negotiation, for which the practitioner has to stay "in the loop". No automatic algorithm may proxy the practioner in the face of such mandatory contingency. This paper describes our experience with Timetabling Expert Support System (TESS) so designed, which has been installed in over one thousand schools in Hong Kong since mid-nineties.