文献类型：期刊文献

英文题名：A novel parallel quantum genetic algorithm for stochastic job shop scheduling

作者：Gu, Jinwei[1];Gu, Xingsheng[1];Gu, Manzhan[2]

机构：[1]E China Univ Sci & Technol, Res Inst Automat, Shanghai 200237, Peoples R China;[2]E China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China

年份：2009

卷号：355

期号：1

起止页码：63

外文期刊名：JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS

收录：;WOS:【SCI-EXPANDED(收录号:WOS:000265801800007)】；

基金：This work is supported by National Natural Science Foundation of China (Grant No. 60774078), Shanghai Commission of Science and Technology (Grant No. 08JC1408200) and Shanghai Leading Academic Discipline Project (Project No. B504).

语种：英文

外文关键词：Stochastic; Job shop scheduling; Quantum evolution; Parallel algorithm

摘要：In this paper, a Novel Parallel Quantum Genetic Algorithm (NPQGA) is proposed for the stochastic job Shop Scheduling Problem with the objective of minimizing the expected value of makespan, where the processing times are subjected to independent normal distributions. Based on the parallel evolutionary idea and some concepts of quantum theory, we Simulate a model of parallel quantum computation. In this frame, there are some demes (sub-populations) and some universes (groups of populations), which are structured in super star-shaped topologies. A new migration scheme based on penetration theory is developed to control migration rate and direction adaptively between demes, and a novel quantum crossover strategy is devised among universes. The quantum evolution is executed in every deme by applying some improvement operators (the coding mechanism aiming at job shop, the new quantum rotation angle and the catastrophe operator). Experiment results show NPQGA's effectiveness and applicability. (c) 2009 Elsevier Inc. All rights reserved.