A Quantum Genetic Scheduling Algorithm for stochastic flow shop scheduling problem with two types of intermediate storage

摘要

In this paper,a Quantum Genetic Scheduling Algorithm (QGSA) was proposed for solving two special types of stochastic flow shop scheduling problem (Zero Wait and Finite Intermediate Storage).In this algorithm,the Q-bit based representation in discrete 0-1 hyperspace was employed,which was then converted into decimal scheduling code and quantum gate was used to update the current generation,meanwhile catastrophe operator is added to avoid premature.Based on stochastic programming and stochastic simulation theory,two stochastic expected value models were presented,in which uncertain processing time was described by stochastic variables with independent normal distributions.Simulation results demonstrated the feasibility and effectiveness of the proposed algorithm.