The University of Edinburgh -
Division of Informatics
Forrest Hill & 80 South Bridge

MSc Thesis #93111

Title:Using Genetic Algorithms for Job-Sequencing msc Dissertation
Date: 1993
Abstract:Many optimisation techniques have been attempted on the popular A.I. research area, scheduling. This project uses GAs to solve job-sequencing problem which is a kind of scheduling problem. A pseudo-parallel version of GA has been adopted and stream-lined to suit the problem domain, which is n jobs to single machine and n jobs to m parallel-machine problems with a series of constraints. Special GA crossover and mutation operators are introduced to cater to the specific chromosome representation which depicts a sequence of jobs that has to be complete and non-repetitive. An exhaustive set of experiments has been carried out to fine-tune GAs performance. A comparison of GA2 with 3 heuristic rules, namely shortest processing time, longest processing time and earliest due date, and exhaustive search is conducted. An attempt has been made to explore and analyse GAs results using clustering techniques. Suggestions have been made in respect to how this area can be further explored. The final system developed can be easily adapted for future problems of similar nature.

[Search These Pages] [DAI Home Page] [Comment]