改进松鼠搜索算法求解分布式节能柔性调度

曾亮 石俊洋 王珊珊 李维刚

摘 要：为了优化同时考虑最大完工时间和机器能耗的双目标分布式柔性作業车间调度问题，提出了一种改进的多目标松鼠搜索算法。引入了基于升序排列规则的转换机制，实现了松鼠位置向量与调度解之间的转换，并针对机器空闲时间设计了从半主动到主动的解码策略。针对不同优化目标设计了三种种群初始化策略。同时提出了动态捕食者策略来更好地协调算法的全局探索和局部开发能力。设计了四种领域搜索策略用于增加种群多样。20个实例上的实验结果验证了改进后的算法求得解的质量和多样性更好，从而证明了其可有效求解分布式节能柔性调度问题。

关键词：松鼠搜索算法； 分布式柔性车间调度； 节能调度； 多目标优化； 优化算法

中图分类号：TP18;TH165   文献标志码：A

文章编号：1001-3695（2024）03-030-0848-06

doi：10.19734/j.issn.1001-3695.2023.07.0334

Improved squirrel search algorithm to solve distributed

energy-efficient flexible scheduling

Zeng Liang1，2， Shi Junyang1，2， Wang Shanshan1，2， Li Weigang3

（1.School of Electrical & Electronic Engineering， Hubei University of Technology， Wuhan 430068， China; 2.Hubei Key Laboratory for High-efficiency Utilization of Solar Energy & Operation Control of Energy Storage System， Wuhan 430068， China; 3.School of Information Science & Engineering， Wuhan University of Science & Technology， Wuhan 430081， China）

Abstract：To optimize the distributed flexible Job-Shop scheduling problem considering both the makespan and machine energy consumption， this paper proposed an improved multi-objective squirrel search algorithm. The algorithm introduced a conversion mechanism based on ranked order value to achieve the conversion between squirrel position vectors and scheduling solutions， and designed decoding strategy from semi-active to active for machine idle time. Additionally， it devised three population initialization strategies based on different optimization objectives. The proposed dynamic predator strategy could better coordinate the algorithms global exploration and local exploitation capabilities. Finally， the algorithm used four local searches to increase population diversity. Experimental results on 20 instances show that the improved algorithm achieves better quality and diversity of solutions， proving that it can effectively solve the distributed energy-efficient flexible scheduling problem.

Key words：squirrel search algorithm; distributed flexible Job-Shop scheduling; energy-efficient scheduling; multi-objective optimization; optimization algorithm

0 引言

柔性作业车间调度问题（flexible Job-Shop scheduling problem，FJSP）是经典作业车间调度中更接近真实加工环境的扩展，它通过对作业车间进行调度优化，能有效降低加工时间、生产成本、加工能耗等［1］。如今随着市场需求的多样化以及加工产品的复杂化，大量的单工厂生产模式正在向分布式多工厂柔性生产模式转换［2］。分布式作业车间调度（distributed flexible Job-Shop scheduling problem，DFJSP）通过研究每个作业车间中各个工序的加工顺序来优化调度目标，可以有效利用每个车间的资源［3］。DFJSP相比于FJSP，其增加了工厂的选择，具有多车间任务关联耦合、多车间性能差异性和空间分散性的特点，因此求解也更加困难［4］，解决DFJSP已经成为制造业优化的一个热门话题。同时，随着经济的发展、人类生存环境的恶化以及资源的过度消耗，使得发展与资源环境的矛盾日趋尖锐。节能减排是世界可持续发展的必然选择，也是应对资源稀缺与环境承载能力有限的挑战的必然选择。因此，在调度的过程中同时考虑节能指标也应逐渐成为研究的重点。

2010年，文献［5］首次定义DFJSP并且使用改进的遗传算法求解調度问题。随后，又有学者使用其他的元启发式算法求解DFJSP，比如Zhao等人［6］提出了一种模因离散差分进化算法，并引入了一种新的离散突变策略来优化最小制造周期；李家磊等人［7］提出一种双种群混合遗传算法，通过种群间的协作和有效局部搜索优化DFJSP的最大完工时间；Li等人［8］使用灰狼算法优化DFJSP的完工时间，还提出了一种针对关键工厂的本地搜索策略。以上这些研究大多只针对完工时间进行优化，并且存在大量盲目的交换和变异操作，局部搜索也存在效率低的问题。

制造企业在生产的过程中不仅要考虑降低时间成本，还要设法降低污染、节能减排。因此，加工时间不再是DFJSP中考虑的单一指标。目前已经有许多学者针对DFJSP提出了多目标元启发算法。例如，Sang等人［9］对NSGA-Ⅲ进行改进并结合了局部搜索和基于关键路径的领域策略，实验证明所提算法能够有效地优化多目标DFJSP；李瑞等人［10］对模因算法进行改进，并设计了具有多种交叉方式的全局搜索算子，改进后的算法能更好地优化调度的最大完工时间和总能量消耗；Wu等人［11］将差分进化算法和模拟退火算法相结合，用于权衡DFJSP的延迟成本和总成本。通过研究发现，许多学者已经在节能减排调度方面作出了贡献。但是大多数的研究是基于离散的旧算法，或者把连续算法使用简单的交叉和变异进化成离散算法，存在未结合多目标DFJSP的具体特性进行改进的问题。

综上所述，关于DFJSP，前期更多的是针对单目标调度模型。近些年随着研究的深入，关于更复杂的多目标调度研究逐渐引起重视。在多目标优化调度方面，缺乏基于调度特性的Pareto多目标进化算法的研究。近些年，群智能算法发展迅速，更多性能强劲的算法被提出，但是连续的群智能算法无法直接应用在离散的车间调度中，因此在车间调度中关于连续的群智能算法的研究更少。

松鼠搜索算法（squirrel search algorithm，SSA）［12］自提出后，已被证明在解决现实问题中具有强大的竞争性，例如新冠肺炎X光图像分类［13］、多目标经济环境调度［14］等。但是目前尚未见关于多目标松鼠搜索算法在DFJSP中的应用研究。SSA是一种基于三种群的算法，具有优秀的种群协作能力，能够避免DFJSP优化中盲目的交叉和变异，这对于复杂的组合优化问题至关重要；此外，DFJSP通常涉及到大量的作业和资源问题，优化问题的数据维度较高，而SSA在处理类似的高维数据方面的优秀性能，使其可能成为应对DFJSP的合适选择。鉴于此，以及SSA在收敛速度和规避局部最优方面相较于其他算法具有的优势等，故选用松鼠搜索算法SSA求解优化DFJSP问题。

本文针对DFJSP，提出了一种改进的多目标松鼠搜索算法（multi-objective squirrel search algorithm，MSSA），同时优化最大完工时间和设备总能耗两个目标。本文将丰富关于SSA的研究，拓展求解多目标DFJSP的方法，具有理论和现实意义。

本文主要贡献以及其与DFJSP的关联性如下：a）设计了旨在降低调度中能耗的主动解码方案，这种解码方案可有效地减少空闲时间段，从而降低DFJSP的机器能耗；b）提出了混合种群初始化策略，可显著提高DFJSP的初始解方案质量，这对于改善最终的调度方案非常有利；c）对SSA的位置更新策略和捕食者概率进行了改进，可增强算法的优化能力，平衡算法的探索和开发能力，进而实现对DFJSP解空间的有效探索；d）设计了针对DFJSP的四种领域搜索策略，通过引入多样化的领域搜索，实现更精细的探索，有效解决了优化算法针对DFJSP易陷入局部最优的问题。

1 问题描述与数学模型

1.1 问题描述

DFJSP可以被描述为将n个工件分配到f个工厂中，每一个工件包含ni个工序，每个工件的所有工序在同一个工厂进行加工，每个工厂拥有m台机器。调度的目标是确定工序的排列顺序以及每道工序加工所选择的机器，同时还要使优化指标尽可能最优。DFJSP还需要满足以下条件：a）每个机器同时只加工一个工序，且不能被其他工序中断；b）一个作业的任何操作必须完成其前面的操作后才能进行；c）所有工件和机器在零时刻均处于就绪状态；d）工件选定工厂后，其所有工序均在此工厂加工，且每个工序只在一个机器上加工；e）不考虑工件加工过程中发生中断，不考虑机器发生故障。

1.2 数学模型

为了方便约束公式的构建和描述，本文引入了相关符号。n为工件数目；i为工件索引；Ji为工件i的工序数目；m为机器数目；nf为工厂数目；f为工厂索引；ni为工件i的工序总数；mf为工厂f的机器总数；j为工序索引；I、M和F分别为工件集合、机器集合和工厂集合；Oij为工件i的第j道工序；mijf为工厂f可加工工序Oij的机器数量；Cmax为调度的最大完工时间；Ci为工件i的完成时间；A为无穷大数；Kf为工厂f的机器集；Kijf为工厂f可加工Oij机器集；Pfk为工厂f机器k的加工次数集合，Pijfk则为本次加工Oij的时间；Sijf为工序Oij在工厂f的开始时间，Cijf为完工时间；Wijfk为工序Oij在工厂f机器k上的加工功率；Bfkt为工厂f机器k第t次加工开始时间， Ffkt为结束时间；Widlefk为工厂f机器k的空闲功率；TEC为总能耗；Yif为工件i分配到工厂f的值为1，否则为0；Efkt为工厂f中机器k第t次加工空闲能耗；Cfmax为工厂f完工时间；xijfkt为二进制数，用来表示Oij是否在工厂f的机器k上进行第t次加工，xijfk类似，用来确定Oij能否在工厂f的机器k上加工。

4 实验与讨论

4.1 实验设计

为了验证本文算法的性能，在数据集MK01-MK10［17］和DP01-DP10［16］上设计了相关的对比实验。所有的代码均使用MATLAB 2019b进行编程，软件的运行环境为：CPU为Intel CoreTM i9-9900K @3.60 GHz，RAM为64 GB ， Windows 10系统。本文设定工厂的数目为2，每个工厂中所有机器的加工能耗CPfk=4 kW·h，空载能耗IPfk=1 kW·h。

使用多目标中的超体积（hypervolume，HV）［18］和集合覆盖率（C-metric，C）［19］来评价算法的性能。HV可以同时评价收敛性和多样性。HV值越大，说明算法的综合性能越好。集合覆盖率（C）用于来评价两个算法所求解集的质量。C（A， B）=1表示B中所有个体都被A中一些个体支配，C （A， B）的百分比越大，说明解集A越好。

4.2 混合初始种群多样性对比

为了评估混合初始种群策略对初始解的影响，分别使用随机初始化和混合初始化在MK01测试实例上生成50个个体。两种个体在两个目标函数上的适应度箱线图如图6所示。箱子的长度表示数据的集中程度，显然混合初始化方式生成的种群更具有多样性。在两个目标函数中，混合初始化方式取得了更好的均值和中位数，说明了针对最大完工时间和机器总能耗初始化方式的有效性，这将更有利于种群的迭代搜索。

4.3 动态捕食者策略有效性验证

为了验证3.5节所提出的动态捕食者策略的有效性。将式（23）提出的非线性Pdp与其初始值0.3、终值0.7和中间值0.5进行对比。保持其他条件不变，在每个测试集上运行20次，计算平均HV。不同Pdp值的平均HV结果如表1所示。表中加粗的字体为最优结果，在所有问题上，改进后的非线性Pdp在七个实例上取得了最优值，位于第一位。这是因为相比于其他的定值，改进后的动态捕食者策略能够更好地平衡全局探索和局部开发，避免算法陷入局部最优。

4.4 领域搜索策略有效性验证

为了验证3.6节所提出的领域搜索策略的有效性。将没有领域搜索的算法记为SSA，将加入领域搜索策略的算法记为SSA+VNS，分别在测试集上进行测试。图7为SSA和SSA+VNS在MK01、MK06、DP08和DP10上所找到的前沿面。前沿面为算法20次运行所求得的非支配解集。由图中结果可知，加入领域搜索策略后，解集拥有更好的收敛性和分布性，且非支配解的数量也更多。

4.5 对比实验

为了进一步验证改进后算法的性能，将本文算法（MSSA）与著名的多目标算法NSGA-Ⅱ、MOEA/D以及新颖的算法HMMA［10］进行对比。每个算法在相同的实验平台上独立运行20次，迭代次数为100。各算法求得的平均HV值如表2所示。表3为MSSA与其他算法对比的C值。

如表2所示，除了MK01和DP02，MSSA在18个实例上取得了最好的HV结果，说明MSSA在绝大多数情况下求得调度方案解的数量以及解的多样性更好。MK01和DP02相比其他的测试实例，它们的机器和工件数量更少，但是MSSA的结果却弱于NSGA-Ⅱ。说明MSSA在面对部分工件数量少的测试问题时，解的多样性会有所减弱，但是在复杂的问题上（例如MK10和DP10），MSSA求得的HV领先更多，其优势非常明显。

在表3中，与其他三个算法进行对比，MSSA的C指标均最佳，说明MSSA在测试集上求得了最好的Pareto解集，其优化的完工时间和机器能耗均最优。这得益于MSSA三种群协作的优点，能够进行充分的信息交流，有助于搜索到更多更优的解。同时，领域搜索能够对找到的解持续优化，使得非支配解集收敛性更好。与其他算法的对比结果充分说明了本文算法的优越性能。

5 结束语

本文提出了一种针对DFJSP的改进多目标松鼠搜索算法，能够同时优化调度中的最大完工时间和机器能耗。结合DFJSP的特点，设计了有效的编/解码方式，针对优化目标的混合初始化方式提升了初始种群的质量。改进的动态捕食者策略能更好地平衡算法的全局开发和局部探索能力，并且设计了多种领域搜索方式来探索更优解。根据问题的特点，对松鼠的位置更新方式进行了改进，实现了连续的个体位置向离散的工序编码转换。通过实验证实了各个策略的效果。与其他算法的对比实验，证明了MSSA具有卓越的性能。

在面对部分测试问题时，算法会出现解的多样性有所下降的问题。因此，在以后的研究中，可对算法的领域搜索策略继续进行改进，寻求更多样、更高效的领域搜索策略。

参考文献：

［1］Gao Kaizhou， Cao Zhiguang， Zhang Le， et al. A review on swarm intelligence and evolutionary algorithms for solving flexible Job-Shop scheduling problems［J］. IEEE/CAA Journal of Automatica Sinica， 2019，6（4）： 904-916.

［2］唐红涛， 沈毅， 张伟， 等. 改进鲸鱼算法求解分布式装配柔性作业车间生产与配送联合调度问题［J］. 计算机应用研究， 2023， 40（7）： 1982-1990. （Tang Hongtao， Shen Yi， Zhang Wei， et al. Improved whale algorithm for integrated production and distribution scheduling problem in distributed assembly flexible job-shop［J］. Application Research of Computers， 2023，40（7）： 1982-1990.）

［3］王思涵， 李新宇， 高亮， 等. 分布式車间调度研究综述［J］. 华中科技大学学报： 自然科学版， 2022，50（6）： 1-10. （Wang Sihan， Li Xinyu， Gao Liang， et al. A review of distributed shop scheduling problems［J］. Journal of Huazhong University of Science and Technology： Natural Science Edition， 2022，50（6）： 1-10.）

［4］王无双， 骆淑云. 基于强化学习的智能车间调度策略研究综述［J］. 计算机应用研究， 2022，39（6）： 1608-1614. （Wang Wu-shuang， Luo Shuyun. Review on intelligent shop scheduling strategies based on reinforcement learning［J］. Applied Research of Compu-ters， 2012，39（6）： 1608-1614.）

［5］Giovanni D L， Pezzella F. An improved genetic algorithm for the distributed and flexible Job-Shop scheduling problem［J］. European Journal of Operational Research， 2010，200（2）： 395-408.

［6］Zhao Fuqing， Hu Xiaotong， Wang Ling， et al. A memetic discrete differential evolution algorithm for the distributed permutation flow shop scheduling problem［J］. Complex & Intelligent Systems， 2021， 8：141-161.

［7］李佳磊， 顾幸生. 双种群混合遗传算法求解具有预防性维护的分布式柔性作业车间调度问题［J］. 控制与决策， 2023，38（2）： 475-482. （Li Jialei， Gu Xingsheng. Two-population hybrid genetic algorithm for distributed flexible Job-Shop scheduling problem with preventive maintenance［J］. Control and Decision， 2023，38（2）： 475-482.）

［8］Li Xinyu， Xie Jin， Ma Qingji， et al. Improved gray wolf optimizer for distributed flexible Job-Shop scheduling problem［J］. Science China Technological Sciences， 2022，65（9）： 2105-2115.

［9］Sang Yanwei， Tan Jianpang. Intelligent factory many-objective distributed flexible Job-Shop collaborative scheduling method［J］. Computers & Industrial Engineering， 2022，164： 107884.

［10］李瑞， 王凌， 龚文引. 知识驱动的模因算法求解分布式绿色柔性调度［J］. 华中科技大学学报： 自然科学版， 2022，50（6）： 55-60. （Li Rui， Wang Ling， Gong Wenyin. Knowledge-driven memetic algorithm for distributed green flexible Job-Shop scheduling problem［J］. Journal of Huazhong University of Science and Technology： Natural Science Edition， 2022， 50（6）： 55-60.）

［11］Wu Xiuli， Liu Xianjing， Zhao Ning. An improved differential evolution algorithm for solving a distributed assembly flexible Job-Shop scheduling problem［J］. Memetic Computing， 2019，11： 335-355.

［12］Jain M， Singh V， Rani A. A novel nature-inspired algorithm for optimization：squirrel search algorithm［J］. Swarm and Evolutionary Computation， 2019， 44： 148-175.

［13］El-Kenawy E S M， Mirjalili S， Ibrahim A， et al. Advanced meta-heuristics， convolutional neural networks， and feature selectors for efficient COVID-19 X-ray chest image classification［J］. IEEE Access， 2021， 9： 36019-36037.

［14］Sakthivel V P， Sathya P D. Multi-area economic environmental dispatch using multi-objective squirrel search algorithm［J］. Evolving Systems， 2022，13（2）： 183-199.

［15］姚冠新， 范雪茹， 张冬梅. 基于改进变邻域搜索的多隔室车辆路径优化算法［J］. 计算机集成制造系统， 2022，28（9）： 2981-2997. （Yao Guanxin， Fan Xueru， Zhang Dongmei. Improved variable neighborhood search algorithm for multi-compartment vehicle routing problem［J］. Computer Integrated Manufacturing System， 2022，28（9）： 2981-2997.）

［16］Dauzère-Pérès S， Paulli J. An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search［J］. Annals of Operations Research， 1997，70（2）： 281-306.

［17］Paolo B. Routing and scheduling in a flexible Job-Shop by tabu search［J］. Annals of Operations Research， 1993，41（3）： 157-183.

［18］王凌， 吴玉婷， 陈靖方， 等. Seru系统调度优化的知识引导协同进化算法［J/OL］. 控制理論与应用. （2023-05-12）. https：//kns.cnki.net/kcms/detail/44.1240.TP.20230511.1840.066.html. （Wang Ling， Wu Yuting， Chen Jingfang， et al. Knowledge-guided co-evolution algorithm for Seru system scheduling optimization［J/OL］. Control Theory & Applications.（2023-05-12）. https：//kns.cnki.net/kcms/detail/44. 1240.TP.20230511.1840.066.html.）

［19］Luo Qiang， Deng Qianwang， Gong Guiliang， et al. An efficient memetic algorithm for distributed flexible Job-Shop scheduling problem with transfers［J］. Expert Systems with Applications， 2020，160： 113721.