|
Abstracts
Constributed Talks
A System for University Examination Timetabling
E.K. Burke, J.P. Newall
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.
Using Agent Technology in Employee Timetabling: Softening
the Human Interface
P. De Causmaecker, M. De Lille, P. De Pauw-Waterschoot,
G. Vanden Berghe, A. Van Weert
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.
Implementation of a University Timetabling System
M. Dimopoulou, P. Miliotis
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.
Scheduling a Major College Basketball Conference - Revisited
Martin, Henz
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.
Automated Rostering for Secondary Schools in the Netherlands
Benjamin, Jansen
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.
Practical Advantages in Using Models for Staff Timetabling
J.A.M. Schreuder
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.
|
