Local Search Genetic Algorithms for the Job Shop Scheduling Problem

摘要

In previous work, we developed three deadlock removal strategies for the job shop scheduling problem (JSSP) and proposed a hybridized genetic algorithm for it. While the genetic algorithm (GA) gave promising results, its performance depended greatly on the choice of deadlock removal strategies employed. This paper introduces a genetic algorithm based scheduling scheme that is deadlock free. This is achieved through the choice of chromosome representation and genetic operators. We propose an efficient solution representation for the JSSP in which the job task ordering constraints are easily encoded. Furthermore, a problem specific crossover operator that ensures solutions generated through genetic evolution are all feasible is also proposed. Hence, both checking of the constraints and repair mechanism can be avoided, thus resulting in increased efficiency. A mutation-like operator geared towards local search is also proposed which further improves the solution quality. Lastly, a hybrid strategy using the genetic algorithm reinforced with a tabu search is developed. An empirical study is carried out to test the proposed strategies.