0 引言

在制造业中，合理的调度能够大幅地提高生产效率、提高资源利用率，减少浪费．置换流水车间调度问题（Permutation Flowshop Scheduling Problem，PFSP）作为一种典型调度问题，在大规模制造生产中得到广泛应用．通过将生产过程分为多个步骤，并有序地安排在专门设计的生产线上，PFSP显著提高了生产效率．然而，当机器的数量大于3个时，该问题已经被证明是NP难问题^[1]．目前，设计有效的元启发式算法是求解PFSP的主流方法．

随着工业技术和全球贸易的不断发展，企业订单数量急剧上升，生产商意识到分布式生产模式的多工厂协同才能满足市场和客户需求，适应不断变化的生产环境^[2]．分布式调度可让多个工厂协同生产，其关键优势在于其较高的生产效率和资源利用率^[3]．Naderi等^[4]首先提出了分布式置换流水车间调度问题（Distributed Permutation Flowshop Scheduling Problem，DPFSP）．DPFSP需要将作业分配给工厂，并确定每个工厂内作业的加工顺序，相较于PFSP更加复杂．为了解决DPFSP，Li等^[5]提出一种改进的人工蜂群算法，设计了基于工作量平衡的初始化方法和局部搜索策略，通过实验测试，证明了算法搜索的高效性; 此外，Zhao等^[6]改进了水波算法并设计了4种局部搜索方法，在优化具有阻塞的DPFSP时表现出优异性．

然而，针对DPFSP的相关研究显示，许多学者并没有考虑到加工速度对调度的影响，或者假设速度是恒定的．实际生产中，制造业的智能化发展加速，机器的加工速度灵活化成为了满足多种材料特性和工艺需求的必要条件．可变加工速度的DPFSP（Distributed Permutation Flowshop Scheduling Problem with Variable Processing Speed，DPFSP-VPS）可根据实时情况进行动态调度，从而提高生产效率并降低成本，有效地减少制造过程中的等待时间和排队时间^[7]，展现出了巨大的应用潜力．如今，学者们逐渐意识到DPFSP-VPS 研究的重要性，例如:Huang等^[8]指出数控机床变速加工的重要性，并提出一种双角色协同进化算法，设计了针对机器速度的多种局部搜索策略，实验结果表明了算法的优越性; Wang等^[9]提出一种基于知识的协同进化算法，设计了多个协同搜索策略，并采用了基于关键路径的方法来进一步提高算法性能; Wang等^[10]提出一种针对DPFSP-VPS的改进多目标鲸鱼群算法，能够在不影响生产效率的情况下提高能源效率，并针对完工时间和机器速度提出了更新利用机制．

同时，随着资源的过度消耗和全球变暖形势的日益严峻，提高环境的可持续性已成为一个迫切的问题，环保组织已开始提倡各种制造领域的节能降耗^[11]．在此背景下，企业在调度中考虑能耗已经成为转型升级的必然趋势．不仅在PFSP^[12]中，在混合车间^[13]和柔性作业车间^[14]等领域，节能调度也得到了广泛的研究．本文的研究主要聚焦于同时考虑最大完工时间和总能量消耗两个目标的DPFSP-VPS．两个目标的优化带来额外的困难，如何在算法中设计优秀的种群更新方式和有效策略成为研究的重点．

针对上述问题，本文提出一种双种群算法（Dual-Population Algorithm，DPA）来求解双目标的DPFSP-VPS．尽管双种群概念已在多个领域有相关研究，但在DPFSP-VPS领域的应用极少．与以往研究不同的是，本文提出的DPA首先针对每个种群的特性设计了不同的进化方式; 其次，完全舍弃了其他算法中固定的交叉变异概率，通过引入动态引导因子来指导算法的进化方向; 同时，两个种群在更新的过程中种群数量也在动态变化，这种灵活性能够平衡两种群的计算资源; 最后，设计了变速节能策略来降低调度中能量消耗．实验结果表明，本文所提算法在解决DPFSP-VPS问题上高效可行，相较于其他算法具有较大的竞争性．

1 分布式置换流水变速车间调度问题

1.1 问题描述

DPFSP-VPS 可描述为n个工件，在F个工厂加工．每个工厂都是一个包含m个机器的置换流水车间问题，即每个工件都包含m道工序．在DPFSP-VPS中，首先为每个作业分配工厂，确定工厂内作业的处理顺序，然后还需要为每个操作选择机器的处理速度．每道工序O_i，j在每个机器上均有一个标准的处理时间t_i，j，若O_i，j的处理速度为V_v，则其真实的处理时间为p_i，j=t_i，j/V_v，其加工能耗与p_i，j和$V_v^2$成正比．因此，加工速度越大，加工时间越短，但加工能耗越大．

关于DPFSP-VPS的假设如下:

1）所有机器可在零时刻开始加工;

2）每个工件可在任一工厂加工，但标准加工时间不同，具有异构性;

3）每个工件选定工厂后，则其所有工序均在此工厂加工完成;

4）一个作业的任何操作必须完成其前面的操作后才能进行;

5）不考虑工件加工过程中发生中断，不考虑机器发生故障．

1.2 数学模型

为了便于描述，对研究中所使用的符号进行了如下定义:

1）索引

j:机器索引$，j\in \{1，\cdots ，m\}$;

f:工厂索引，$f\in \{1，\cdots ，F\}$;

v:速度索引，$v\in \{1，\cdots ，s\}$;

i:工件索引，$i\in \{1，\cdots ，n\}$．

2）参数

n:工件的数量;

m:每个工厂的机器数量;

F:工厂数量;

s:加工速度的数量;

l:按顺序排列的工件位置;

V_v:第v个处理速度;

O_i，j:第i个工件的第j道工序．

3）决策变量

t_i，j:O_i，j的标准处理时间;

p_i，j:O_i，j的真实处理时间;

PP_f，j，v:工厂f中以速度v运行的机器j的单位能耗;

SP_f，j:工厂f中机器j单位时间的待机能耗;

PEC_f，j:工厂f中机器j的加工能耗;

SEC_f，j:工厂f中机器j的空闲能耗;

TEC:总能耗;

C_max:调度的最大完工时间;

C_l，j，f:工厂f中机器j上位置l的完成时间;

C（f）:工厂f的最大完工时间;

x_i，l，f:二进制变量，如果作业i占用工厂f的位置l，则值为1，否则为0;

z_i，j，v:二进制变量，如果作业i在机器j上以速度v处理，则值为1，否则为0．

DPFSP-VPS包括最大完工时间（Makespan）和总能量消耗（TEC）两个目标．Makespan和TEC是两个矛盾的目标，更小的Makespan意味更大的加工速度．但是，更大的加工速度会带来更大的加工能耗．因此，为了更好地平衡两个目标，需要有优秀的调度方案，以及合适的速度选择．

第一个目标Makespan如式（1）所示:

第二个目标TEC计算方法见式（2）．TEC包括每个工厂中所有机器的加工能耗（PEC）和空闲能（SEC），PEC和SEC的计算方法分别如式（3）和式（4）所示．

根据上文的假设和实际的生产情况，DPFSP-VPS的约束如下:

式（5）确保每个工件只能分配给一个工厂; 式（6）确保每个机器同一时刻只加工一个工件; 式（7）确保每道工序只能在一个速度下进行加工; 式（8）表示O_i，j的实际处理时间; 式（9）表示工厂中第一台机器从零时刻开始加工; 式（10）确保O_i，j在O_i，j-1完工后才可加工; 式（11）确保每台机器不能同时加工多个工序; 式（12）和（13）表示每个工厂的加工时间约束．

2 双种群算法求解DPFSP-VPS

2.1 编码解码

对于DPFSP-VPS，包括3个子问题:1）确定每个工件加工的工厂; 2）确定每个工厂内工件的处理顺序; 3）确定每道工序在每个机器上的处理速度．本研究根据3个子问题的特点采用三段式编码，即工件编码（JS）、工厂编码（FS）、速度编码（VS）．表1给出了一个7个工件、2个工厂和3种速度的DPFSP-VPS示例．根据JS和FS可知:有4个工件在工厂1处理，加工顺序为{1，5，3，7}; 有3个工件在工厂2处理，加工顺序为{6，2，4}．每一个工件有3道工序，对应每个工厂内的3台机器，根据VS可知每道工序的加工速度．假设每道工序的t_i，j均为3 h，则根据表1生成的调度甘特图如图1所示．

解码时，首先根据FS将所有工件分配给各个工厂，然后依照JS中的工件加工顺序安排每个工厂内的工序加工序列，最后根据VS确定每道工序的加工速度．通过标准处理时间除以加工速度，可以得到真实的处理时间，并根据加工能耗与速度的平方正相关原则计算出总能耗．

2.2 混合种群初始化

有效的初始化方法能够显著提高初始种群的质量，不仅有利于算法的快速收敛，还会提高最终解的质量．本文根据不同的优化目标提出了4种初始化策略，最终由每种策略各生成1/4个体组成混合种群．

1）DNEH原则:DNEH（Distributed Nawaz Enscore Ham）^[15]是在NEH基础上针对最小化流经时间的DPFSP提出的．本文对其进行改进，应用于多目标DPFSP．首先将所有工件的加工时间降序排列，假设为{3，2，4，1}．若有2个工厂，则将加工时间最长的工件3和工件2分别分配给2个工厂，保证每个工厂均有工件．至于工件4和工件1则逐一插入到任何可能的位置，并进行非支配排序，最后保留最好的方案．

2）完工时间优先原则:首先随机初始化JS和FS，然后将所有操作的VS设为最大．此操作能够使完工时间最小化．

3）加工能耗优先原则:执行速度选择时与策略2）相反，所有操作的VS被设为最小，以最小化加工能耗．

4）随机初始化:初始种群的多样性同样对最终的解方案至关重要^[16]．因此，本研究的一部分个体采用随机初始化策略，即随机初始化JS、FS和VS，这将有利于丰富种群的多样性．

2.3 双种群进化

本文提出的算法将所有个体分为2个种群，分别命名为精英种群（Elite Population，EP）和普通种群（Normal Population，NP）．在种群初始化完成后，根据非支配解集和拥挤度进行排序，初始时精英种群包含排名前50%的个体，剩余个体归为普通种群．算法中针对不同种群设计了不同的进化方式．

2.3.1 EP进化

EP的进化方式有2种，如式（14）所示．其中，GF为引导因子，可对个体的进化方式进行引导．

EP中均是拥有优良基因的个体，因此，对其执行自我进化有利于优良基因的融合交叉，从而加速收敛过程．对于EP中的某个个体EP₁，其自我进化方式为随机选取另一个体EP₂进行交叉进化．每个个体均包含3段编码的信息，在进化过程中，针对JS采用部分匹配交叉（Partial Match Crossover，PMX）．图2a给出了一个PMX的示例．首先，对2个个体随机选择2个不同的点并交换2点之间的排列生成2个后代; 然后，对个体内存在的非法解进行映射，通过映射将重复的非法解替换成另一个体相同位置的工件，若映射后仍存在非法解，则再次进行映射．由于每个工件的工厂分配和速度设定不存在相关性，速度也不存在排列约束，因此，针对FS和VS采用统一交叉（Uniform Crossover，UX）．UX即随机选取2个个体的对应的编码进行交换，图2b给出了一个关于FS的UX交叉的示意图．最终通过EP₁和EP₂的自我进化，产生2个新个体EP_new1和EP_new2．

在进化过程中，EP会逐渐靠近帕累托前沿，可能会陷入局部最优．因此，本文针对EP设计了4种针对关键工厂的局部搜索．关键工厂即完工时间最长的工厂，关键路径则为从开始到结束历时最长的加工路径．对关键路径中的关键操作进行优化，将有利于跳出局部最优，找到更优解．4种局部搜索如下所示:

1）LS1:关键工厂内插入．在关键工厂内，随机选择一个关键操作，将其插入其他可能的位置．

2）LS2:关键工厂内交换．在关键工厂内，随机选择两个关键操作，交换它们的位置．

3）LS3:关键工厂外插入．从关键工厂内，随机选择一个关键操作，将其插入到其他工厂可能的位置．

4）LS4:关键工厂内加速．随机选择一个关键操作，增大其处理速度．这将有利于降低Makespan．

2.3.2 NP进化

NP的进化方式也有两种，如式（15）所示:

NP中为普通个体，为了加快其收敛速度，将NP与EP进行协同进化．具体而言，NP中的个体会随机选择EP中的一个个体作为进化引导对象．进化方法仍是对JS使用PMX，对FS和VS使用UX．通过这种协同进化，可以避免算法盲目搜索，加快搜索过程．

变异是增加种群多样性的重要方式，NP中本就是较差的个体，对其进行变异会有更大的概率搜索到更优解．根据三段式编码的特点，设计了相应的变异方式．对于JS，变异是随机交换两个位置的工件．对于FS，变异是随机选择一个工件重新分配给另一个工厂．对于VS，变异是随机选择一个操作并改变其处理速度．

2.4 动态引导因子

EP和NP的进化方式均受到引导因子GF的影响．为了在种群迭代的过程中动态调整2个种群的进化方式，对GF的大小进行动态调整，如式（16）所示:

其中:GF_min和GF_max分别为GF的最小值和最大值，本文设置GF_min=0.2，GF_max=0.8; Iter和MaxIter分别为当前迭代次数和最大迭代次数．在迭代的前期，GF较小，2个种群将进行充分的自我进化和协同进化，此阶段是算法的快速收敛阶段．迭代过程中，GF不断增大，2个种群将更倾向于进行局部搜索和变异搜索．后期较大的GF可使 EP通过局部策略进行精细搜索，跳出局部最优，而NP则可通过变异增加种群多样性．

通过GF的动态引导，可调节2个种群的分工，让算法在不同阶段利用不同的优化策略．同时，算法能够在不同迭代阶段更加灵活地进行搜索，从而提高算法的性能和收敛速度．

2.5 调速节能策略

总能耗是DPFSP-VPS的另一个重要目标，如何设计有效的节能技术是节能调度的关键．在DPFSP-VPS中，加工速度是造成Makespan和TEC两个子目标相互冲突的关键因素．因此，本文设计了两种针对空闲时间的调速节能策略．这两种策略能够调整机器的加工速度，可以在不影响Makespan的情况下降低能耗．

1）减速策略:当同一台机器上的某个操作的开始时间大于上一个操作的结束时间时，就会产生空闲时间段．因此，可以降低空闲时间段前操作的加工速度，这样在减少空闲时间的同时还能降低加工能耗．如图3所示，将f₁中O_5，2，O_5，3，O_3，3加工速度变慢一档，空闲时间T₁和T₂消失，T₃减少一半．为了不影响Makespan，此操作只在非关键路径上进行．

2）加速策略:某个工件的上一道工序加工时间过长同样会产生空闲时间段．例如图1中f₂的O_2，1加工时间过长造成O_2，2的开始时间晚于O_6，2的结束时间，产生了一段空闲时间．因此，适当地增大O_2，1的加工速度，缩短其加工时间，即可提前O_2，2的开始时间，减少空闲时间．如图4所示，增大O_2，1加工速度后既减少了空闲时间还降低了Makespan．在加速后会降低空闲能耗，但也会造成加工能耗增加，所以，此方法调速后需要判断新解是否支配旧解．若新解支配旧解，则保留新解，否则旧解被保留．

减速策略能延长空闲时间段前一道工序的完工时间，加速策略能提前空闲时间段后一个工序的开始加工时间．两种方式均可降低TEC，且不会增大 Makespan．对于以上两种策略，设定各自随机选取概率为0.5．另外，为避免复杂的运算，规定只有迭代超过总迭代次数的90%时才执行调速策略．

2.6 动态种群

两个种群进化后，它们都会生成新的个体．这些新个体将与前一代的个体一同进行评价，根据拥挤度进行非支配排序．为保持种群数量的稳定，排名靠后的个体被淘汰，其余个体被选择并进入下一次迭代．

在双种群机制中，如何为两个种群分配合适的个体资源很重要．因此，本文设计了一种正反馈动态种群分配机制，如式（17）所示:

其中：|POP_new|为某个种群本代进化后被选择的个体数量; |POP|为该种群的个体总数．某个种群进化后，新生成个体被选择的比例越大，DP越大．通过计算两个种群的DP值，为取得较大DP值的种群在进入下一次进化时，额外分配5%的个体．通过计算两个种群的子代存活率，可以判断出当前哪个种群的进化效果更好．基于正反馈机制，为进化效果好的种群分配更多的个体，从而让其获得更多的资源，能够进一步提高算法的性能．

2.7 算法框架

本文提出了一种解决DPFSP-VPS的双种群算法，并为每个种群设计了不同的进化方式，算法的整体流程框架如图5所示．

3 实验结果与分析

3.1 实验介绍

目前尚未有关于DPFSP-VPS的开源基准．本研究参考文献^[8]和^[9]，基于Taillard基准生成了16个不同规模的实例，以n_m_F方式命名，具体的实例参数如表2所示．在异构工厂中，每个操作在不同工厂中的处理时间不同，工序的标准处理时间符合均匀分布U（1，99）．种群数量和迭代次数根据以往研究中的主流选择，分别设置为100和200．所有代码使用Matlab2019b编程，软件的运行环境为:CPU:Intel（R）Core（TM）i9-9900K @3.60 GHz; RAM:64 GB，Win10．

由于真实的帕累托前沿未知，本文采用超体积度量（Hypervolume，HV）^[17]作为评价指标．HV可以同时评价解的多样性和收敛性，HV值越大说明算法的综合性能越好．本文对每个问题均独立运算20次，以确保结果的可靠性．

3.2 策略有效性验证

表3展示了不同算法所拥有的策略．为了验证各个策略对算法性能的影响，将这些算法进行对比测试．表4展示了算法20次运行求得的平均HV值，加粗体为最优值．可以看出，随着策略的增加，算法的性能逐步提升．包含所有策略的DPA取得了最多的最优值，证实了各个策略对算法的性能均有提升．

注：黑体为最优值.

3.3 对比实验

为了进一步验证DPA求解DPFSP-VPS的有效性，将其与主流的多目标进化算法进行对比，包括NSGA-Ⅱ、MOEA/D、SPEA2和专门用于DPFSP-VPS的新颖算法:BRCE^[8]．表5展示了所有算法的平均HV值（Ave）和相对标准误差（Dev），Dev为标准差与平均值的比值，表中加粗体为最优值．

正如表5所示，DPA的平均HV值和相对标准误差均显著优于其他对比算法，这表明DPA性能最佳且最稳定．此外，通过观察表中的数据，可以发现随着工件数量和机器数量的增加，算法的Ave均有不同程度的下降，但DPA的下降幅度是最小的．这主要归因于随着计算难度的增大，搜索空间不断膨胀，在有限的计算资源下更难找到高质量的解．而EP的自我进化能够在一部分空间进行精细搜索，NP的协同进化实现了不同空间的信息交流，两种群不同的进化方式使得DPA能够对解空间进行充分的搜索．复杂的多目标问题通常具有更多的局部最优解，这使得算法更易陷入局部最优．但是，DPA中的局部搜索以及变异搜索可有效地帮助算法跳出局部最优，避免了像其他算法那样性能大幅下降．

表6展示了所有算法的Friedman秩和检验结果，其中DPA排名第一．此外P值为5.440 2×10^-12，说明所有算法求得的结果具有明显差异．这进一步验证了DPA算法在求解多目标DPFSP-VPS时的优越性．

图6展示了在实例20_10_2上，所有算法得到的帕累托前沿．可以观察到DPA相比其他算法在分布性和收敛性方面表现更优．尽管在中部区域少部分解的质量稍逊于NSGA-Ⅱ和BRCE，但这是可接受的，因为DPA在两个目标的极值区域进行了更充分的探索．得益于调速节能策略的有效性，DPA找到了能耗更低的调度方案．在实际生产中，这意味着DPA给出的方案更有能耗优势．在图6中的A点（827.6，26 142）附近，DPA相比第二名NSGA-Ⅱ（827，26 376）能耗节省了0.9%，相比最后一名MOEA/D（840.9，28 412）能耗节省了8.7%，证明了DPA在节能方面的有效性和实用价值．

4 总结

本文提出了一种双种群算法，用于求解加工速度可变的分布式置换流水车间调度问题，同时优化最大完工时间和能量总耗．为了提高初始种群的质量，提出一种针对不同目标的混合初始化策略．针对两个种群的特点，设计了不同的进化方式，实现了对解空间的充分探索．同时，设计了动态引导因子，可在迭代过程中动态引导种群的进化方式．提出了一种新颖的调速节能策略，可在不影响最大完工时间的情况下降低能量消耗．最后，基于正反馈的动态种群机制，合理地分配了两个种群的资源．通过实验验证了各个策略的有效性，与其他算法的对比结果，证明了本文所提出的算法具有优异的性能．

注：黑体为最优值.

参考文献