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. |
| Keywords: | |
| 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. |
| Download: | POSTSCRIPT COPY |
![[Search These Pages]](http://www.dai.ed.ac.uk/icons/dai_search.gif){kind=icon}
![[DAI Home Page]](http://www.dai.ed.ac.uk/icons/dai_home.gif){kind=icon}
![[Comment]](http://www.dai.ed.ac.uk/icons/dai_comment.gif){kind=icon}