分布式生产制造模式已逐渐成为国际智能制造业的主要生产方式之一，其发展也进一步推进着经济全球化和生产国际化的进程[1]．分布式生产制造系统能够充分利用不同国家和地区的多个企业或工厂的资源[2]，通过原材料的有效分配、生产力的最优组合及科学合理的资源共享等方式，以较低的成本快速实现产品的生产和制造[3]．以不同的生产和加工条件为背景，诞生了许多具有复杂约束条件的调度问题，如：分布式置换流水车间调度问题(DPFSP)[4-5]，分布式零空闲流水车间调度问题(DNIFSP)[6-7]，分布式零等待流水车间调度问题(DNWFSP)[8]，分布式阻塞流水车间调度问题(DBFSP)[9-10]等．以分布式装配制造为背景，加工阶段与装配阶段的协同生产模式，不仅能够缩短产品的生产周期、降低企业的生产成本，而且能有效减小企业的运营风险，进一步提升企业的核心竞争力．然而，由于随着问题规模的扩大，基于强约束的分布式装配流水车间调度也逐渐成为制约企业提高生产效率的又一关键问题．DABFSP可分为加工阶段和装配阶段两个过程[11]．在加工阶段，具有阻塞约束的分布式流水车间由一组分布式的加工工厂组成，其中每个加工工厂的工件分配和工件的排序是要解决的关键问题．这类分配和调度问题是非线性、强约束的，近些年学者提出了许多方法解决此类问题：分散搜索算法(SS) 以最小化DPFSP中的最大完工时间为优化目标[5]；合免疫算法(HIA)在解决DPFSP时有效利用了具有四个搜索算子的局部搜索方法，并通过实验验证了算法的有效性[4]．此外，求解DBFSP一系列建设性的启发式方法[12]为解决加工工厂中的工件的分配和排列问题做出了有效地尝试．在装配阶段，具有产品组装功能的装配流水车间仅由一个装配机器组成，在加工车间制造完成的待组装工件被转移至装配工厂进行组装，从而产生最终产品．分布式装配调度最初是将分布式置换流水车间调度与装配调度问题相结合而提出，即分布式装配置换流水车间调度问题(DAPFSP)[13]．此问题的目的是在最大装配完成时间最小化的情况下输出调度序列．此外，对于分布式装配零空闲流水车间调度问题的研究也取得了一定的效果[14]．本研究针对分布式装配阻塞流水车间调度问题(DABFSP)，以最大装配完成时间为优化目标，提出协同帝王蝶优化(CMBO)算法．相较于其他研究，在算法的初始化以及迭代过程中，CMBO不仅能够有效利用DABFSP的特征，而且在解决高维问题时能够高效降低算法的复杂度，并通过局部搜索方法使解的精度得到进一步提升．1 问题描述及最大装配完成时间计算1.1　模型建立定义如下的符号变量：n为工件数量；m为加工工厂内的机器数量；F为加工工厂数量；s为产品数量；i为工件索引号；j为机器索引号；f为工厂索引号；k为工序索引号；h为产品索引号；Oi，j为加工时间；th为产品装配时间；π为调度序列；πf为加工工厂调度序列；nf为加工工厂内工件数；nhf为加工工厂内属于某一产品的工件数；Nh为组成产品的工件数；Cmax(π)为最大装配完成时间；{J1，J2，…，Jn}为工件集合；{M1，M2，…，Mm}为机器集合；{F1，F2，…，FF}为工厂集合；{P1，P2，…，Ps}为产品集合；Ti为工件的流经时间；Gi，h为二进制变量；Df，k，j为连续变量，表示工件j在机器k、工厂f中的离开时间；Di为工件的离开时间；Bh为某一产品的装配完成时间；xi，k，f为决策变量；Pi为第i个产品；Ji为第i个工件；Ti为总处理时间；πi(j)为第i个工厂第j个工件的调度序列．利用数学方法对实际应用问题进行建模是一种常见的求解问题的方法，因此DABFSP的混合整数线性规划模型(MILP)如下所示．决策变量xi,k,f∈{0,1}．(1)优化目标min Cmax(π)．(2)约束条件∑f=1F∑k=1nxi,k,f=1    (∀i=1,2,…,n)；(3)∑i=1nxi,k,f≤1    (∀k=1,2,…,n，∀f=1,2,…,F)；(4)Df,0,j≥0    (∀j=1,2,…,m，∀f=1,2,…,F)；(5)Df,k,0≥Df,k-1,1(∀k=1,2,…,n，∀f=1,2,…,F)；(6)Df,k,j≥Df,k,j-1+∑i=1nxi,k,fOi,j (∀k=1,2,…,n，∀j=1,2,…,m，∀f=1,2,…,F)；(7)Df,k,j≥Df,k-1,j+1 (∀k=2,3,…,n，∀j=1,2,…,m-1，∀f=1,2,…,F)；(8)Di≥Df,k,m-L(1-xi,k,f) (∀k=1,2,…,n，∀i=1,2,…,n，∀f=1,2,…,F)；(9)Bh≥Bh-1+th (∀h=1,2,…,S)；(10)Bh≥Di+th-L(1-Gi,h) (∀i=1,2,…,n，∀h=1,2,…,S)；(11)Cmax≥Bh (∀h=1,2,…,S)；(12)Bh0．(13)式(1)为决策变量；式(2)为本问题的优化目标；约束(3)确保将每个待加工工件仅分配给一个加工厂，并且仅出现在该工厂可行的调度序列中的一个位置；约束(4)确保加工工厂的每个位置最多只能分配一个待加工工件；约束(5)定义了初始条件；约束(6)表示第一台机器上每个工厂的待加工工件开始时间；约束(7)表示每个工厂中同一工件的两个相邻加工工艺的离开时间之间的关系；约束(8)表示每个工厂中两个相邻工件的离开时间之间的关系，表示满足了阻塞的约束；约束(9)确定每个待加工工件离开加工厂的时间；约束(10)确保相邻组装产品之间的关系；约束条件(11)确保仅在处理了所有组成待加工工件之后才组装每个产品；约束(12)定义了最大组装完成时间；约束(13)确保每个产品的装配完成时间均为非负数．1.2　最大装配完成时间计算方法DABFSP的最大组装完成时间Cmax(π)计算过程包括：a．在加工工厂中计算所有工件的加工完成时间；b．根据属于每个产品的最后一项工件的处理完成时间，确定产品组装顺序；c．计算组装完成时间．表1列举了一个分布式装配阻塞流水车间调度问题的实例．10.13245/j.hust.220523.T001表1分布式装配阻塞流水车间调度问题实例产品工件序号加工时间/ms装配时间/ms机器1机器2P1216746468405896872362P2184123732294675188808为了详细阐述DABFSP的计算过程，该实例包含八个待加工工件，两台机器，两个加工工厂和两件产品．假设调度顺序为π=[π1,π2]，处理顺序为π1=[π1(2),π1(4),π1(5),π1(7)]和π2=[π2(1),π2(3),π2(6),π2(8)]．步骤1 由加工序列和每个产品的加工时间可得每个工件的加工完成时间，进而确定产品组装顺序，如表2所示．10.13245/j.hust.220523.T002表2计算步骤1结果产品工件加工时间/ms工件的加工完成时间/ms机器1机器2P1216723468401245896824172362303P218414932294143675181618808249步骤2 由表2可知：组成产品P1的最后一个加工完成的工件是工件J7，组成产品P2的最后一个加工完成的工件是工件J8，因此组成产品P2的所有工件率先进入装配过程，其开始时间为249 ms，待产品P2组装完成后，判断产品P1是否能够开始组装．步骤3 经计算可得：按照上述加工顺序进行产品的加工和装配时的最大装配完成时间为(486+46) ms=532 ms．2 协同帝王蝶优化算法帝王蝶优化(MBO)算法是一种高效的元启发式方法，可直接用于求解连续优化问题[15]．分布式装配阻塞流水车间调度问题是离散问题，不能直接使用MBO求解，因此本研究提出的协同帝王蝶优化算法CMBO中，所包含的各种机制均是在原始MBO算法的基础上结合分布式装配阻塞流水车间调度问题特征离散化的结果．2.1　算法初始化首先，根据总处理时间Ti对属于同一产品的待加工工件进行降序排列，重复该过程，直到考虑所有产品为止．其次，假设此时每个加工工厂只加工属于某一特定产品的全部工件，根据以上步骤产生的序列选择组成此产品的全部工件，在所有可能的邻域位置中选择总加工完成时间最小的位置进行插入，重复此过程，直到考虑所有产品为止．然后，在组成某一产品的全部工件都加工完成后，根据组成此产品的所有工件的最大加工完成时间对所有产品进行降序排列．以表1中所提供的问题实例为例，经过上述步骤后的初始化结果如表3所示．10.13245/j.hust.220523.T003表3初始化产品排序结果产品工件加工时间/ms总处理时间/ms最大加工完成时间/ms机器1机器2P158968157157468401087236285216723P2322941161246751893880888184149由于CMBO采用实数编的方法，因此可得初始化序列为{5，4，7，2，3，6，8，1}，将此序列当作协同帝王蝶优化算法的初始化种群．最后，将种群分为子种群1和子种群2，子种群1和子种群2中的个体数量分别为N1和N2，有N1=lN；N2=N-N1，式中：N为种群规模；l为子种群1中帝王蝶的迁移率，且l=5/12．2.2　迭代过程与局部搜索策略在子种群1中，候选解决方案生成为xit+1↔xr1t    (r≤l),xr2t    (其他); (14)r=RE，(15)式中：t为CMBO当前的代数；xit+1为迭代t+1时的第i个解；xr1t为迭代t时的第r1个解；xr2t为迭代t时的第r2个解；r为基于式(15)的随机数；R为取值范围为[0，1]的随机数；E设置为1.2；r1为从子种群1中随机挑选的个体下标；r2为从子种群2中随机挑选的个体下标；↔表示交换．在子种群2中，候选解决方案生成为xjt+1↔xbestt    (R≤l);xr3t    (其他), (16)式中：xjt+1为迭代t+1时的第j个解；xbestt为子种群1和子种群2在迭代t时整个种群的最佳解；xr3t为迭代t时的第r3个解；r3为从子种群2中随机挑选的个体下标．根据上述步骤产生的序列，开始执行局部搜索操作：将序列中的工件逐一插入工厂中所有可能的位置，并选取最小装配完成时间的位置作为此工件的最终位置，重复上述步骤，直到考虑所有的工件．2.3　算法流程本研究提出的CMBO算法的步骤如下：步骤1 使用初始化方法构造初始化调度序列；步骤2 种群划分，划分种群为两个子种群；步骤3 使用离散的迁移算子更新子种群1；步骤4 使用离散蝴蝶调整算子更新子种群2；步骤5 合并两个更新的子种群；步骤6 采用局部搜索机制；步骤7 计算适应度函数值；步骤8 输出最优解．3 实验设置及结果分析3.1　实验设置为分析CMBO的性能，在900个实例上进行性能测试[9]，测试集由不同的待加工工件数、机器数、工厂数和产品数组合而成．本实验将900个实例按照待工件数、机器数、工厂数和产品数进行分类，同时将CMBO与迭代贪心算法(IG)[11]和迭代局部搜索(ILS)[14]进行性能比较．实验使用蒙特卡罗实验方法计算平均相对指数偏差值(ARPD)，所有实例均独立运行21次，结果如表4所示．10.13245/j.hust.220523.T004表4ARPD实验结果序号变量数量ILSIGCMBO1n82.3283.8430.2622123.8673.8900.2893164.4274.5760.4314204.8124.2220.4805244.4754.4870.5696m24.0054.2330.462734.5353.9810.631844.5854.5540.419954.4564.4070.25610f25.7302.6680.7751133.9484.5530.2921242.9665.3940.11413s22.90511.5350.1751433.5732.3110.2111543.3081.1570.1843.2　结果分析由表4可得到：ILS的均值为3.995，IG的均值为4.387，CMBO的均值为0.370，显然CMBO的ARPD值最小．从不同测试问题下的稳定性及与其他对比算法的显著性差异来看，CMBO明显优于其他两种算法．图1为根据实验结果三种算法的ARPD值的概率分布图，图中：εARPD为ARPD的均值；ρ为概率．每种颜色对应一种算法，细线为三种算法ARPD值的拟合正态分布线，显示用于生成直线或曲线的参数估计值，粗线为离散点的集合，对应三种算法ARPD值的结果，单种颜色虚线间距越大，效果就越差，离散程度越低则效果越好．从实验的概率图中能够看出：在满足正态分布的情况下，无论是均值还是方差，CMBO都是所有实验算法中最优的．10.13245/j.hust.220523.F001图1实验结果概率图为了在CMBO算法和其他比较算法之间进行成对比较，本研究使用Wilcoxon检验以分析实验结果的统计学差异．Wilcoxon符号测试的结果如下：CMBO和ILS比较，p值为3.384×10-111，在置信区间α(α=0.05)内存在显著性差异；CMBO和IG比较，p值为8.498×10-69，在置信区间内存在显著性差异．在Wilcoxon检验中，若p值小于α，则表示成对之间算法存在显著差异．将CMBO与对比算法进行了比较，所有p值均小于α，因此根据Wilcoxon检验，与其他算法相比，CMBO对解决分布式装配阻塞流水车间调度问题有显著性优势．为了在CMBO和其他比较算法之间进行统计比较，本研究采用Friedman检验，这是一种用于确定多个(相关)样本中显著差异的统计学检验方式，能够有效反映算法之间的性能差异．按照不同的待加工工件数量、机器数量、工厂数量及产品数量，将CMBO与两个对比算法分别进行Friedman检验，秩和检验结果如表5所示．因此，在95%的置信区间下，CMBO的性能均优于其他对比算法．10.13245/j.hust.220523.T005表5利用Friedman检验的实验结果变量平均等级ILSIGCMBOn2.3602.1861.454m2.3602.1851.458f2.3602.1831.457s2.3602.2171.4574 结语为解决分布式装配阻塞流水车间调度问题，本研究提出协同帝王蝶优化算法CMBO．利用问题的特征，在初始化阶段构造可行调度序列，在迭代阶段利用两个协同的离散操作算子，在局部搜索阶段进一步提升了解的精度．由900个问题实例的实验结果及对结果统计学分析可知：当解决DABFSP时，CMBO相较于其他两种对比算法具有显著优势．同样，CMBO为解决分布式装配阻塞流水车间调度问题也提供了新的解决方案．虽然所提出的算法在求解900个小规模分布式装配阻塞流水车间调度问题上具有显著优势，但是将CMBO应用于解决带有其他约束条件的分布式装配调度问题还有很大的拓展空间，今后的主要研究方向将集中在带有其他约束条件的分布式装配调度问题上．