EPSRC logo

Details of Grant 

EPSRC Reference: GR/J44513/01
Title: GENETIC ALGORITHMS FOR GENERIC TIMETABLING PROBLEMS
Principal Investigator: Ross, Professor P
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Artificial Intelligence
Organisation: University of Edinburgh
Scheme: Standard Research (Pre-FEC)
Starts: 01 July 1993 Ends: 30 June 1996 Value (£): 152,644
EPSRC Research Topic Classifications:
Artificial Intelligence
EPSRC Industrial Sector Classifications:
Related Grants:
Panel History:  
Summary on Grant Application Form
To do a systematic study of the potential of genetic algorithms (GAs) for solving a wide variety of timetabling problems. To develop a general GA-based architecture that can handle a wide variety of timetabling problems. To collect a substantial corpus of timetabling problems from different areas, for use as benchmark problems.Progress:We have developed a general-purpose GA-based timetabling program in C, called GATT, which accepts a problem description in a simple special-purpose language. It can handle a wide variety of constraints, e.g. travel times between events; room capacity constraints; restrictions on when events can happen, and/or their order; availability of personnel and rooms; varying duration of events; whether more than one event can happen at a location (e.g. exams) or not (e.g. lectures); spread constraints (e.g. so that students should not have consecutive exams without a break of some minimum duration). We have collected a good set of practical problems from universities, schools and colleges which have helped us to develop GATT into a genuinely useful tool for solving practical problems. Indeed, we have been able to provide good solutions to major exam and lecture timetabling problems for some other institutions, which they have used. We have also used problem generators to study many random instances of different classes of problems, from light to very highly constrained. It is clear that, for modestly-constrained problems with only binary constraints, conventional graph-colouring methods are better than GAs; and for modeslty-constrained problems also having non-binary constraints, simple hill-climbing or simulated annealing can do better. GA-based methods work best on highly-constrained problems. The classical GA model (the Holland & Goldberg model with simple crossover and random mutation) is generally insufficient, it is necessary to introduce special-purpose operators such as forms of directed mutation. A basic GA program (PGA) capable of solving a useful subest of timetabling problems has been made available by FTP and has been used around the world; GATT is based on this. Refereed papers describing the work so far have been published in the 1994 AISB workshop on Evolutionary Computing (proceedings available from Springer-Verlag); in the proceedings of ECAI-94; in the proceedings of PPSN-3, 1994 (Springer-Verlag); and at the 13th UK Planning SIG. Several other papers are in preparation. Papers and some software are available by FTP from ftp.dai.ed.ac.uk. We are collaborating with Napier and Nottingham Universities to run an international conference on the theory and practice of timetabling, to be held in Edinburgh in September 1995.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Summary
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.ed.ac.uk