Genetic Algorithms for Job-Shop Scheduling

This chapter considers job-shop scheduling problems, which determine a processing order of operations on each machine in order to minimize the maximum completion time. By incorporating the concept of similarity among individuals into the genetic algorithm that uses a set of completion times as individual representation and the Giffler and Thompson algorithm-based crossover, an efficient genetic algorithm for job-shop scheduling problems is presented. As illustrative numerical examples, 6 x 6, 10 x 10, and 15 x 15 job-shop scheduling problems are considered. The comparative numerical experiments with simulated annealing and the branch and bound method for job-shop scheduling problems are also demonstrated.