调度优化是选择合理调度方案的过程，对于提高制造企业装配生产的效益具有重要意义[1]．以轨道交通、航空航天和汽车制造等为代表的复杂产品的装配生产是现代制造业的重要组成部分[2]，不同于传统柔性作业车间生产，此类产品生产往往须要同时考虑加工和装配环节，因此其工艺输入是一个具有紧前紧后和并行执行关系的复杂工艺结构树．为了求解这种复杂产品的生产调度，综合调度(ISP)受到了广泛的关注，如文献[3-6]提出多种启发式规则对综合调度进行了优化，文献[7]采用遗传算法对其进行求解，文献[8]基于遗传算法设计了一种基于工序约束链的编码方法．ISP的本质为离散组合优化问题，烟花算法[9](FA)近年来在此类问题求解上受到广泛关注和应用，如电力系统备用约束动态经济调度[10]、复杂网络关键节点查找[11]、电动汽车继电器寿命预测[12]、电路面积优化[13]和随机装配线混流调度[14]等．文献[15]将烟花算法应用至柔性车间调度问题求解，文献[16]提出改进烟花算法求解混合流水车间调度问题，文献[17]设计离散多目标烟花算法求解带准备时间的流水车间调度问题，文献[18]为了改进传统烟花算法的迭代过程，避免多样性的缺失和防止过早陷入局部最优，提出一种基于独立框架的合作型烟花算法(CoFFWA)．ISP虽然同时考虑到了复杂结构件的加工和装配环节，但是在实际生产中焊接调度广泛存在于航空装备生产、汽车制造和轮船制造等企业[19]．不同于传统机加工，焊接生产具有两个特殊的约束：a. 在焊接生产中，部分工序须要多台焊接设备协同作业，即存在多台焊接设备同时服务于一道工序的情况；b. 除焊接设备外，焊接生产还须要在特定的平台上进行，即焊接生产调度须要在分配焊接设备的基础上进一步分配焊接平台．这两个约束会增加航空航天、轨道交通中大型结构件生产调度的复杂程度，并且仅考虑加工和装配环节的ISP问题模型不适用焊接环节，因此考虑焊接生产的ISP调度模型构建更加符合实际生产．同时，FA具有强大的搜索能力，但缺乏在ISP上的应用，且传统FA具有迭代后期种群多样性降低和过早陷入局部最优的缺陷，如CoFFWA在后期劣质烟花占据了大部分候选池，不利于后期完全收敛，因此有必要探索FA在ISP上的应用和搜索能力的进一步提升．综上所述，本研究将焊接生产中焊接相关设备及平台需求的实际情况在ISP的基础上进行扩展，提出一种基于双资源需求下的焊接综合调度模型(WSISP)，并在此基础上提出一种混合框架改进烟花算法(MFFA)用于求解．本算法设计了满足工序紧前、紧后约束的编码方式，无须修复操作即可方便获取合法解，在迭代前期和后期分别采用独立烟花框架模式和传统烟花框架模式进行搜索，以保证烟花种群的多样性和高质量，最后利用该算法对现有综合调度算例和实例进行求解和验证，表明了本研究算法的优越性和有效性．1 WSISP模型WSISP可以描述为通过调度复杂大型结构件中的n道具有顺序约束的焊接工序来使其成型，并优化某个/些目标，整个焊接加工过程必须按照各工序之间的紧前紧后约束关系得到树状结构进行．由此，模型中须同时考虑焊接设备和平台，其基本元素集合为三个：工序集N={N1，N2，…，Nn}；焊接装配平台集P={P1，P2，…，Ph，…，Pg}，其中，g为焊接相关平台的总数量，h为焊接相关平台的索引序号；焊接设备集M={M1，M2，…，Mq，…，Mm}，其中，m为焊接相关设备的总数量，q为焊接相关设备的索引序号．在工序集执行过程中，Pi表示第i道工序的所须焊接相关平台，i∈ N；Mi表示第i道工序的所需焊接相关设备集；li表示第i道工序的所须焊接相关设备数量；Si表示第i道工序的开始时间；Ci表示第i道工序的完工时间；ti表示第i道工序的加工时间；Ji表示第i道工序的同设备紧前工序；Fi表示第i道工序的工艺紧前工序集；v表示紧前工序索引号，v ∈ Fi；Ui表示第i道工序的同平台紧前工序；u表示同平台紧前工序索引号，u∈ Ui．同时，WSISP还必须满足以下假设：a．工序必须等所有紧前工序全部完工后才能开始加工；b．每个平台在任意时刻只能容纳一道工序装焊或加工；c．每台设备在任意时刻只能加工一个工序，同一工序可能会由多台设备协同加工，且加工过程不能中断；d．工序集中的工序同时须要占用焊接相关平台资源和焊接相关设备资源，两种资源缺一不可，其中，焊接相关平台的需求量只能为1，而工序的焊接相关设备需求量则根据实际情况给定．基于上述假设，该问题的数学模型如下．目标函数min d=max{Ci|1≤i≤n}，(1)式中d为最小化加工产品最大完工时间．约束条件Si≥max(max(Sv+tv),(Sj+tj),(Su+tu))    (v∈Fi,j∈Ji,u∈Ui); (2)Ci=Si+ti    (i∈{1,2,…,n})；(3)∑q=1myi,qa=li    (i∈N,  q∈{1,  2, …,  m})；(4)∑h=1gyi,h=1    (i∈N,  h∈{1,  2,  …,  g})；(5)yi,qa=1    (第i道工序占用了焊接相关设备Mq),0    (第i道工序未占用焊接相关设备Mq); (6)yi,hp=1    (第i道工序占用了焊接相关平台Ph),0    (第i道工序未占用焊接相关平台Ph), (7)其中：约束(2)表示每个工序的开工时间必须大于等于其全部紧前工序的完工时间；约束(3)表示第i道工序的加工完成时间为其开工时间加上该工序加工时间；约束(4)表示每道工序选择的设备数量为其工艺设定值，即对于每个工序加工存在多设备协同的情况；约束(5)表示每道工序只占用一个焊接平台；式(6)和式(7)为决策变量．2 MFFA基本原理2.1　MFFA流程本研究提出一种MFFA，其优势在于迭代前、后期分别采用不同的搜索框架，自适应解决搜索空间问题．根据现阶段烟花算法的收敛情况[9-18]，可在总迭代次数的70%前后完成收敛，因此将70%作为爆炸迭代前后期的分界线，前期采用独立框架模式[18]，K个烟花独立爆炸形成K个独立候选池，在各池内选择一个精英个体进入下一代．独立爆炸可以保留潜力烟花，使其顺利进入到爆炸后期，也适当保留前期表现相对劣的烟花，避免多样性降低从而陷入局部最优．后期爆炸采用传统框架[9]，所有烟花在通用候选池进行比较．在爆炸末期，失去潜力的劣质烟花会被淘汰，留给优质烟花更多的爆炸资源，确保探索到更优的位置，从而提高算法性能．MFFA流程如图1所示．10.13245/j.hust.220522.F001图1MFFA流程图2.2　个体编码WSISP的编码须考虑工序之间存在的紧前紧后约束，为设计满足约束的合法基因结构，本研究设计了一种基于工艺树的编码方法．以图2所示的简化工艺树为例：方框的内容为“工序号/装焊平台 装焊设备/加工时间”，如工艺树的第二行“N5/P1 M2/20”表示工序N5须要占用序号为M2的装焊设备和序号为P1的装焊平台，加工时间为20单位时间，并且部分工序存在多个设备协同加工的情况，如N6须要两台设备(M1和M2)协同加工．箭头指向代表工艺顺序，被指向工序须要在紧前工序完成后才能进行调度，图2中首次可调度工序集为{N1，N2，N3}．10.13245/j.hust.220522.F002图2简单产品焊接工艺树示例基于图2所示工艺树，可按照以下步骤执行个体编码以产生合法的基因结构．步骤1 输入工艺树和资源信息，设置备选工序集N0，初始化当前工序维度z=1，总工序数为Z；步骤2 扫描工艺树工序，将入度为0的工序放入备选工序集N0，更新备选工序集；步骤3 在N0中产生随机数来确定此次调度的工序Pi，将该工序Pi放到烟花的维度z；步骤4 在工艺树上检索当前被调度工序的紧后工序，其入度减1，当前维度z加1；步骤5 判断所有工序是否调度完毕，即当前工序维度z是否超过总工序数Z，若是则转步骤6，否则转向步骤2；步骤6 输出烟花个体．2.3　爆炸算子和高斯变异烟花集合为X={X1，X2，…，Xk，…，XK}，其中k为烟花序号索引．设Ek为烟花k的爆炸火花数目，其定义式为Ek=Ks(fk-fmin+ε)/∑k=1K(fk-fmin)+ε，(8)式中：fk为烟花k的适应度值；Ks为火花总数；fmin为当前代数烟花集合中的最差适应度值；ɛ为一个特别小的常数．式(8)在实际计算中采用取整操作．设Rk为烟花k的爆炸半径，其定义式为Rk=O(fmax-fk+ε)/∑k=1K(fmax-fk)+ε，(9)式中：O为基本爆炸半径；fmax为当前代数烟花集合中的最优适应度值．为使烟花爆炸搜索过程中不产生非法解，须要对爆炸和高斯变异做出改进．在爆炸操作中，随机选取原烟花Xk的一个位置z，对位置z上的工序进行爆炸位移，首先找到该工序离爆炸点最近的紧前工序和紧后工序的位置，其紧后工序与紧前工序之间的距离为R'，爆炸偏移距离为式(9)计算得到的Rk和紧后工序与紧前工序之间的距离R'的较小值，对位置z上的工序加上在该位移得到新烟花XkN．该操作可保证每次爆炸都满足约束的合法解，不需要修复过程，其表达式为XkN=Xk+round(min(Rk,R')rand(-1,1))，(10)式中：Xk为本次爆炸操作前的原始烟花；XkN为爆炸中烟花Xk在位置z上的工序须要爆炸偏移到新位置后的新爆炸烟花；round(∙)为根据四舍五入原则的取整函数；rand(∙)为随机函数，括号内为随机数范围．基于式(10)的位移变换操作示例如图3所示，被选择工序(如N4)的位移范围在最近的紧前工序(N2)和唯一的紧后工序(N6)之间，该位移变换的范围可保证迭代过程的合法性，且不漏掉每一次可爆炸达到的区域．10.13245/j.hust.220522.F003图3位移变换过程同时，基于同样的位移变换过程，考虑到进行高斯变异可不受适应度值fk计算得到的爆炸范围Rk的约束，其变异过程如下：当满足高斯概率pm时，随机选取Xk的一个位置z，须要对位置z上的工序进行高斯位移，同样根据工艺树信息找到紧后工序与紧前工序之间的距离R'，对位置z上的工序加上在R'内的高斯位移得到新基因XkM，其表达式为XkM=Xk+round(R'gs)，(11)式中：XkM为在烟花Xk在位置z上的工序须要通过高斯变异位移到达新位置后产生的变异火花；gs为服从高斯分布G(0，1)的一个随机数．3 算法验证为了验证本研究算法的有效性，选取相关复杂产品综合调度的实例进行算法性能测试．采用所提算法进行相关实例求解，测试环境为Acer Nitro N50-600台式机，8 GiB内存，Intel(R)Core(TM)i5-9400 CPU@2.9 GHz，Win10 64 bit操作系统．3.1　综合调度算例验证由于本研究解决的是综合调度中的新问题——焊接综合调度问题，且目前产品综合调度问题还未总结出通用基准算例，因此将现有研究文献中已存在测试算例进行比较分析，以验证本研究算法的有效性及稳定性．在对综合调度类算例求解中对比了五种规模的算例(见表1)，分别验证本研究算法在不同规模、复杂度和问题的算例求解中的有效性和稳定性．10.13245/j.hust.220522.T001表1不同规模实验参数设置参数11×418×433×454×528×4K2020200200200L2020100100200pm0.250.250.250.250.25T2020202020本研究所提算法MFFA设计的参数包括烟花数量K、爆炸次数L、高斯概率pm[14]和求解次数T．K和L根据算例规模大小和经验设定，不同规模算例的参数设置如表1所示．算例1为11个工序和4台机器数量的小规模算例[4]，文献[20]中ACPM&BFSM算法、文献[21]中动态优先级算法、文献[22]中动态关键路径算法、文献[23]基于设备空闲事件驱动算法、文献[3]可回退抢占的设备驱动算法和文献[4]考虑串行工序紧密度的择时综合调度算法求得最大完工时间(makespan)的最优调度结果分别为30，36，30，30，30和28，本研究算法求得最优结果为28，算法执行的平均时间为0.36 s．算例2为18个工序和4台机器数量的小规模算例[22]，文献[20]基于ACPM and BFSM的动态调度算法、文献[21]工序优先级动态调度算法、文献[22]动态关键路径调度算法和文献[7]虚拟零部件级别分区编码的遗传算法求得最优调度结果分别为200，190，175和170，本研究算法求得最优解为170，算法执行的平均时间为0.49 s．算例3为33个工序和4台机器数量的中等规模算例[5]，文献[22]中动态关键路径算法，文献[3]可回退抢占的设备驱动综合调度算法和文献[5]考虑后续工序的择时综合调度算法求得最优调度结果分别为23，23和20，本研究算法求得最优解为20，算法执行的平均时间为30.91 s．算例4为54个工序和5台机器数量的较大规模算例[8]，文献[7]分区编码GA和文献[8]基于工序约束链编码的遗传算法求得最优调度结果分别为711和681，本研究算法求得最优解为681，算法执行的平均时间为44.62 s．算例5为28个工序和4台机器数量的中等规模算例[6]，该算例具有多设备工序的特殊约束，MFFA是首次应用到多设备工序综合调度的智能算法．文献[6]的两个算法分别为首次适应及动态调整算法和优先调度虚拟工序算法，求得最优解分别为300和260，本研究算法求得最优解为255，对应调度结果甘特图如图4所示，图中：M1～M4为机器号；N1～N28为工序号．算法执行的平均时间为59.34 s．10.13245/j.hust.220522.F004图4MFFA求解多设备工序算例的甘特图通过上述五个综合调度算例的对比求解，本研究算法可以准确、稳定求得每一个算例的现存最优解，并在最复杂的28×4多设备工序综合调度[6]算例的求解中超越了现存最优解，验证了MFFA在求解综合调度问题上的有效性、通用性和优越性．3.2　烟花算法框架验证为了验证基于混合框架的改进烟花算法的有效性，选择算例1～5设计对比实验，对传统框架的烟花算法(FA)[9]、基于独立框架的协作烟花算法(CoFFA)[18]和MFFA进行对比实验，设置算法参数参照3.1节，对比内容包括mean(20次实验所得到的最大完工时间平均值)、min(20次实验所得到的最大完工时间最小值)、击中率(20次实验中击中最优解的几率)和求解耗时，对比结果如表2所示．10.13245/j.hust.220522.T002表2改进烟花算法框架性能对比规模FACoFFAMFFAmeanmin击中率求解耗时/smeanmin击中率求解耗时/smeanmin击中率求解耗时/s11×428.05280.950.3428.05280.950.39282810.3618×4174.001700.750.48170.251700.950.5117017010.4933×421.60200.3529.9720.75200.3531.522020130.9154×5686.506810.8043.02682.506810.9546.87681681144.6228×4261.252550.3557.52255.252550.9561.53255255159.34可以看出：在多个不同综合调度算例的求解结果中，MFFA在设定不同的烟花种群规模和爆炸次数下，随着算例规模的增大，求解耗时也在增加，在保证求解精度的条件下，MFFA的算法执行时间与FA的差距不大，同时少于CoFFA，在对五个不同规模算例求解20次得到的目标均值和击中率均优于FA和CoFFA，其中击中率较FA提升36%，较CoFFA提升17%，由此可看出MFFA在保证算法效率的前提下对求解综合调度类问题是有效的．3.3　焊接实例验证由于现有算例未考虑到本研究所提的焊接综合调度模型，为进一步验证本研究算法在求解该类问题上的性能，因此采用某大型焊接制造企业实例进行求解验证，车间焊接资源信息如表3所示，由多个复杂产品串行线构成(见图5)，共包括71道工序．该企业生产的复杂焊接结构件的一般串行工艺顺序为：装配→焊接→打磨→修复焊接→热处理→喷砂→交检收尾．基于产品类别差异，部分产品的工艺顺序和工序略有不同．10.13245/j.hust.220522.T003表3焊接资源清单资源名称资源符号资源名称资源符号装配平台P1点焊装配设备M1焊接平台P2堆焊设备M2打磨平台P3打磨设备M3修复焊平台P4修复焊设备M4热处理平台P5喷砂设备M5喷砂平台P6装配辅助设备M610.13245/j.hust.220522.F005图5复杂产品焊接工艺树本节的实例求解对比算法为FA[9]，GA[8]，CoFFA[18]和MFFA，上述三种烟花算法中的参数设置如下：烟花数量为600，爆炸次数为200，遗传算法初始种群规模为600，迭代代数为200，交叉概率为0.7，高斯概率为0.1[8]．每个算法独立运行20次，计算得到最大完工时间，其对比结果如表4所示．本研究MFFA算法求得最优结果makespan为115 d，调度结果甘特图如图6所示．10.13245/j.hust.220522.T004表4实例算法验证对比(makespan)算法minmean求解耗时/sFA124127.60376.43GA119123.95423.12CoFFA120122.40386.30MFFA115120.75384.3010.13245/j.hust.220522.F006图6采用MFFA算法获得的某大型焊接车间调度结果从表4中可以看出：MFFA算法求解此类综合调度问题，求解精度上有明显提升，平均耗时较GA更少，与其他算法差异不大，说明本算法在保证效率前提下较其他算法具有更好的搜索性能，其原因在于改进混合框架保证了前期种群多样性和后期寻优效率，从而提升了算法性能和搜索精度．在图6中，焊接相关平台和焊接相关设备分别由不同颜色的矩形块表示，最大完工时间与焊接车间原计划的147 d相比工期缩短了21.7%，再次验证了本算法的有效性．4 结语本研究针对实际复杂产品制造中存在大量焊接生产的特性，将复杂产品生产的工艺树输入与焊接生产的多资源需求和多机协同等特点结合，提出一种以最大完工时间为目标的焊接综合调度优化模型．在此基础上，设计了一种改进烟花算法进行优化求解，该算法首先改进了基于工艺树的编码方式、爆炸算子和高斯变异算子以避免搜索过程中产生非法解，其次采用了一种以迭代次数作为控制参数的混合搜索框架以提升算法的搜索性能．通过在多个综合调度算例和焊接综合调度工程实例上与其他算法的对比，验证了该算法的有效性．