第14卷第4期 智能系统学报 Vol.14 No.4 2019年7月 CAAI Transactions on Intelligent Systems Jul.2019 D0:10.11992/tis.201804016 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180704.1011.004html 改进猫群算法求解置换流水车间调度问题 裴小兵，于秀燕 (天津理工大学管理学院，天津300384) 摘要：标准猫群算法(CSO)在求解最小化最大完工时间的置换流水车间调度问题(PFSP)时收敛速度较慢，同 时，当问题规模变大时容易出现“维数灾难”。为加快寻优速度，同时避免“维数灾难”，提出了一种基于分布估 计算法的改进猫群算法(EDA-CSO)。以猫群算法为框架，嵌入分布估计算法，在搜寻模式下，利用概率矩阵挖 掘解序列中的优秀基因链组合区块，使用猫群算法中的跟踪模式更新猫的速度和位置，从而更新优秀解序列产 生子群体。最后，通过对Carlier和Reeves标准例题集的仿真测试和结果比较，验证了该算法良好的鲁棒性和 全局搜索能力。 关键词：置换流水车间调度；猫群算法：分布估计算法；搜寻模式：概率矩阵：组合区块；跟踪模式：优秀解序列 中图分类号：TP18文献标志码：A 文章编号：1673-4785(2019)04-0769-10 中文引用格式：裴小兵，于秀燕.改进猫群算法求解置换流水车间调度问题.智能系统学报，2019,14(4)：769-778， 英文引用格式：PEI Xiaobing,YU Xiuyan.Improved cat swarm optimization for permutation flow shop scheduling problemJ. CAAI transactions on intelligent systems,2019,14(4):769-778. Improved cat swarm optimization for permutation flow shop scheduling problem PEI Xiaobing,YU Xiuyan (School of Management,Tianjin University of Technology,Tianjin 300384,China) Abstract:The standard cat swarm optimization(CSO)has a slow convergence rate in solving the permutation flow shop scheduling problem(PFSP)to minimize the maximum completion time.Meanwhile,the "dimension disaster"is prone to occur when the scale of the problem is large.To speed up the optimization and avoid the"dimension disaster,"a CSO al- gorithm based on the estimation of distribution algorithms is proposed in this paper.Based on the cat swarm algorithm, the distribution estimation algorithm is embedded.In the search mode,the probability matrix is used to mine the excel- lent gene chain combination blocks in the solution sequence,and the tracking mode in the cat swarm algorithm is used to update the speed and position of the cat,thus updating the excellent solution sequence to generate a subpopulation.Fi- nally,through the simulation test and comparison result of Carlier and Reeves standard example set,the good robust- ness and global searching ability of the algorithm are verified. Keywords:permutation flow shop scheduling problem;cat swarm optimization;estimation of distribution algorithm; search mode;probability matrix;combination block;tracking mode;excellent solution sequence 置换流水车间调度问题(permutation flow shop al-.time hard,NP)。常见的PFSP求解方法可分为： scheduling problem,PFSP)是智能制造的核心问题 精确算法、启发式算法等。启发式算法能够快 之一，具有很重要的工程应用价值。研究表明， 速求得问题的可行解，但这些算法结构比较复 该问题属于NP难题(non-deterministic polynomi- 杂，求解最优解比较困难。 收稿日期：2018-04-13.网络出版日期：2018-07-04. 在有限的资源条件下，对PFSP的优化可有效 基金项目：国家创新方法工作专项项目(2017IM0I0800) 通信作者：于秀燕.E-mail:Yu xiuyanl026@163.com 增加企业收益，相关人士一直致力于研究和开发DOI: 10.11992/tis.201804016 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180704.1011.004.html 改进猫群算法求解置换流水车间调度问题 裴小兵，于秀燕 （天津理工大学 管理学院，天津 300384） 摘 要：标准猫群算法 (CSO) 在求解最小化最大完工时间的置换流水车间调度问题 (PFSP) 时收敛速度较慢，同 时，当问题规模变大时容易出现“维数灾难”。为加快寻优速度，同时避免“维数灾难”，提出了一种基于分布估 计算法的改进猫群算法 (EDA-CSO)。以猫群算法为框架，嵌入分布估计算法，在搜寻模式下，利用概率矩阵挖 掘解序列中的优秀基因链组合区块，使用猫群算法中的跟踪模式更新猫的速度和位置，从而更新优秀解序列产 生子群体。最后，通过对 Carlier 和 Reeves 标准例题集的仿真测试和结果比较，验证了该算法良好的鲁棒性和 全局搜索能力。 关键词：置换流水车间调度；猫群算法；分布估计算法；搜寻模式；概率矩阵；组合区块；跟踪模式；优秀解序列 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)04−0769−10 中文引用格式：裴小兵, 于秀燕. 改进猫群算法求解置换流水车间调度问题 [J]. 智能系统学报, 2019, 14(4): 769–778. 英文引用格式：PEI Xiaobing, YU Xiuyan. Improved cat swarm optimization for permutation flow shop scheduling problem[J]. CAAI transactions on intelligent systems, 2019, 14(4): 769–778. Improved cat swarm optimization for permutation flow shop scheduling problem PEI Xiaobing，YU Xiuyan (School of Management, Tianjin University of Technology, Tianjin 300384, China) Abstract: The standard cat swarm optimization (CSO) has a slow convergence rate in solving the permutation flow shop scheduling problem (PFSP) to minimize the maximum completion time. Meanwhile, the "dimension disaster" is prone to occur when the scale of the problem is large. To speed up the optimization and avoid the "dimension disaster," a CSO al￾gorithm based on the estimation of distribution algorithms is proposed in this paper. Based on the cat swarm algorithm, the distribution estimation algorithm is embedded. In the search mode, the probability matrix is used to mine the excel￾lent gene chain combination blocks in the solution sequence, and the tracking mode in the cat swarm algorithm is used to update the speed and position of the cat, thus updating the excellent solution sequence to generate a subpopulation. Fi￾nally, through the simulation test and comparison result of Carlier and Reeves standard example set, the good robust￾ness and global searching ability of the algorithm are verified. Keywords: permutation flow shop scheduling problem; cat swarm optimization; estimation of distribution algorithm; search mode; probability matrix; combination block; tracking mode; excellent solution sequence 置换流水车间调度问题 (permutation flow shop scheduling problem，PFSP) 是智能制造的核心问题 之一，具有很重要的工程应用价值。研究表明， 该问题属于 NP 难题[1] (non-deterministic polynomi￾al-time hard，NP)。常见的 PFSP 求解方法可分为： 精确算法、启发式算法[2] 等。启发式算法能够快 速求得问题的可行解，但这些算法结构比较复 杂，求解最优解比较困难。 在有限的资源条件下，对 PFSP 的优化可有效 增加企业收益，相关人士一直致力于研究和开发 收稿日期：2018−04−13. 网络出版日期：2018−07−04. 基金项目：国家创新方法工作专项项目 (2017IM010800). 通信作者：于秀燕. E-mail：Yu_xiuyan1026@163.com. 第 14 卷第 4 期 智 能 系 统 学 报 Vol.14 No.4 2019 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2019