A Standard Framework for Timetabling Problems

摘要

When timetabling experts are faced with a new timetabling problem, they usually develop a very specialised and optimised solution for this new underlying problem. One disadvantage of this strategy is that even slight changes of the problem description often cause a complete redesign of data structures and algorithms. Furthermore, other timetabling problems cannot be fit to the data structures provided. To avoid this, we have developed a standardised framework which can describe arbitrary timetabling problems such as university timetabling, examination timetabling, school timetabling, sports timetabling or employee timetabling. Thus, a general timetabling language has been developed which enables the definition of resources, events and constraints. Furthermore, we provide a way to apply standard problem solving methods such as branch-and-bound or genetic algorithms to timetabling problems defined by means of the general timetabling language. These algorithms can be improved by problem-specific user-defined hybrid operators. In this paper we present a generalised view on timetabling problems from which we derive our timetabling framework. The framework implementation and its application possibilities are shown with some concrete examples. The paper concludes with some preliminary results and an outlook.