求解混合流水生产线调度问题的变量相关EDA算法AnEDAalgorithm.PDF

求解混合流水生产线调度问题的变量相关 EDA 算法1 1 1,2 1 1 刘 昶 ，李 冬 ，彭 慧 ，史海波 (1.中国科学院 沈阳自动化研究所，辽宁 沈阳 110016； 2.中国科学院大学，北京 100049) 摘要：针对混合流水车间调度问题（Hybrid flow‐shop scheduling problem, HFSP）和分布估计算 法（Estimation of distribution algorithm, EDA）的特点，提出了将变量按工序分组，通过组内概率约束， 组间概率耦合的方式建立 HFSP 变量间概率关系的新方法。对分布估计算法中的紧致遗传算法 （Compact Genetic Algorithm ，cGA)的种群产生和概率更新机制进行了改进以解决混合 HFSP 等复杂 问题。最后通过仿真实验、与其它算法比较以及在大规模生产实际问题中的应用，验证了该算法的 有效性和鲁棒性。  关键词：分布估计算法；紧致遗传算法；混合流水车间；概率模型    中图分类号： TP315 文献标识码：A   An EDA algorithm with correlated variables for solving hybrid flow-shop scheduling problem LIU Chang 1 ，LI Dong1,2，PENG Hui 1 ，SHI Hai-bo1 (1.Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016，China; 2. University of Chinese Academy of Sciences, Beijing 100049 , China) Abstract: According to the characteristic of the hybrid flow-shop scheduling problem (HFSP) and the estimation of distribution algorithm, a new method of building probabilistic relationships between variables has been proposed. In the new method, grouping the variable by process, and then building the variable probabilistic relationship in a high level through the probabilistic constraints in the same group and the probabilistic coupling in different groups. In addition that, the mechanism of population generation and probability updating has been improved in the standard compact genetic algorithm （a kind of EDA ）which accelerate the convergence rate of algorithm. At last, the effectiveness and robustness of the algorithm has been proved by simulation, comparing with other algorithms and the verification