随着全球经济一体化的发展，传统的中心化制造难以满足市场敏捷生产的需求，分布式制造引起了广泛的关注[1]．分布式柔性作业车间调度问题作为传统柔性作业车间调度问题的扩展，在后者工序排序和机器选择的基础上新增了工厂选择的要求，使得其更加难以求解．分布式柔性作业车间调度问题的模型主要分为考虑工序跨厂传输模型[2]和无工序跨厂传输模型[3]．分布式柔性作业车间调度问题的主要求解方法是采用元启发式算法配合局部搜索算子，包括遗传算法[2]、差分进化算法[4]、禁忌搜索算法[5]、蛙跳算法[3]、模因算法(memetic algorithm) [6]和分布估计算法[7]．总结已有研究，目前多数邻域结构的设计是基于交换和插入等大范围盲搜 [2-4,6-7]，这类模式效率较低．此外也有提出基于临界块的小范围邻域结构，文献[5]提出移动关键工序减少机器负载，但对于最大完工时间优化效率较低，因此针对问题特性设计知识驱动的邻域结构对于减少最大完工时间非常关键．随着全球变暖还有极端天气的频发，低碳的绿色调度越来越引起制造商们的关注，因此在分布式柔性作业车间调度问题中节能低碳也必须考虑．目前的研究缺乏有效节能策略，文献[3]提出基于主动调度的节能策略，但主动调度中有许多工序可通过延迟加工来优化空闲时间，因此设计更高效的节能策略是有意义的．针对上述问题，本研究提出了一种知识驱动的模因算法来求解多目标分布式绿色柔性作业车间调度问题，同时最小化最大完工时间和总的能量消耗，设计了一种知识驱动的变邻域搜索算子，提出一种新的基于全主动调度的能量存储策略．1 问题描述和模型1.1　问题描述多目标分布式绿色柔性作业车间调度问题包含三个子问题(工序排序、机器选择和工厂选择)．将n个工件分配到nf个工厂中，每个工件有ni个工序，这些工序被一同分配到同一工厂，每个工厂都有m台机器，将每个工厂中的工序排列调度顺序并为每个工序选择加工机器，最后将所有工厂中最大的完工时间作为整体的完工时间．在调度顺序确定后所有工厂的能量消耗也可以获得，主要的目标是调整工序和机器选择还有工厂选择最小化总体的完工时间和总能量消耗．多目标分布式绿色柔性作业车间调度问题的假设条件如下：a. 所有工厂、工件和机器在零时刻都是可用的；b. 每个机器同一时刻只能加工一个工序且不能被其他工序抢占；c. 所有的时间数据都是确定的而不是模糊的；d. 一个工件只能选择一个工厂，一个工序只能选择一个机器加工；e. 所有工厂的m台机器的型号都是相同的；f. 运输时间、启动时间及其能量消耗在本研究中都不考虑．1.2　车间调度问题的混合整数线性规划模型在对多目标分布式绿色柔性作业车间调度问题建模之前，给出本研究符号定义如下：i，i'为工件索引；j，j'为工序索引；k，k'为机器索引；t为机器加工次数索引；f为工厂索引；n为总工件数；m为总机器数；ni为工件的工序数；nf为总工厂数；mf为工厂f中机器的数量；mijf为工厂f中能加工工序Oij机器的数量；nmax为工件的最大工序数；pfk为工厂f中机器Mk的加工次数；I为工件集，I={1，2，…，n}；M为机器集，M={1，2，…，m}；F为工厂集，F={1，2，…，nf}；Ji为工件Ii的工序集，Ji={1，2，…，ni}；Kf为工厂f中机器集，Kf={1，2，…，mf}；Kijf为工厂f中能加工工序Oij机器集；Pfk为工厂f中机器Mk次数集合，Pfk={1，2，…，pfk}；Pfk'为工厂f中机器Mk前pfk-1的次数集合，Pfk'={1，2，…，pfk-1}；Oij为工件Ii的第j个工序；PijfkO为工序Oij在工厂f的机器Mk上的加工时间；Sfij为工序Oij在工厂f的开始时间；Cfij为工序Oij在工厂f的完成时间；Bfkt为机器Mk在工厂f的第t次加工的开始时间；Ffkt为机器Mk在工厂f的第t次加工的结束时间；WijfkO为工序Oij在工厂f的机器Mk上的加工功率；WfkIdle为在工厂f的机器Mk上的空闲功率；EW为总的加工能耗；EI为总的空闲能耗；Efkt为机器Mk在工厂f第t次加工的空闲能耗；Cmax为一个调度序列的最大完工时间；ET为总的能耗；L为一个为了保持不等式一致性的很大的整数；xijfk为若工序Oij可以被在工厂f的机器Mk加工值为1，否则为0；Xijfkt为若工序Oi，j被在工厂f的机器Mk上第t次加工则值为1，否则为0；Yif为若工件Ii被分配到工厂f的值为1，否则为0．多目标分布式绿色柔性作业车间调度问题的目标函数主要是Cmax和ET．a. 最大完工时间定义为min F1=Cmax=max{Cfini}    (∀i∈I,f∈F).b. 总能耗的定义为：minF2=ET=EW+EI;EI=∑f∈F ∑k∈M ∑t∈Pfk'WfkIdle(Bfk,t+1-Ffkt);EW=∑i∈I ∑j∈Ji ∑f∈F ∑k∈M ∑t∈PfkWijfkOPijfkOXijfktO.本研究提出的多目标分布式绿色柔性作业车间调度问题的混合整数线性规划模型描述如下：min F1=Cmax;min F2=ET.两个目标之间是负相关且存在冲突又存在依赖，优化ET须要尽可能减少EW和EI，而一味减少这两项可能使得Cmax变大，虽然优化Cmax同样须要减少加工时间和空闲时间，但起关键作用的是如何决定调度序列、机器选择和工厂选择，约束条件为：∑f∈FYif=1    (∀i∈I); (1)∑k∈Kijf ∑t∈PfkXijfkt=Yif(∀i∈I,j∈Ji,f∈F); (2)Sfini+∑k∈Kijf ∑t∈PfkPinifkOXinifkt≤Cfmax(∀i∈I, f∈F); (3)Cfmax≤Cmax    (∀f∈F); (4)Sfij+∑k∈Kijf ∑t∈PfkPijfkOXijfkt≤Sfi,j+1(∀i∈I, j∈Ji-1, f∈F); (5)∑i∈I ∑j∈JiXijfkt≥∑i∈I ∑j∈JiXijfk,t+1(∀f∈F,k∈Kf,t∈Pf,k'); (6)∑i∈I ∑j∈JiXijfkt≤1    (∀f∈F, k∈Kf, t∈Pfk); (7)Bfk,t+1-Bfkt≥∑i∈I ∑j∈JiXijfk,t+1PijfkO(∀f∈F, k∈Kf, t∈Pfk'); (8)Efkt+L≥(Bfk,t+1-Bfkt-∑i∈I ∑j∈JiXijfktPijfkO)WfkIdle(∀f∈F, k∈Kf, t∈Pkf'); (9)Bfkt≥Sfij-L(1-Xijfk,t+1)(∀i∈I, j∈Ji, f∈F, k∈Kijf,t∈Pfk); (10)Bfkt≤Sfij-L(1-Xijfk,t+1)(∀i∈I, j∈Ji, f∈F, k∈Kijf, t∈Pfk); (11)0≤Sfij≤L    (∀i∈I, j∈Ji, f∈F); (12)0≤Bfkt≤L    (∀f∈F, k∈Kf, t∈Pfk). (13)式(1)确保每个工件只能选择一个工厂，式(2)保证每个工件同一时刻只能被一个机器加工，式(3)和(4)定义了最大完工时间，式(5)确保机器加工不会被后置工序打断，式(6)强调每个机器的每次加工只能有一个工序，式(7)表示一个工件同一时刻只能有一个机器加工，式(8)确保空闲时间不小于零，式(9)表示同一机器两个邻接工序的空闲能耗，式(10)和(11)描述机器开工时间和工序开始时间的关系，式(12)和(13)表示变量范围．2 混合多目标模因算法2.1　算法框架模因算法可以高效平衡全局搜索和局部搜索的优点，在其他调度问题中应用广泛并取得了良好效果．考虑其优点，本研究设计了一种知识驱动的模因算法求解多目标分布式绿色柔性作业车间调度问题，主要步骤如下．步骤1 随机初始化种群Pt，大小为ps．步骤2 采用双人锦标赛选择，从Pt中选择精英个体加入交配池Qt．步骤3 遍历Qt，从Qt中随机选择个体与Pt中的个体以Pc和Pm的概率进行交叉变异，产生两个子代加入子种群Ct．步骤4 合并Qt和Ct得到Ht，删去Ht中适应值重复的个体，将Ht进行快速非支配排序[8]．步骤5 将得到的前沿面[8]中前ps个解加入新的父代种群Pt+1中．步骤6 对于Pt+1的每个解，执行全主动调度的能量存储策略，并将更新了父代的子代解加入存档Ω．步骤7 对于精英存档Ω中的所有个体，执行知识驱动的变邻域搜索策略，并更新存档Ω．步骤8 保留Ω中的非支配解，若不满足停止条件，则转到步骤2继续迭代．2.2　编码和解码采用传统的基于工序的编码虽然只具有半Larmark性质，但任意基因排序都是可行调度[9]．基于上述优点，本研究采用S(SO，SM，SF)的三层编码形式，分别表示工序顺序、机器选择和工厂选择．SO和SM长度为总工序数，SF长度为工件数n，详细编码参见文献[3]．2.3　初始化为了增加种群的分布性，本研究采用随机初始化策略．将SO按工件和工序顺序排列，再随机打乱生成ps个工序码，对于每个工序码中的每个工序，在可选的范围内随机选取一个机器构成机器码SM．从1到n对nf取余，随机打乱分配给每个工件构成工厂码SF，产生ps组(SO，SM，SF)为初始种群．2.4　全局搜索算子为了取得较大的搜索步长，本研究在全局搜索算子(global search operator，GSO)的设计中采用基于工序的交叉算子(precedence operation crossover，POX)和一般交叉算子(universial crossover，UC)，具体过程参见文献[8]．在交配池中随机选择一个不重复的解与当前解以Pc的概率做交叉操作，对于SO采用POX，对于SM和SF采用UC产生两个新解．然后以Pm的概率进行突变操作，随机选择两个工序交换位置，再随机选择两个工序随机重选机器．2.5　局部搜索算子针对问题的特性设计邻域结构以提升局部搜索效率称为知识驱动，在多目标分布式柔性作业车间调度问题中Cmax主要取决于关键工厂中关键路径上的工序，要想改变Cmax则必须改变关键工序的位置[9]．每个工厂可以视为一个柔性作业车间，一个柔性作业车间调度序列可以转换成相应的析取图[9]．而从开始节点到结束节点中的所有路径中长度最大的称为关键路径，在关键路径上的相同机器上相邻的工序组成一个临界块．块内的第一个工序称为头工序，最后一个称为尾工序，其他的则为中间工序，针对于临界块内的工序移动可以提高搜索效率．考虑多目标分布式柔性作业车间调度问题的收敛性与分布性，本研究设计了两种知识驱动的邻域结构，分别是针对减少Cmax的N6和变体来增加收敛性，并配备了两种随机搜索邻域结构增加分布性．2.5.1　邻域结构N6文献[9]提出邻域结构N6对柔性作业车间问题有效，在N6中对于首个临界块，随机将中间工序插到尾工序后，在最后一个临界块中随机将中间工序插到头工序之前．在其他临界块中随机将中间工序插入到头工序之前并再将另一个中间工序插入到尾工序后．2.5.2　邻域结构N6变体文献[9]认为只有移动临界块中头工序和尾工序的位置才能提升，因此在N6的基础上设计一种邻域结构变体．如图1所示，对于中间的临界块，随机选择中间工序或者尾工序插入到头工序之前．10.13245/j.hust.220606.F001图1N6变体邻域结构2.5.3　随机搜索邻域结构随机双点交换很常用，主要目的是用于增加搜索空间，增加存档的分布性．随机选择两个工序，交换其位置．同样地，使用随机单点插入算子，选择两个不同的工序，将后者插入到前者之前的位置．2.5.4　变邻域搜索策略对精英存档中的每个解，轮流执行上述四种局部搜索算子，若新解的适应值支配或互不支配旧解，则加入精英存档；若其支配原解则替换原解．2.6　能量存储策略同样地，针对绿色调度的知识特性，优化能耗是首要目标．总能耗ET主要与机器的加工时间和空闲时间有关，因此根据多目标分布式柔性作业车间调度问题的特性，设计有效的策略减少空闲时间，保持关键路径不变的前提下减少总能耗，提升后期种群收敛效率和增加找到非支配解的成功率．根据文献[9]“最优解一定在于全主动调度中”的结论，本研究设计了一种基于全主动调度的能量存储策略．2.6.1　主动调度解码当不推迟工序加工时间或改变工序之间优先级时，没有工序可提前的调度称为主动调度．通过改变同一机器上的工序顺序可以将半主动调度变为主动调度，即在同一机器上将后续工序提前，插入到可行的空闲时间处，具体过程参见文献[3]．2.6.2　全主动调度解码当一个调度既无法通过左移也无法通过右移来减少Cmax时则为全主动调度．如图2所示，将一个10.13245/j.hust.220606.F002图2右移得到全主动调度无法左移的调度序列，通过右移工序O11的方式减少空闲时间来节省能耗，具体步骤如下．步骤1 将全主动调度翻转，从最后一个工序开始动态解码，每个工序开始时间必须晚于其下一个工序的结束时间．步骤2 遍历当前工序所在机器上的空闲时间片，若小于自身加工时间，且插入后的开始时间小于其下一个工序的结束时间则可右移，重复以上步骤直至所有工序都完成解码．3 实验结果3.1　实验设计为了验证提出算法的有效性，本研究选取Mk01-10[10]和DP01-10[11]作为测试问题．本研究中所有代码均用Matlab2020编程，运行在Win11 Inter i7 2.9 GHz 16 GiB RAM(内存)．为了衡量多目标优化算法的性能，本研究采用超体积度量(VH)[12]和覆盖率C指标[6]．VH用于衡量综合性能且越大越好，C用于衡量两个算法之间的收敛性且越小越好．此外本研究只考虑双工厂的生产环境且WijfkO=4 kW·h，WfkIdle=1 kW·h．将所有工序分配到两个工厂中使得目标函数最小．3.2　参数实验算法参数的设置对算法的性能有较大的影响．在此对多目标模因算法(HMMA)的三个参数进行讨论，设置了三组因子ps={80，100，120}，Pc={0.5，0.7，1.0}和Pm={0.10，0.15，0.20}，并进行田口正交实验．随机选取一个测试集，每个参数变体独立运行20次，每次迭代200代，收集VH均值衡量不同参数的表现．设置ps=100，Pc=1.0和Pm=0.2．3.3　局部搜索策略的有效性为验证提出的知识驱动的变邻域搜索的有效性，在全局搜索算子GSO(记为A)和精英策略的基础上加入局部搜索算子GSO+VNS(记为B)．在所有测试集上独立运行20次，最大迭代次数为200．收集每次运行的非支配解集，计算VH的均值和覆盖率C．表1中展示了A和B的对比结果，加粗的数字表示更好，“+，-，=”分别表示显著性地好于、差于对比算法或二者没有显著性区别．由表1的结果可知超过一半以上的测试集中B的收敛性好于A，从VH指标看B的综合性能在一半测试集以上显著性好于A．这说明提出的知识驱动的变邻域搜索能增加收敛性，随机的算子可以增加分布性．10.13245/j.hust.220606.T001表1算法A和B的VH和C指标对比结果测试问题C(B，A)C(A，B)VH (A)VH (B)DP01DP02DP03DP04DP05DP06DP07DP08DP09DP10Mk01Mk02Mk03Mk04Mk05Mk06Mk07Mk08Mk09Mk100.250.250.400.250.430.000.670.000.800.500.570.670.000.291.001.000.200.001.000.500.600.170.000.750.251.000.000.330.500.000.000.001.000.200.000.000.711.000.000.330.123 90.146 20.137 70.135 00.151 20.147 70.130 00.109 50.144 50.063 50.167 80.160 20.089 40.135 90.067 00.093 00.117 60.080 90.088 90.086 80.124 4+0.147 4+0.136 8=0.135 2+0.152 0+0.145 7-0.130 9+0.111 3+0.139 5-0.064 4+0.167 2-0.162 6+0.089 6=0.137 0+0.068 3+0.099 2+0.115 8-0.081 2+0.086 5-0.093 3+3.4　能量存储策略的有效性为了验证提出的局部搜索策略的有效性，同样地设置变体算法在GSO的基础上添加能量存储策略(记为D)．如表2所示，在C指标和VH指标上，D都显著优于A，证明了提出的能量存储策略的有效性能够使得算法找到更多的非支配解．10.13245/j.hust.220606.T002表2算法A和D的VH和C指标对比结果测试问题C(D，A)C(A，D)VH (A)VH (D)DP01DP02DP03DP04DP05DP06DP07DP08DP09DP10Mk01Mk02Mk03Mk04Mk05Mk06Mk07Mk08Mk09Mk101.000.501.001.000.860.461.001.000.801.000.290.830.250.431.001.000.600.001.000.000.000.430.000.000.000.000.000.000.000.000.630.000.600.200.000.000.330.000.001.000.123 90.146 20.137 70.135 00.151 20.147 70.130 00.109 50.144 50.063 50.167 80.160 20.089 40.135 90.067 00.093 00.117 60.080 90.088 90.086 80.132 9+0.153 3+0.140 4+0.144 5+0.159 5+0.148 1+0.141 5+0.117 1+0.146 1+0.073 9+0.169 2+0.167 5+0.095 4+0.140 6+0.070 6+0.104 6+0.117 8=0.089 2+0.085 7-0.075 9-3.5　对比实验为了进一步验证多目标模因算法(记为F)的有效性，本研究选取算法HSLFA[3](记为E)进行对比．为了公平比较，在所有测试集上独立运行20次，并使用相同的停止条件．最大函数评价次数为6.5×104次．HSLFA参数设置参见文献[3]．表3给出了两个算法的对比结果，多目标模因算法在两个指标上显著好于对比算法．这是因为提出的知识驱动的局部搜索算子增加了收敛性，能量存储策略进一步增加了找到非支配解的能力．但在部分测试集上所提算法效果不如对比算法，原因是HSLFA的小10.13245/j.hust.220606.T003表3算法HSLFA和HMMA的VH和C指标对比结果测试问题C(F，E)C(E，F)VH (E)VH (F)DP01DP02DP03DP04DP05DP06DP07DP08DP09DP10Mk01Mk02Mk03Mk04Mk05Mk06Mk07Mk08Mk09Mk101.000 00.670 00.500 00.750 01.000 00.000 01.000 00.830 00.670 00.500 00.500 01.000 00.000 00.710 01.000 00.500 00.500 00.200 00.000 00.000 00.000 00.130 00.000 00.000 00.000 00.250 00.000 00.000 00.100 00.000 00.000 00.000 00.500 00.140 00.000 00.000 00.170 00.500 00.000 00.500 00.143 60.159 30.153 70.168 80.165 50.190 50.158 20.170 70.168 60.123 60.151 10.131 90.197 20.175 00.112 50.206 50.114 80.146 60.213 50.246 50.152 7+0.166 2+0.162 1+0.175 8+0.175 3+0.190 1=0.167 6+0.172 4+0.171 2+0.135 0+0.169 9+0.160 2+0.215 5+0.195 0+0.125 5+0.230 9+0.130 2+0.147 1+0.198 0-0.220 3-生境技术使得分布性增加，而多目标模因算法(HMMA)本身的基于拥挤度的多样性策略不能保证很好的分布性．4 结语本研究提出了一种知识驱动的混合模因算法求解双目标分布式绿色车间调度问题，同时最小化最大完工时间和总能耗．为了求解该问题，针对该问题特性设计了四种知识驱动的邻域结构，提高局部搜索效率，增加收敛性和分布性，提出了基于全主动调度的节能策略减少空闲时间，经过实验证明提出的算法能够求解该问题．但本研究还存在一些不足，如设计的局部搜索算子单独使用有良好效果，混合使用就会相互制约．设计新的邻域结构仍是重点，采取自适应策略协调不同算子之间的选择也是待解决的问题．