改进离散麻雀搜索算法求解柔性作业车间调度问题  

Improved discrete sparrow search algorithm for flexible job-shop scheduling problem

作　　者：李峥峰 丁其聪 张东方 张国辉 LI Zhengfeng;DING Qicong;ZHANG Dongfang;ZHANG Guohui(School of Mechatronics Engineering,Zhongyuan University of Technology,Zhengzhou 450007,China;School of Management Engineering,Zhengzhou University of Aeronautics,Zhengzhou 450015,China)

机构地区：[1]中原工学院机电学院,郑州450007 [2]郑州航空工业管理学院管理工程学院,郑州450015

出　　处：《现代制造工程》2023年第9期18-27,共10页Modern Manufacturing Engineering

基　　金：国家自然科学基金联合基金项目(U1904167);河南省科技攻关项目(182102210515);教育部人文社会科学规划基金项目(18YJAZH125);河南省高校科技创新团队项目(21IRTSTHN018);河南省高等学校重点科研计划项目(19A460034)。

摘　　要：针对最小化最大完工时间的柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP),提出了一种改进离散麻雀搜索算法(Improved Discrete Sparrow Search Algorithm,IDSSA)。首先,采用了两段式编码方式,针对两段编码分别设计了有效的编码转化方式,实现了麻雀搜索算法(Sparrow Search Algorithm,SSA)连续搜索空间与FJSP离散决策空间之间的映射。其次,设计了一种随机与组合启发规则相结合的初始化方法,在保证了麻雀初始种群分散广度的同时提高了麻雀个体的质量,加快麻雀搜索算法的收敛速度。再次,融合一种基于关键路径的变邻域搜索策略,对发现者进行深度发掘,提高种群引领者的质量。此外,为了维持SSA种群多样性,设计了自适应柯西高斯变异策略,提升算法全局搜索能力和跳出局部极值的能力。最后,使用Kacem和Brandimarte系列12个基准算例与多种算法进行仿真实验,实验结果证明了IDSSA的有效性和求解FJSP的优越性。An Improved Discrete Sparrow Search Algorithm(IDSSA)was proposed for the Flexible Job Shop Scheduling Problem(FJSP)with minimum makespan.Firstly,a two-stage encoding method was adopted,and an effective encoding conversion method was designed for the two-stage encoding.The mapping between Sparrow Search Algorithm(SSA)continuous search space and FJSP discrete decision space was realized.Secondly,an initialization method combining random and combinatorial heuristic rules was designed to ensure the dispersion of sparrow initial population,improve the quality of sparrow individuals,and accelerate the convergence speed of sparrow search algorithm.Thirdly,a variable neighborhood search strategy based on critical path was integrated to deeply explore the discoverers and improve the quality of the population leaders.In addition,in order to maintain the diversity of SSA population,an adaptive Causi-Gaussian mutation strategy was designed to improve the global search ability and the ability to get rid of local extremum of the algorithm.At last,12 test examples of Kacem and Brandimarte series and various algorithms were used for simulation experiments.The experimental results prove the effectiveness of IDSSA and the superiority of solving FJSP.

关 键 词：柔性作业车间调度 麻雀搜索算法 变邻域搜索策略 柯西高斯变异 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置] TP301[自动化与计算机技术—控制科学与工程]