The Parallel Genetic Algorithm for the Job-shop Scheduling Problem

Y.-B. Yoo and D. Helzer (USA)


genetic algorithms, job-shop scheduling, parallel genetic algorithms, island model, soft computing


A genetic algorithm (GA) is a heuristic that can be used to solve optimization problems. A GA maintains a population of candidate solutions and this population is evolved until a final, near-optimal solution is obtained. A parallel genetic algorithm (PGA) can reduce the execution time by dividing the population among a number of processors. Each processor represents an island that evolves independently and occasionally exchanges individuals with its neighboring islands. This paper describes how a PGA can be implemented to solve the job-shop scheduling problem (JSSP). Experimental results using nine processors show that a PGA is able to obtain JSSP solutions that are significantly better than a serial GA in a fraction of the elapsed time.

Important Links:

Go Back