A genetic algorithm applied to a classic job-shop scheduling problem

Abstract

Job-shop scheduling is essentially an ordering problem. A new encoding scheme for a classic job-shop scheduling problem is presented, by which a schedule directly corresponds to an ordering string. For the new encoding, a simple but highly effective crossover operation is contrived, and the problem of infeasibility in genetic generation is naturally overcome. Within the framework of the newly designed genetic algorithm, the NP-hard classic job-shop scheduling problem can be efficiently solved with high quality. Moreover the optimal solutions of the two famous benchmarks, the Fisher and Thompson's 10 × 10 and 20 × 5 problems, are found.