第3期 裴小兵，等：应用改进区块遗传算法求解置换流水车间调度问题 ·549· 4结束语 advanced manufacturing technology,2016,85(9/10/11/12): 2459-2469. 本文针对置换流水车间调度问题，通过对p-ACGA [7]GANGULY S,MUKHERJEE S,BASU D.et al.A novel 改进，提出了p-IACGA。该算法初始化采用随机 strategy adaptive genetic algorithm with greedy local 机制和改进反向学习机制相结合的方式，提高了 search for the permutation flowshop scheduling 初始种群的多样性和质量。进一步考虑了工件与 problem[M]//Swarm,Evolutionary,and Memetic Comput- 所在解序列的位置关系，对节点信息素浓度进行 ing.Berlin,Heidelberg:Springer,2012:687-696. 了分析，通过位置信息素矩阵和相依信息素矩阵 [8]齐学梅，王宏涛，陈付龙，等.求解多目标PFSP的改进遗 挖掘区块加快了收敛速度，提高了最终解的质 传算法U.计算机工程与应用，2015,51(11)：242-247. 量。该算法保留了传统GA的交叉、变异等操作， QI Xuemei,WANG Hongtao,CHEN Fulong,et al.Im- 通过若干代的GA进化过程产生精英群体，不断 proved genetic algorithm for multi-objective of PFSP[J]. 更新区块，提高了人工染色体的质量和更新速 Computer engineering and applications,2015,51(11): 242-247 度。实验中，通过Taillard和Reeves实例进行测 [9]崔琪，吴秀丽，余建军.变邻域改进遗传算法求解混合流 试，以误差率作为比较指标，将结果与其他算法 水车间调度问题.计算机集成制造系统，2017,23(9)： 比较，验证了p-IACGA的有效性。 1917-1927 未来研究方向可以将所提出的p-IACGA应 CUI Qi,WU Xiuli,YU Jianjun.Improved genetic al- 用于其他组合优化问题，如旅行商问题、车辆路 gorithm variable neighborhood search for solving hybrid 径问题等。也可以通过改进该算法对PFSP的最 flow shop scheduling problem[J].Computer integrated 小化流程时间、最小化延迟时间等其他一个或多 manufacturing systems,2017,23(9):1917-1927 个目标进行研究。 [10]CHANG P C.HUANG W H.WU JL.et al.A block min- 参考文献： ing and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J].Interna- [1]周明，孙树栋遗传算法原理及应用M.北京：国防工业 tional journal of production economics,2013,141(1): 出版社，1999：6. 45-55. [2]夏小云，周育人.蚁群优化算法的理论研究进展.智能 [11]JIN Jian.A hybrid discrete biogeography-based optimiza- 系统学报，2016,11(127-36. tion for the permutation flow shop scheduling problem[J]. XIA Xiaoyun,ZHOU Yuren.Advances in theoretical re- International journal of production research,2016,54(16): search of ant colony optimization[J].CAAI transactions on 4805-4814 intelligent systems,2016,11(1):27-36 [12]DORIGO M.GAMBARDELLA L M.Ant colony sys- [3]李金忠，夏洁武，曾小荟，等.多目标模拟退火算法及其 tem:a cooperative learning approach to the traveling 应用研究进展[J】.计算机工程与科学，2013,35(8)： salesman problem[J].IEEE transactions on evolutionary 77-88. computation,1997,1(1):53-66. LI Jinzhong,XIA Jiewu,ZENG Xiaohui,et al.Survey of [13]陈慧芬.基于链结学习的子群体进化算法求解多目标 multi-objective simulated annealing algorithm and its ap- 调度问题[D].天津：天津理工大学，2017 plications[J].Computer engineering and science,2013, CHEN Huifen.Sub-population evolutionary algorithm 35(8):77-88 based on linkage learning for multi-objective scheduling [4]TAYEB F B S,BESSEDIK M,BENBOUZID M,et al.Re- problem[D].Tianjin:Tianjin University of Technology, search on permutation flow-shop scheduling problem 2017. based on improved genetic immune algorithm with vaccin- [14]裴小兵，陈慧芬，张百栈，等.改善式BVEDA求解多目 ated offspring[J].Procedia computer science,2017,112: 标调度问题[.山东大学学报（工学版），2017,47(4)： 427-436 25-30. [5]CHEN Rongchang,CHEN J,CHEN T S,et al.Synergy of PEI Xiaobing,CHEN Huifen,ZHANG Baizhan,et al.Im- genetic algorithm with extensive neighborhood search for proved bi-variables estimation of distribution algorithms the permutation flowshop scheduling problem[J].Mathem- for multi-objective permutation flow shop scheduling atical problems in engineering,2017,2017:3630869. problem[J].Journal of Shandong University (engineering [6]BESSEDIK M.TAYEB F B S.CHEURFI H,et al.An im- science,2017,47(4):25-30. munity-based hybrid genetic algorithms for permutation [15]裴小兵，赵衡.基于二元分布估计算法的置换流水车间 flowshop scheduling problems[J].International journal of 调度方法.中国机械工程，2017,28(22)：2752-27594 结束语 本文针对置换流水车间调度问题，通过对p-ACGA 改进，提出了 p-IACGA。该算法初始化采用随机 机制和改进反向学习机制相结合的方式，提高了 初始种群的多样性和质量。进一步考虑了工件与 所在解序列的位置关系，对节点信息素浓度进行 了分析，通过位置信息素矩阵和相依信息素矩阵 挖掘区块加快了收敛速度，提高了最终解的质 量。该算法保留了传统 GA 的交叉、变异等操作， 通过若干代的 GA 进化过程产生精英群体，不断 更新区块，提高了人工染色体的质量和更新速 度。实验中，通过 Taillard 和 Reeves 实例进行测 试，以误差率作为比较指标，将结果与其他算法 比较，验证了 p-IACGA 的有效性。 未来研究方向可以将所提出的 p-IACGA 应 用于其他组合优化问题，如旅行商问题、车辆路 径问题等。也可以通过改进该算法对 PFSP 的最 小化流程时间、最小化延迟时间等其他一个或多 个目标进行研究。 参考文献： 周明, 孙树栋. 遗传算法原理及应用[M]. 北京: 国防工业 出版社, 1999: 6. [1] 夏小云, 周育人. 蚁群优化算法的理论研究进展[J]. 智能 系统学报, 2016, 11(1): 27–36. XIA Xiaoyun, ZHOU Yuren. Advances in theoretical re￾search of ant colony optimization[J]. CAAI transactions on intelligent systems, 2016, 11(1): 27–36. [2] 李金忠, 夏洁武, 曾小荟, 等. 多目标模拟退火算法及其 应用研究进展[J]. 计算机工程与科学, 2013, 35(8): 77–88. LI Jinzhong, XIA Jiewu, ZENG Xiaohui, et al. Survey of multi-objective simulated annealing algorithm and its ap￾plications[J]. Computer engineering and science, 2013, 35(8): 77–88. [3] TAYEB F B S, BESSEDIK M, BENBOUZID M, et al. Re￾search on permutation flow-shop scheduling problem based on improved genetic immune algorithm with vaccin￾ated offspring[J]. Procedia computer science, 2017, 112: 427–436. [4] CHEN Rongchang, CHEN J, CHEN T S, et al. Synergy of genetic algorithm with extensive neighborhood search for the permutation flowshop scheduling problem[J]. Mathem￾atical problems in engineering, 2017, 2017: 3630869. [5] BESSEDIK M, TAYEB F B S, CHEURFI H, et al. An im￾munity-based hybrid genetic algorithms for permutation flowshop scheduling problems[J]. International journal of [6] advanced manufacturing technology, 2016, 85(9/10/11/12): 2459–2469. GANGULY S, MUKHERJEE S, BASU D, et al. A novel strategy adaptive genetic algorithm with greedy local search for the permutation flowshop scheduling problem[M]//Swarm, Evolutionary, and Memetic Comput￾ing. Berlin, Heidelberg: Springer, 2012: 687–696. [7] 齐学梅, 王宏涛, 陈付龙, 等. 求解多目标 PFSP 的改进遗 传算法[J]. 计算机工程与应用, 2015, 51(11): 242–247. QI Xuemei, WANG Hongtao, CHEN Fulong, et al. Im￾proved genetic algorithm for multi-objective of PFSP[J]. Computer engineering and applications, 2015, 51(11): 242–247. [8] 崔琪, 吴秀丽, 余建军. 变邻域改进遗传算法求解混合流 水车间调度问题[J]. 计算机集成制造系统, 2017, 23(9): 1917–1927. CUI Qi, WU Xiuli, YU Jianjun. Improved genetic al￾gorithm variable neighborhood search for solving hybrid flow shop scheduling problem[J]. Computer integrated manufacturing systems, 2017, 23(9): 1917–1927. [9] CHANG P C, HUANG W H, WU J L, et al. A block min￾ing and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J]. Interna￾tional journal of production economics, 2013, 141(1): 45–55. [10] JIN Jian. A hybrid discrete biogeography-based optimiza￾tion for the permutation flow shop scheduling problem[J]. International journal of production research, 2016, 54(16): 4805–4814. [11] DORIGO M, GAMBARDELLA L M. Ant colony sys￾tem: a cooperative learning approach to the traveling salesman problem[J]. IEEE transactions on evolutionary computation, 1997, 1(1): 53–66. [12] 陈慧芬. 基于链结学习的子群体进化算法求解多目标 调度问题[D]. 天津: 天津理工大学, 2017. CHEN Huifen. Sub-population evolutionary algorithm based on linkage learning for multi-objective scheduling problem[D]. Tianjin: Tianjin University of Technology, 2017. [13] 裴小兵, 陈慧芬, 张百栈, 等. 改善式 BVEDA 求解多目 标调度问题[J]. 山东大学学报(工学版), 2017, 47(4): 25–30. PEI Xiaobing, CHEN Huifen, ZHANG Baizhan, et al. Im￾proved bi-variables estimation of distribution algorithms for multi-objective permutation flow shop scheduling problem[J]. Journal of Shandong University (engineering science), 2017, 47(4): 25–30. [14] 裴小兵, 赵衡. 基于二元分布估计算法的置换流水车间 调度方法[J]. 中国机械工程, 2017, 28(22): 2752–2759. [15] 第 3 期 裴小兵，等：应用改进区块遗传算法求解置换流水车间调度问题 ·549·