language: en

Investigating Genetic Algorithms for Scheduling

Hsiao-Lan Fang

[MSc Dissertation]

Department of Artificial Intelligence University of Edinburgh
1992

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 Edinburg, 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 5 minutes) and satisfactorily (producing timetables which are measurably better than those produced by the human schedulers). The project 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 operator 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.

[Table of Contents]

1. Introduction