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

Research Paper #623

Title:A Promising Genetic Algorithm Approach to Job-Shop Scheduling, Rescheduling, and Open-Shop Scheduling Programs
Authors:Fang,H; Ross,PM; Corne,D
Date:Dec 1993
Presented:Published in Proc. of 5th International Conference on Genetic Algorithms.
Abstract:The general job-shop scheduling problem is known to be extremely hard. We describe a GA approach which produces reasonably good results very quickly on standard benchmark job-shop scheduling problems, better than previous efforts using genetic algorithms for this task, and comparable to existing conventional search-based methods. The representation used is a variant of one known to work moderately well for the traveling salesman problem. It has the considerable merit that crossover will always produce legal schedules. A novel method for performance enhancement is examined based on dynamic sampling of the convergence rates in different parts of the genome. Our approach also promises to effectively address the open-shop scheduling problem and the job-shop rescheduling problem.

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