| 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: |
|
| 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 |