Friday, September 14, 2007

1993 Top marks for timetables in the generation game

Top marks for timetables in the generation game

  • 26 June 1993
  • From New Scientist Print Edition. Subscribe and get 4 free issues.

Here is an examination question. How long does it take a university lecturer to devise an exam timetable for 90 students who can choose 8 papers from more than 60 being offered? All the exams must take place within seven days, there must be no clashes, and as few students as possible should have to sit two papers consecutively or more than two per day.

At the University of Edinburgh's artificial intelligence department the answer used to be: up to seven weeks. But now a computer program has done the job, cutting the time to one minute. And in the timetable that it drew up for this term, no student had to sit consecutive 90-minute exams - a significant improvement on the past two years.

Designed by David Corme, a research assistant, the timetabling program uses a 'genetic' algorithm. It makes up 100 random timetables, and divides them into 50 pairs which 'mate' with each other. Every pair produces two 'offspring' which take their characteristics from their parents. Each second-generation timetable is then assigned a score depending on how well it fits the timetabling conditions. This is rather like measuring how successful a living organism is at finding food.

The program next mates 50 pairs from the second generation. The probability of a particular timetable being chosen depends on its score, so the best could be selected several times. An especially good timetable might even mate with itself - in which case it would produce unchanged offspring. After several generations, the offspring converge on the best solution.

Corme believes there are many important areas where genetic algorithms could improve scheduling. For airlines, railways and coach operators, vehicles and their crews need to be in the right place at the right time. Such algorithms could also help to schedule jobs in engineering workshops.

Working with research student Hsiao-Lan Fang, Corme devised a simple code to represent the exam timetable. For example 3,7,11,2,7 represents the timetable in which exam 1 occupies the third time slot, exam 2 the seventh slot, exam 3 the eleventh slot and so on. In this example, exams 2 and 5 clash because they are both allocated to the seventh slot. Scoring is by penalties, with a large penalty for a clash and a smaller one if any student has to sit papers consecutively.

When the parent 3,7,11,2,7 is mated with another parent, such as 1,2,3,4,5, the digits or 'genes' are swapped about to generate the two children. This can be done in many different ways, such as swapping the first three and the last two to give 1,2,3,2,7 and 3,7,11,4,5. 'You then have to evaluate each of the offspring,' says Corme. 'You almost certainly find a better set of timetables and (eventually) you evolve one which is optimum.' Poor timetables are not removed from the population: 'You don't discard anything, just give it a lower chance of reproduction,' he says.

The program was tried out on the 1991 and 1992 timetables, which had been set manually. In 1991 the manual timetable produced 15 instances of students sitting consecutive exams: in the computer program, this scored 37 penalty points. The genetic algorithm produced a timetable that scored a perfect 0. In 1992, when there were more students, the manual timetable had 29 consecutive exams and two cases of three exams in a single day - a disappointing score of 101. The final genetic algorithm scored 3, representing just one student sitting consecutive papers.

This summer, with still more students, the course organiser did not even try to produce a timetable manually but handed over the task to the algorithm, which produced another perfect timetable. The department is now considering setting its lecture timetable by computer. Corme says that all you have to do to try the program on another problem is to think up the right notation to represent the problem and the right scoring system.

From issue 1879 of New Scientist magazine, 26 June 1993, page 19

No comments: