A promising genetic algorithm approach to job-shop scheduling, rescheduling, and open-shop scheduling problems

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 bench-mark job-shop scheduling problems, better than previous eorts using genetic algorithms for this task, and comparable to existing con-ventional search-based methods. The rep-resentation 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 le-gal schedules. A novel method for perfor-mance enhancement is examined based on dynamic sampling of the convergence rates in dierent parts of the genome. Our approach also promises to eectively address the open-shop scheduling problem and the job-shop rescheduling problem.