第14卷第3期 智能系统学报 Vol.14 No.3 2019年5月 CAAI Transactions on Intelligent Systems May 2019 D0:10.11992/tis.201801041 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20180503.1008.003.html 应用改进区块遗传算法求解置换流水车间调度问题 裴小兵，张春花 (天津理工大学管理学院，天津300384) 摘要：针对最小化最大完工时间的置换流水车间调度问题，提出一种将遗传算法与蚊群算法相结合的改进区 块遗传算法。算法利用随机机制和改进反向学习机制相结合的方式产生初始解，以兼顾初始种群的多样性和 质量。通过若干代简单遗传算法操作产生精英群体，借鉴蚁群算法中利用蚂蚁信息度浓度统计路径和节点信 息的思想，对精英群体所携带信息进行统计分析并建立位置信息素矩阵和相依信息素矩阵，根据两矩阵挖掘区 块并将区块与非区块组合形成染色体。将染色体进行切段与重组，以提高染色体的质量，使用二元竞赛法保留 适应度较高的染色体。算法通过Reeves实例和Taillard实例进行测试，并将结果与其他算法进行比较，验证了 该算法的有效性。 关键词：生产调度：组合优化：遗传算法：蚁群优化算法：构建区块：人工染色体 中图分类号：TP18文献标志码：A文章编号：1673-4785(2019)03-0541-10 中文引用格式：裴小兵，张春花.应用改进区块遗传算法求解置换流水车间调度问题[.智能系统学报，2019,14(3)： 541-550. 英文引用格式：PEI Xiaobing,.ZHANG Chunhua..An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems[J].CAAI transactions on intelligent systems,2019,14(3):541-550. An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems PEI Xiaobing,ZHANG Chunhua (School of Management,Tianjin University of Technology,Tianjin 300384,China) Abstract:Targeting the permutation flow-shop scheduling problem that minimizes maximum completion times,an im- proved block genetic algorithm combined with an ant colony algorithm is proposed.The algorithm uses a random mech- anism and the improved opposition-based learning mechanism to generate the initial solution.It takes into account the diversity and quality of the initial population.Elite populations are generated through several generations of simple ge- netic algorithm operations.Based on the idea of using ant information density concentration's statistical path and node information in the ant colony algorithm,the information carried by elite groups was counted.Position pheromone and dependent pheromone matrices were established.Mining blocks according to two matrices were developed and blocks were combined with non-blocks to form artificial chromosomes.Chromosomes were cut and recombined to increase chromosome quality.The binary race method was used to retain chromosomes with higher fitness.The algorithm was tested through the Reeves and Taillard instances,and the results were compared with other algorithms to verify effect- iveness of the algorithm. Keywords:production scheduling;combinatorial optimization;genetic algorithms;ant colony optimization;building block;artificial chromosome 收稿日期：2018-01-23.网络出版日期：2018-05-03， 置换流水车间调度问题(permutation flow-shop 基金项目：国家创新方法工作专项项目(2017IM060200):天津 市哲学社会科学规划项目(TYY17-013). scheduling problem,PFSP)是广泛受到研究的一种 通信作者：张春花.E-mail:Zhang_chunhual203@126.com. 组合优化问题，属于NP-hard问题。PFSP的搜索DOI: 10.11992/tis.201801041 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20180503.1008.003.html 应用改进区块遗传算法求解置换流水车间调度问题 裴小兵，张春花 （天津理工大学 管理学院，天津 300384） 摘 要：针对最小化最大完工时间的置换流水车间调度问题，提出一种将遗传算法与蚁群算法相结合的改进区 块遗传算法。算法利用随机机制和改进反向学习机制相结合的方式产生初始解，以兼顾初始种群的多样性和 质量。通过若干代简单遗传算法操作产生精英群体，借鉴蚁群算法中利用蚂蚁信息度浓度统计路径和节点信 息的思想，对精英群体所携带信息进行统计分析并建立位置信息素矩阵和相依信息素矩阵，根据两矩阵挖掘区 块并将区块与非区块组合形成染色体。将染色体进行切段与重组，以提高染色体的质量，使用二元竞赛法保留 适应度较高的染色体。算法通过 Reeves 实例和 Taillard 实例进行测试，并将结果与其他算法进行比较，验证了 该算法的有效性。 关键词：生产调度；组合优化；遗传算法；蚁群优化算法；构建区块；人工染色体 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)03−0541−10 中文引用格式：裴小兵, 张春花. 应用改进区块遗传算法求解置换流水车间调度问题[J]. 智能系统学报, 2019, 14(3): 541–550. 英文引用格式：PEI Xiaobing, ZHANG Chunhua. An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems[J]. CAAI transactions on intelligent systems, 2019, 14(3): 541–550. An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems PEI Xiaobing，ZHANG Chunhua (School of Management, Tianjin University of Technology, Tianjin 300384, China) Abstract: Targeting the permutation flow-shop scheduling problem that minimizes maximum completion times, an im￾proved block genetic algorithm combined with an ant colony algorithm is proposed. The algorithm uses a random mech￾anism and the improved opposition-based learning mechanism to generate the initial solution. It takes into account the diversity and quality of the initial population. Elite populations are generated through several generations of simple ge￾netic algorithm operations. Based on the idea of using ant information density concentration’s statistical path and node information in the ant colony algorithm, the information carried by elite groups was counted. Position pheromone and dependent pheromone matrices were established. Mining blocks according to two matrices were developed and blocks were combined with non-blocks to form artificial chromosomes. Chromosomes were cut and recombined to increase chromosome quality. The binary race method was used to retain chromosomes with higher fitness. The algorithm was tested through the Reeves and Taillard instances, and the results were compared with other algorithms to verify effect￾iveness of the algorithm. Keywords: production scheduling; combinatorial optimization; genetic algorithms; ant colony optimization; building block; artificial chromosome 置换流水车间调度问题 (permutation flow-shop scheduling problem, PFSP) 是广泛受到研究的一种 组合优化问题，属于 NP−hard 问题。PFSP 的搜索 收稿日期：2018−01−23. 网络出版日期：2018−05−03. 基金项目：国家创新方法工作专项项目 (2017IM060200)；天津 市哲学社会科学规划项目 (TJYY17-013). 通信作者：张春花. E-mail: Zhang_chunhua1203@126.com. 第 14 卷第 3 期 智 能 系 统 学 报 Vol.14 No.3 2019 年 5 月 CAAI Transactions on Intelligent Systems May 2019