Division of Informatics
Forrest Hill & 80 South Bridge
MSc Thesis #92115 | |
|---|---|
| Title: | Investigating Genetic Algorithms for Scheduling |
| Authors: | Fang,H |
| Date: | 1992 |
| Presented: | |
| Keywords: | |
| Abstract: | This project investigates the use of Genetic Algorithms on the problem of scheduling exam timetables for the AI/CS MSc exams at the University of Edinburgh, with the constraints that the timetables should be as fair as possible on students (avoiding clashes, three exams in a day, and consecutive exams). This problem is very hard to solve because of the extremely large number of possible timetables, and the difficulty of simultaneously satisfying a large number of students. Human experts take many iterations at this task, until over several days of trial and error and consultation with students a timetable is arranged. This project shows that a Genetic Algorithm system can perform this job quickly (in about 20 minutes) and satisfactorily (producing timetables which are measurably better than those produced by the human schedulers). The dissertation describes Genetic Algorithms, the representation used for exam timetables, and also discusses experiments in which ways are studied to improve performance. We find that an elitist strategy using inverse square pressure, variation of operation rates (crossover and mutation) and fixed-point uniform crossover is a measurably better strategy than traditional Genetic Algorithms on this problem. The system described can be easily adapted for use in similar timetabling problems. |
| Download: | NO ONLINE COPY |
![[Search These Pages]](http://www.dai.ed.ac.uk/icons/dai_search.gif){kind=icon}
![[DAI Home Page]](http://www.dai.ed.ac.uk/icons/dai_home.gif){kind=icon}
![[Comment]](http://www.dai.ed.ac.uk/icons/dai_comment.gif){kind=icon}