The application of genetic algorithms with meta-learning capabilities to job shop scheduling algorithms

This paper examines an efficient way of finding good solutions to job shop scheduling problems by using genetic algorithms (GAs) with meta-learning capabilities. An algorithm is discussed which dynamically adapts the probabilities in which the various operators, such as mutation and crossover are applied as the GA runs. A number of new crossover and mutation genetic operators are discussed which were found to be effective with the Job Shop Scheduling problem. A second algorithm is presented which optimises the other internal probability parameters of the scheduling GA. This is a meta-GA which has the probability parameters of the scheduling GA encoded in its chromosomes. This meta-GA is responsible for breeding good parameter sets for the scheduling GA. A set of optimal parameters is presented which was optimised on a 10 machine, 10 job problem. It is demonstrated that the combination of these two meta-learning techniques results in a GA which quickly evolves to quality solutions. Ths discussion of results illustrates the performance of such a GA on a test example shows that a scheduling GA with well-bred internal parameters and adaptive operators has comparable performance with single heuristic methods.