智能制造焊接车间协同作业调度优化

周 珂，吕 民，夏自祥，李小冬

（1.济宁学院机械工程系，山东 曲阜 273155；2.哈尔滨工业大学机电工程学院，黑龙江 哈尔滨 150001）

1 引言

随着制造业不断向智能制造迈进，产品的定制化属性更加明显。为了适应定制化生产、提高生产柔性，工业机器人、加工机床、自动化生产线等在发挥自身优势基础上协同作业。在焊接车间，机器人焊接、人工焊接等方式并存，部分工序可以由多种方式完成，有些工序可以同时由多台设备和人员协同作业。随着定制化产品的增多，生产过程柔性提高，如何合理有效的进行协同作业焊接调度成为智能制造中亟待解决的问题。

柔性作业车间调度问题是车间调度问题的扩展，其中加工工序存在至少一台可供选择的设备，不同设备完成该工序的时间存在不同[1]，国内外专家学者利用加工分段、瓶颈分区、设备聚类、合理缓冲等方法，建立了相应的调度模型并加以求解[2-4]。遗传算法[5-6]、差分进化算法[7-10]在调度问题求解中有通用性较强、鲁棒性良好等优势，但在求解协同作业调度问题中易出现干扰方案，须对解码不可行的干扰方案及时修正。

针对智能制造焊接车间中协同作业调度问题，利用部分焊接设备可移动协同作业的属性，建立数学模型，以最小化最大完工时间和焊接能耗为目标开展调度优化研究。

2 可协同作业焊接调度问题描述

焊接车间内协同作业指的是不同焊接设备同时对同一焊接件进行焊接，协同作业可以缩短产品工期，加快定制化产品上市。焊接作业用时包括等待时间、运输时间、焊接前的装配时间、焊接预热时间、焊接时间、热处理时间、检验及补焊时间、焊接件拆卸时间等，使用不同设备、操作人员不同会导致焊接用时不同。

为建立焊接调度问题数学模型，定义基本变量，如表1 所示。

表1 变量及说明Tab.1 Variable and Description

协同作业焊接车间调度问题可描述为：存在N个待加工焊接件台焊接设备焊接件Wi（i=1，2，…，N）在焊接车间的加工由Ni个焊接工序Pi1，Pi2，…，PiNi组成，焊接工序Pij可在中任何一台焊接设备上完成（K为能够完成工序Pij的设备总数），焊接工序Pi（j-1）至工序Pij的运输时间为TTij，焊接工序Pij的加工等待时间为TLij，焊接工序Pij加工前的装配时间为TAij，焊接工序Pij预热时间为TPij，使用设备Ml时工序Pij所需的焊接时间为TWijt，焊接工序Pij焊接热处理时间为THij，焊接工序Pij检验时间为TEij，焊接工序Pij补焊时间为TWPij，焊接工序Pij加工结束的拆卸时间为TDij。设备Ml单位时间能耗为ECl。焊接件Wi（i=1，2，…，N）的工序须符合工艺路径要求，即Pi1→Pi2→…→PiJ。另外，焊接件在满足工艺要求且设备可移动的条件下，可以同时进行若干工序，但焊接设备同一时刻只能有一个焊接件在加工，即：焊接过程须满足不可中断约束、焊接件唯一性约束。

（1）焊接件Wi（i=1，2，…，N）的焊接工序Pij，可在预先给定的焊机或机器人的任一台设备上加工，且∃Pij，使

（2）每个焊接件Wi（i=1，2，…，N）的工序须符合工艺路径要求，即Pi1→Pi2→…→PiJ。

（3）焊接件的工艺路径多样（不同焊接件的工艺路径可不同），即∃Wk，Wj（k≠j），l，使得Mkl≠Mjl。

3 面向协同作业的焊接调度数学模型

求解焊接调度问题即是在满足工期和焊接工序约束条件下，确定焊接件的每道工序的焊接方式、作业设备，并依次安排加工顺序，以达到最小化最大完工时间Tmax和焊接能耗EC的目的。

式中：Ti—第i个焊接件的完工时间；TWl—第l台焊接设备Ml的焊接时间；TWPl—第l台焊接设备Ml的补焊时间。

这里的调度优化目标是完工时间短、焊接能耗低，目标函数为：

在该调度问题中，存在两个决策过程：（1）将焊接件Wi（i=1，2，…，N）的工序Pij（i=1，2，…，N；j=1，2，…，Ni），分配给具备加工该焊接工序能力的设备，即中的某台焊接设备进行加工；（2）确定焊接设备Ml（l=1，2，…，L）上相应焊接工序Pij的加工顺序。

4 改进的差分算法设计

4.1 算法流程

智能制造环境下的柔性焊接调度问题属于多目标优化问题，这类问题被证明是NP 难题。智能优化算法在求解这类问题中有结构较简单、算法较易于实现、收敛较快速、鲁棒性较强等优势，差分进化算法属于其中一种。差分算法采用实数编码，通过父代向量差分矢量扰动产生新个体，并将评判更优良的个体纳入种群完成迭代更新，逐渐得到所求问题的最优解。但是传统差分进化算法在求解焊接调度优化问题时易陷入局部最优解，针对该问题求解在利用差分矢量求实验个体方面按照工艺要求进行了修正，改进的差分算法流程，如图1 所示。

算法流程如下：

（1）初始化算法参数，定义种群规模M，进化代数g=0。

（2）基于负载均衡生成初始种群，种群内包括M个个体，每个个体由n维向量组成，Xi（0）=（Xi，1（0），Xi，2（0），Xi，3（0），…，Xi，n（0）），i=1，2，…，M。

（3）计算种群个体适应度值h（Xi）。

（4）判断是否满足终止条件，若满足则输出结果，若不满足则执行（5）。

（5）选择两个父代个体，生成差分矢量Xp1（g）-Xp2（g）。

（6）选择另一个体Xp3（g），与缩放的差分矢量求和生成实验个体Hi（g）。

（7）解码实验个体Hi（g），判断是否为可行解，即是否为可行调度方案。若方案可行，则进入（9）；若方案不可行，则进入步骤8进行实验个体修正。

（8）修正不可行方案的实验个体Hi（g），主要包括：对超出设备编号的焊接设备子串进行修正，对取值不在工艺要求范围内的设备编号进行修正，对取值超出设备能力的工序编号进行修正。

（9）父代个体与实验个体Hi（g）交叉生成新个体Vi（g）。

（10）基于适应度选择个体。

（11）进化代数加 1，返回（3）。

图1 改进的差分进化算法流程Fig.1 Improved Differential Evolution Algorithm Flow

4.2 算法设计

（1）编码采用MSOS 编码法对焊接调度进行编码，所有种群都采用整数编码，编码为两条子串，焊接设备串和焊接工序串。焊接设备串解决焊接工艺路径问题，焊接工序串解决工序排序问题。在解码时任意一个由MSOS 编码所生成的染色体总是可以解码成一套可行的焊接方案。此外，MSOS 编码中的两条子串分别代表设备及工序排序含义，反映焊接环节各工序所在设备和加工顺序，且在编码阶段采用相互独立的编码方法，因此，可以使用符合各自特征的交叉和变异算子，分别对两条子串进行操作。

（2）群体初始化根据负载均衡的原则生成初始种群：对于焊接设备子串，按照工序工艺要求以均衡负载的原则进行排列生成初始子串；对于焊接工序顺序子串，依据焊接件的交货期进行升序排列生成初始子串Xi（0）=（Xi，1（0），Xi，2（0），Xi，3（0），…，Xi，n（0）），i=1，2，…，M。

（3）适应度值为便于观察，采用目标函数值的倒数并扩大100倍作为适应度值。

（4）变异随机选择两个父代个体生成差分矢量Xp1（g）-Xp2（g）。选择另一个体Xp3（g），与缩放的差分矢量求和生成实验个体Hi（g）。

式中：F—缩放因子，一般取值范围［0，2］。

根据智能制造焊接车间调度问题特点，设计自适应差分缩放因子，如式（7）所示。其中Fu、Fl为边界值。

对于焊接车间调度问题，直接采用父代个体生成的差分矢量进行缩放生成实验个体，可能会得到不可行解，即解码后不能得到可实施的焊接调度方案。首先进行解码检测判断：焊接设备子串中设备是否超出设备编号，焊接设备子串解码是否承担了不具备加工能力的工序等。然后，根据焊接设备台数和工艺要求对得到的不可行解进行修正，修正后的实验个体再进入交叉操作。

（5）交叉父代个体与实验个体交叉产生新的个体。对于焊接设备子串，在与同一类型焊接设备组内任两台设备所对应的工序集中分别选择一个工序，对应交叉。对于焊接工序子串，采用交换位置变异算子。随机选择任一焊接工序，在可行设备对应序列内随机选择两个不同的变异点，交换两个变异点的焊接顺序。

（6）基于适应度选择个体分别计算新个体和父代个体的适应度值，将适应度值高的个体选择保留下来。

5 实例验证及分析

表2 部分工序与加工要求Tab.2 Partial Data of Processes and Requirements

某工业集团焊接车间部分焊接件、工序等数据，如表2 所示。焊接工期单位为天，“-”表示该焊接设备不能完成该工序。该实例中共有10 个焊接件和10 台可用设备，利用所述调度优化方法进行优化后，调度方案，如图2 所示。不同算法迭代代数和完工时间数据整理后，如图3 所示。

图2 焊接调度方案Fig.2 Welding Scheduling Scheme

图3 不同算法计算得到的完工时间数据Fig.3 Completion Time Data of Different Algorithms

由图2 可以看出，协同作业可以缩短完工时间，但是也带来了工位占用问题。不可移动的设备M5和M10在焊接结束后，由于协同作业设备M3尚未完成焊接，该工位仍被占用。即便如此，协同作业仍然比独立作业完工时间明显提前，如图3 所示。提高了设备利用率，缩短了生产周期。

6 结论

针对智能制造焊接车间中部分工序可协同作业的问题，采用改进的差分进化算法，对协同作业焊接车间调度进行了优化。通过对不同算法进行计算对比，发现采用自适应差分缩放因子的差分算法在进化前期能够保证种群多样性、在进化后期能够加快收敛速度，解决协同作业焊接调度问题可行且有效，为智能制造环境下定制化产品生产调度研究提供了参考。

在仿真实验和实例验证环节发现，个性化产品占比的提高对设计制造环节响应速度影响非常大，给调度优化带来了困难。为提高响应速度和市场竞争力，下一步研究中将基于调度预测数据反馈至工艺设计环节，建立工序柔性的焊接调度数学模型进行优化。