一种求解置换流水车间调度问题的多策略粒子群优化

详细信息    查看全文 | 推荐本文 |

英文篇名：Multi-strategy particle swarm optimization for solving permutation flow-shop scheduling problem 作者：汤可宗 ; 詹棠森 ; 李佐勇 ; 舒云 英文作者：Tang Kezong;Zhan Tangsen;Li Zuoyong;Shu Yun;School of Information Engineering,Jingdezhen Ceramic Institute;Industrial Robot Application of Fujian University Engineering Research Center,Minjiang University; 关键词：粒子群优化 ; 置换流水车间调度问题 ; 多策略粒子群优化方法 ; 多样性 英文关键词：particle swarm optimization;;permutation flow-shop scheduling problem;;multi-strategy particle swarm optimization method;;diversity 中文刊名：NJLG 英文刊名：Journal of Nanjing University of Science and Technology 机构：景德镇陶瓷大学信息工程学院;工业机器人应用福建省高校工程研究中心闽江学院; 出版日期：2019-03-13 13:23 出版单位：南京理工大学学报 年：2019 期：v.43;No.224 基金：国家自然科学基金(61662037;71763013);; 江西省教育厅科技项目(GJJ170764);; 江西省杰出青年人才计划资助(20171bc b23069);; 福建省高校青年自然基金重点项目(JZ160467);; 工业机器人应用福建省高校工程研究中心开放基金资助(MJUKF-IRA201808) 语种：中文; 页：NJLG201901007 页数：7 CN：01 ISSN：32-1397/N 分类号：52-57+66

摘要

为了提高粒子群优化方法解决组合优化问题的效率,该文基于多种组合优化策略,提出一种求解置换流水车间调度问题的多策略粒子群优化方法。该方法基于万有引力值划分的子区间,按信息熵方式度量粒子群体的多样性。同时在蚂蚁路径选择的基础上,综合考虑粒子间距离和惯性质量择优选出全局最优粒子。此外,一种新颖的集合变异方式被用于引导粒子群体跳出局部最优解区域,增强粒子群体的全局搜索能力。测试问题的仿真结果表明,所提出方法能加快最优解的收敛速度和搜索性能,可有效应用于置换流水车间调度问题的求解。
        In order to improve the search performance of combinatorial optimization problem for particle swarm optimization,a multi-strategy particle swarm optimization method is proposed for solving permutation flow-shop scheduling problems based on various combinatorial optimization strategies. The proposed method uses information entropy to measure the population diversity of particle group through the sub interval of gravitational value partition. At the same time,the global optimal particle selection is selected by ant routing selection strategy and considering the distance between particles and the mass of inertia. In addition,a novel mutation is designed to guide particle swarm to jump out of the local optimal solution area and enhance the global search ability of particle swarm. The simulation results of test problems show that the multi-strategy particle swarm optimization can effectively accelerate the search performance and convergence speed of the optimal solution,and it can be effectively applied to solve the permutation flow-shop scheduling problem.

引文

[1] 王凌,邓瑾,王圣尧. 分布式车间调度优化算法研究综述[J]. 控制与决策,2016,31(1):1-11.Wang Ling,Deng Jin,Wang Shengyao. Survey on optimization algorithms for distributed shop scheduling[J]. Control and Decision,2016,31(1):1-11.
    [2] 赵莉. 基于改进量子粒子群算法的云计算资源调度[J]. 南京理工大学学报,2016,40(2):223-228.Zhao Li. Cloud computing resource scheduling based on improved quantum particle swarm optimization algorithm[J]. Journal of Nanjing University of Science and Technology,2016,40(2):223-228.
    [3] Kennedy J,Eberhart R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks. Perth,Australia:IEEE Press,1995:1942-1948.
    [4] 张静,王万良,徐新黎,等. 混合粒子群算法求解多目标柔性作业车间调调度问题[J]. 控制理论与应用,2012,29(6):715-722.Zhang Jing,Wang Wanliang Xu Xinli,et al. Hybrid particle-swarm optimization for multi-objective flexible job-shop scheduling problem[J]. Control Theory & Applications,2012,29(6):715-722.
    [5] 戴月明,王明慧,王春,等. 骨干双粒子群算法求解柔性作业车间调度问题[J]. 系统仿真学报,2017,29(6):1268-1276.Dai Yueming,Wang Minghui,Wang Chun,et al. Double bare bones particle swarm algorithm for solving flexible job-shop scheduling problem[J]. Journal of System Simulation,2017,29(6):1268-1276.
    [6] Li D,Deng N. Solving permutation flow shop scheduling problem with a cooperative multi-swarm PSO algorithm[J]. Journal of Information & Computational Science,2012,9(4):977-987.
    [7] Le Z,Wang Jinnan. A PSO-based hybrid metaheuristic for permutation flowshop scheduling problems[J]. The Scientific World Journal,2014,36(6):1-8.
    [8] Bewoor L,Prakash V C,Sapkal S. Evolutionary hybrid particle swarm optimization algorithm for solving NP-hard No-wait flow shop scheduling problems[J]. Algorithms,2017,10(4):121-137.
    [9] 张其亮,陈永生,韩斌. 改进的粒子群算法求解置换流水车间调度问题[J]. 计算机应用,2012,32(4):1022-1024.Zhang Qiliang,Cheng Yongsheng,Han Bing. Improved particle swarm optimization for permutation flowshop scheduling problem[J]. Journal of Computation Applications,2012,32(4):1022-1024.
    [10] 刘勇,马良. 置换流水车间调度问题的中心引力优化算法求解[J]. 运筹与管理,2017,26(9):46-51.Liu Yong,Ma Liang. Solving permutation flow-shop scheduling problem by central force optimization algorithm[J]. Operations Research and Management Science,2017,26(9):46-51.
    [11] 顾文斌,唐敦兵,郑堃,等. 基于激素调节机制改进型自适应粒子群算法在置换流水车间调度中的应用研究[J]. 机械工程学报,2012,48(14):177-182.Gu Wenbin,Tang Dunbing,Zheng Kun,et al. Research on permutation flow-shop scheduling problem based on improved adaptive particle swarm optimization algorithm with hormone modulation mechanism[J]. Journal of Mechanical Engineering,2012,48(14):177-182.
    [12] Liu Bo,Wang Ling,Jin Yihui. An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers[J]. Computers & Operations Research,2008,35(9):2791-2806.