Application Of A Quantum Evolution Algorithm To Stochastic Job Shop Scheduling Problems

Quantum evolutionary algorithm is a type of evolutionary algorithm based on the principle of quantum computation.It was developed in the continuous fusion of quantum theory and evolutionary algorithm,which has the advantages of small population size,fast convergence rate and strong global search ability.The most obvious feature of the stochastic job shop scheduling problem is that the processing time for processing step on machine is obtained according to certain rule.This makes that the stochastic job shop scheduling problem have great randomness and complexity,which brings great difficulties to the solution of the problem.Many scholars apply quantum evolutionary algorithm to solve the stochastic job shop scheduling problem and good results have obtained.However,the local optimization,large amount of computation and high complexity always appear during the solution process,which needs further improvement.The quantum evolutionary algorithm takes advantage of the coherence,superposition,and entanglement of quantum states and possesses quantum parallelism.The quantum evolutionary algorithm uses quantum bits to encode quantum chromosomes and uses quantum gates as update operators for evolutionary search.At the same time,the quantum evolutionary algorithm also uses equations and population dynamics which exist in evolutionary algorithms.There are various forms of quantum evolutionary algorithms now,such as binary observation and mixed quantum evolutionary algorithms.These different quantum evolutionary algorithms have been widely used in combinatorial optimization,signal processing,numerical optimization and other fields.This thesis mainly presents a class of quantum evolutionary algorithms for stochastic job shop scheduling problem.The algorithm uses the dynamic rotation gate and the H? operation in the quantum update operation.Before determine whether to conduct quantum crossover operator by the means of adaptive quantum crossover probability,we need to calculate the quantum crossover probability of each generation.At the same time,the algorithm adopts two strategies of population size adjustment in co-evolution:competitive evolutionary strategy and cooperative evolutionary strategy,which can provide sufficient motivation for population evolution.Finally,in order to avoid the algorithm getting into local optimum,the algorithm uses catastrophic operation.Once the algorithm is found to be in local optimum,the algorithm will adopt catastrophic operation,so that it can jump out of local optimal continuous search solution space.Finally,an experimental analysis is carried out to verify the effectiveness of the algorithm in solving stochastic job shop scheduling problem.The experimental results show that the algorithm in this thesis performs well in the small and medium-scale stochastic job shop scheduling problem,but it doesn't behave well in solving the large-scale problem,the algorithm proposed in this thesis needs further improvement.