Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (8): 2249-2257.DOI: 10.11772/j.issn.1001-9081.2020101675

Special Issue: 先进计算

• Advanced computing • Previous Articles     Next Articles

Hybrid particle swarm optimization with multi-region sampling strategy to solve multi-objective flexible job-shop scheduling problem

ZHANG Wenqiang1,2, XING Zheng2, YANG Weidong1,2   

  1. 1. Key Laboratory of Grain Information Processing and Control, Ministry of Education(Henan University of Technology), Zhengzhou Henan 450001, China;
    2. College of Information Science and Engineering, Henan University of Technology, Zhengzhou Henan 450001, China
  • Received:2020-10-29 Revised:2021-01-25 Online:2021-08-10 Published:2021-02-05
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61772173), the Program for Supporting Science and Technology Innovation Talents in Colleges and Universities of Henan Province (19HASTIT027), the Science and Technology Research Project of Henan Province (202102210131).

基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题

张闻强1,2, 邢征2, 杨卫东1,2   

  1. 1. 粮食信息处理与控制教育部重点实验室(河南工业大学), 郑州 450001;
    2. 河南工业大学 信息科学与工程学院, 郑州 450001
  • 通讯作者: 张闻强
  • 作者简介:张闻强(1975-),男,河南新乡人,副教授,博士,CCF会员,主要研究方向:进化计算、多目标优化;邢征(1995-),男,河南安阳人,硕士研究生,CCF会员,主要研究方向:进化计算、多目标优化;杨卫东(1977-),男,内蒙古卓资人,教授,博士,CCF高级会员,主要研究方向:车联网信息安全、粮食光电信息检测。
  • 基金资助:
    国家自然科学基金资助项目(61772173);河南省高校科技创新人才支持计划项目(19HASTIT027);河南省科技攻关项目(202102210131)。

Abstract: Flexible Job-shop Scheduling Problem (FJSP) is a widely applied combinatorial optimization problem. Aiming at the problems of multi-objective FJSP that the solution process is complex and the algorithm is easy to fall into the local optimum, a Hybrid Particle Swarm Optimization algorithm with Multi-Region Sampling strategy (HPSO-MRS) was proposed to optimize both the makespan and total machine delay time. The multi-region sampling strategy was able to reorganize the positions of the Pareto frontiers that the particles belonging to, and guide the corresponding moving directions for the particles in multiple regions of the Pareto frontiers after sampling. Thus, the convergence ability of particles in multiple directions was adjusted, and the ability of uniform distribution was improved to a certain extent. In addition, in the encoding and decoding aspect, the decoding strategy with interpolation mechanism was used to eliminate the potential local left shift; in the particle updating aspect, the particle update method of traditional Particle Swarm Optimization (PSO) algorithm was combined with the crossover and mutation operators of Genetic Algorithm (GA), which improved the diversity of search process and avoid the algorithm from falling into the local optimum. The proposed algorithm was tested on benchmark problems Mk01-Mk10 and compared with Hybrid Particle Swarm Optimization algorithm (HPSO), Non-dominated Sorting Genetic Algorithm Ⅱ (NSGA-Ⅱ), Strength Pareto Evolutionary Algorithm 2 (SPEA2) and Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) on algorithm effectiveness and operation efficiency. Experimental results of significance analysis showed that, HPSO-MRS was significantly better than the comparison algorithms on the convergence evaluation indexes Hyper Volume (HV) and Inverted Generational Distance (IGD) in 85% and 77.5% of the control groups, respectively. In 35% of the control groups, the distribution index Spacing of the algorithm was significantly better than those of the comparison algorithms. And there was no situation that the proposed algorithm was significantly worse than the comparison algorithms on the three indexes. It can be seen that, compared with the others, the proposed algorithm has better convergence and distribution performance.

Key words: Particle Swarm Optimization (PSO), Multi-Region Sampling (MRS), Multi-objective Optimization Problem (MOP), Flexible Job-shop Scheduling Problem (FJSP), Genetic Algorithm (GA)

摘要: 柔性作业车间调度问题(FJSP)是一类应用广泛的组合优化问题。针对多目标FJSP求解过程复杂、算法易陷入局部最优的问题,提出了一种基于多区域采样策略的混合粒子群优化算法(HPSO-MRS),以同时优化最大完工时间和总机器延迟时间这两个目标。多区域采样策略能够区分粒子所在Pareto前沿面的位置,根据不同区域进行采样重组,并为采样后位于Pareto前沿面多个区域的粒子规划相应的运动方向,从而有针对性地调整粒子在多个方向上的收敛能力,并带来一定程度的均匀分布能力的提升。此外,编解码方面使用带插空机制的解码策略来消除可能存在的局部左移;粒子更新方面将传统粒子群优化(PSO)算法的粒子更新方式与遗传算法(GA)的交叉变异算子相结合,提升了算法搜索过程的多样性并避免算法陷入局部最优。把所提算法在Benchmark问题Mk01~Mk10上进行测试,与传统的HPSO、NSGA-Ⅱ、基于适应度分配策略的多目标进化算法(SPEA2)和基于分解的多目标进化算法(MOEA/D)进行算法效力和运行效率对比。显著性分析的实验结果表明,HPSO-MRS在收敛性评价指标HV和IGD上分别在85%和77.5%的对照组中显著优于对比算法,而该算法在35%的对照组中的分布性指标Spacing显著优于对比算法,且均不存在所提算法显著差于对比算法的情况。可见相较于对比算法,所提出的算法具备较好的收敛与分布性能。

关键词: 粒子群优化, 多区域采样, 多目标优化问题, 柔性作业车间调度问题, 遗传算法

CLC Number: