Recent research directions in automated timetabling

The aim of this paper is to give a brief introduction to some recent approaches to timetabling problems that have been developed or are under development in the Automated Scheduling, Optimisation and Planning Research Group (ASAP) at the University of Nottingham. We have concentrated upon university timetabling but we believe that some of the methodologies that are described can be used for different timetabling problems such as employee timetabling, timetabling of sports fixtures. etc. The paper suggests a number of approaches and comprises three parts. Firstly. recent heuristic and evolutionary timetabling algorithms are discussed. In particular. two evolutionary algorithm developments are described: a method for decomposing large real-world timetabling problems and a method for heuristic initialisation of the population. Secondly, an approach that considers timetabling problems as multicriteria decision problems is presented. Thirdly, we discuss a case-based reasoning approach that employs previous experience to solve new timetabling problems. Finally. we outline some new research ideas and directions in the field of timetabling. The overall aim of these research directions is to explore approaches that can operate at a higher level of generality than is currently possible. (C) 2002 Elsevier Science B.V. All rights reserved.