A Cooperative Coevolutionary Genetic Scheduling Algorithm for solving stochastic Job Shop scheduling

摘要

Coevolutionary algorithms have gained much attention in the past few years for its powerful searching ability.In this paper,we combine the coevolutionary computation with genetic algorithm,introducing a novel algorithm—Cooperative Coevolutionary Genetic Scheduling Algorithm (CCGSA) for solving the stochastic Job Shop Scheduling Problem (JSSP).In CCGSA,the number of sub-population depends on the number of working procedures.The interaction of all sub-populations is reflected by fitness function.The global optimization can be obtained with probability 1 with interaction of mutation and crossover operator in each sub-population.Based on stochastic sampling simulation and stochastic programming theory,an expected value model is presented to describe a stochastic job shop scheduling problem，in which the processing times are independent random variables following normal distribution.Initial computational results indicate the CCGSA performs effectively while comparing with basic GA.