Malcolm McIlhagga, Phil Husbands
This CSRP describes a Distributed Genetic Algorithm (DGA) which has been used to solve generic scheduling problems. The system is capable of allowing its user to define and solve any scheduling problem using a Scheduling Description Language (SDL), e.g. job-shop scheduling, time-tabling, resource sequencing etc. We will describe a unique encoding/decoding scheme that allows simple representation, straightforward chromosome recombination and fast schedule building and therefore evaluation times. A comparative study has been made of the DGA, random search and a heuristic method of scheduling using 100 very large scale problems; problems of the order of 500 tasks. This is the first study of its kind to look at problems of this scale. It was found that, although it is possible to reduce the makespan of a schedule by about 40% of a randomly generated solution using dispatching rules, only the DGA produced solutions that had as high as a 60% reduction.
Download compressed postscript file