考虑质量预测的前摄调度问题模型与算法

陆志强， 朱宏伟， 廖怡娜

(同济大学 机械与能源工程学院， 上海 201804)

对于飞机、船舶等大型设备装配制造企业而言，建立合理的调度计划是实现管理者高效管理装配过程的重要前提[1]. 目前，陆志强等[2]和朱宏伟等[3]将大型设备装配过程的调度问题抽象为资源受限项目调度问题(resource constrained project scheduling problem, RCPSP)及其扩展问题. 其中，RCPSP问题以满足资源限制和作业优先顺序为前提，通过合理安排装配作业的开始时间来达到优化相关决策目标(包括最小化装配工期等)的目的.

尽管已有学者就静态环境下RCPSP问题做了许多研究[4-6]，但装配环境中存在的不确定性使得实际装配过程的调度计划安排变得更加复杂. 不确定性环境下的RCPSP研究主要集中在决策方法和研究对象两个方面. 在决策方法方面，目前解决不确定性RCPSP问题的方法主要包括反应式调度、随机项目调度、模糊项目调度和前摄调度等. 其中，前摄调度通过生成模板调度计划以尽可能防止项目执行过程中由于不确定性因素导致的中断[7]. 崔南方等[8]和徐小峰等[9]分别提出了集中缓冲、STC(starting time criticality)分散缓冲方法和关键链缓冲区设置方法. Chakrabortty等[10]以具有不同概率分布函数的随机变量表示作业持续时间，并针对该问题提出了一种鲁棒优化模型. 在研究对象方面，除物料到达不确定、作业工期不确定和资源空窗期等外，部分学者还对有关质量缺陷问题开展了相关研究. 在单项目问题中，Al-Fawzan等[11]考虑到作业的执行时间会因为作业返工而增加. 为了有效求解这一问题，Abbasi等[12]提出了一种模拟退火算法. 在多项目问题中，Tiwari等[13]假设作业可以先按照一种不满足质量标准的模式执行，后续通过作业返工的形式来完善该作业. 此外，Maghsoudlou等[14]认为作业产生返工的风险由人员的技能水平差异所决定，因此以项目的执行成本和作业的返工风险作为目标函数. 然而，上述研究主要将目光集中在返工事件发生后被动的应对处理，缺少通过主动改善影响装配质量的相关因素而减少质量缺陷的深入研究.

事实上，在装配或加工流程明确的前提下，作业质量可以通过分析质量偏差传递过程以及建立质量预测模型来实现. 刘伟东等[15]通过建立偏差源传递的基本偏差流模型说明零件内部和外部偏差传递和相互作用. 江平宇等[16]采用基于粒子群算法优化的支持矢量回归机方法实现各作业的加工质量预测. 这些研究虽对质量偏差传递机理和质量预测方法进行了详细的分析，但相关模型仍不能真实反映实际飞机装配过程的作业装配质量. 由于飞机装配本身工艺的复杂性，除了待装配零件加工质量等因素对作业的影响之外，作业完成质量极大程度上依赖于装配人员水平. 装配人员的水平会影响整个装配系统的可靠性与稳定性，是产生质量缺陷的重要原因之一[17].

综上所述，本文以飞机装配过程为研究对象，分析与飞机装配质量传递相关的环节与信息，并结合装配人员水平对作业质量的影响情况，建立考虑装配人员水平的作业质量预测模型. 由于飞机装配中产生的质量特征(尺寸、位置和形状等)具有高度非线性[18]，结合支持向量回归(support vector regression，SVR)在非线性预测领域的适用性[19]，本文选择用高斯径向基函数为核函数的SVR预测模型对作业质量进行预测. 在此基础上，考虑到装配人员分配的合理性会通过作业质量间接影响到飞机整体装配进度，本文进一步提出了考虑作业质量预测的前摄调度问题，将装配作业的时间和人员决策耦合在同一决策框架中，并构建两阶段禁忌搜索算法进行求解.

1 问题描述及数学模型

1.1 问题描述

考虑质量预测的前摄调度问题，是通过分析各质量相关因素对飞机装配过程作业质量的影响形式，并结合实际作业质量的历史数据建立作业质量预测模型，以此为基础实现模板调度计划制定过程中装配资源合理分配和装配工期优化的目的. 考虑质量预测的前摄调度问题的假设和说明如下.

1)设有I个装配作业I={1,2,...,n}，i∈I为作业编号；作业i的前道作业集合为Pi，作业j为作业i的第j项前道作业；作业一旦开始便无法中断.

2)所有作业需要由相关装配人员等可更新的装配资源配合完成，记装配资源种类为K={1,2,...,e},k∈K为资源种类编号. 其中，装配人员存在异质性，主要体现在装配人员水平的差异. 记m∈M⊂K为装配人员种类编号，则装配人员m的水平可以表示为lm∈L. 不同装配作业i对资源k需求量记为rik. 资源k的资源总量上限为Rk.

图1 作业质量传递过程Fig.1 Transfer process of job quality

5)将时间离散化，记时间集合T={1,2,...,z}，t∈T为离散时间节点.

1.2 数学模型

基于以上分析，建立问题数学模型如下：

(1)

(2)

(3)

(4)

(5)

(6)

xit={0,1},i∈I, ∀t∈T;

(7)

yim={0,1}, ∀i∈I, ∀m∈M.

(8)

式(1)表示生成前摄调度计划的目标函数为最小化项目工期；式(2)代表作业间的时序约束，即任一作业不得早于其前道作业结束之前开始；式(3)代表资源约束，即任一时刻资源用量不得多于资源总供应量；式(4)代表作业一旦开始就不能中断；式(5)代表任一装配人员在同一时刻最多只能参与一个作业；式(6)为作业实际工期与人员水平、工件质量及前道作业质量间的映射关系，通过预测模型实现；式(7)和(8)分别代表了xit与yim的取值范围.

2 算法设计

针对质量预测前摄调度问题的特点，提出考虑人员水平的SVR预测模型和两阶段循环迭代搜索算法. 算法核心包括：结合装配作业历史质量数据，以装配人员水平、工件质量和前道作业装配质量等数据为输入，作业装配质量为输出，构建考虑人员水平的SVR预测模型. 在SVR预测模型基础上构建两阶段循环迭代搜索算法. 算法上层为基于作业编码的禁忌搜索算法，优化作业执行顺序；算法下层在SVR预测模型的基础之上，设计基于人员分配编码的禁忌搜索算法，通过优化人员配置提升作业质量，从而减少作业返工的发生，降低项目整体工期.

2.1 SVR预测模型

SVR的基本原理为将给定的训练数据集映射到高维特征空间，在高维特征空间中寻求一个最优超平面f(x)使得样本点Ym(此处Yim和Xim省略下标i)离超平面的总方差不大于误差ε则为回归无损，即满足|Ym-f(Xm)|≤ε,∀m. SVR标准状态形式为：

图2 多输出目标SVR模型训练及预测过程Fig.2 Training and prediction processes of multi-output SVRmodel

综上所述，多输出SVR预测模型的训练主要包含如下步骤：

步骤1确定训练样本集，向模型中输入样本集中的样本(Xim,Yim).

步骤2利用MOR，针对Yim中的每个偏差值，将Xim映射到高维空间中，并通过求解对偶问题，最终分别得到特征向量Xim对应的Yim中各个目标输出值的超平面参数.

步骤3通过步骤2得到的各个超平面的参数分别建立各目标输出超平面模型.

2.2 两阶段循环迭代搜索算法

鉴于考虑质量预测前摄调度问题耦合了时间和资源两类决策，本文采用两阶段循环迭代搜索算法构建模板计划. 其中，考虑到禁忌搜索算法在求解效率和搜索深度的优势，两阶段算法在上、下两层中均采用禁忌搜索算法来实现时间和资源的决策. 算法上层借鉴陆志强等[2]求解静态RCPSP问题时采用的作业列表编码方法设计禁忌搜索框架对作业执行顺序进行深度搜索；鉴于传统串行调度(serial schedule generation scheme, SSGS)在解码时缺乏对人员合理安排的机制，下层在传统串行调度基础上内嵌人员分配搜索模块，通过对人员分配编码进行深度搜索来获取较优的人员配置情形. 算法整体流程图如图3所示.

图3 两阶段循环迭代搜索算法流程Fig.3 Flow chart of two-level iterative search algorithm

2.2.1 基于作业列表禁忌搜索框架

基于作业列表禁忌搜索框架采用作业列表生成第一阶段的作业执行顺序决策. 作业列表的编码例子如图4a所示，每一编码位的数字代表作业编号，编码过程要求：1)第一个编码位和最后一个编码位分别为虚拟初始作业和虚拟结束作业；2)后一编码位中不得包含前一编码位的直接或间接前道作业. 只有前一编码位的作业被执行完成后，后一编码位的作业才可以安排开始.

图4 邻域生成方法示例Fig.4 Example of neighborhood generation method

初始作业列表通过随机规则生成. 为搜索作业列表的邻域，禁忌搜索框架采用两作业随机邻域生成方法进行单项互换操作，操作过程主要为：首先从当前作业列表中随机选取2个无直接或间接前道关系的作业，并互换两作业在作业列表中的位置(如图4b所示). 每一阶段选取解码后模板计划工期最优的作业列表所对应的互换操作作为下一步移动的禁忌对象，禁忌次数在[tabu1min,tabu1max]间随机生成，设置禁忌搜索最大循环次数为iter1.

算法具体步骤如下：

步骤1令阶段k=1，初始化作业列表Lk. 调用内嵌人员分配搜索模块的串行调度进行解码，获得初始解SLk，令最优解Sbest=SLk.

步骤2调用禁忌搜索框架搜索作业列表的邻域N(Lk). 若列表L′∈N(Lk)未被禁忌，则调用内嵌人员分配搜索模块的串行调度求解；否则跳过该列表.

步骤3找出L*∈N(Lk)具有最小模板计划工期. 若SL*

步骤4令k=k+1，构建新邻域N(Lk)=N(L*).

步骤5若达到终止条件，则输出Sbest；否则，转步骤2.

2.2.2 内嵌人员分配搜索模块串行调度

本文通过人员分配搜索模块对可行的人员组合进行搜索，以获得较优的人员分配方案，并在此基础上通过的串行调度生成模板调度计划. 内嵌人员分配搜索模块的初始人员分配方案通过最高质量水平(highest quality level，HQL)规则生成. 采用HQL规则时，当前作业会被分配当前质量水平最高的装配人员.

为搜索当前人员分配方案的邻域，首先需要选取待调整作业组合(i,j)，其选取的规则为：若作业i、j不存在优先关系约束且两作业的开始时间和结束时间满足STi

将每一阶段解码后模板计划工期最优的装配人员交换操作作为下一步交换操作的禁忌对象，禁忌次数在[tabu2min,tabu2max]间随机生成，设置禁忌搜索最大循环次数为iter2.

算法具体步骤如下：

步骤1输入作业列表L. 记最优模板计划工期为Tbest=M(M为足够大的数).

步骤2令阶段k=1采用HQL规则生成初始装配人员分配方案Ck.

步骤4采用SSGS生成模板计划，记模板计划工期为TCk. 若Tbest>TCk，则令Tbest=TCk.

步骤5令阶段k=k+1，调用人员分配搜索模块搜索人员配置的邻域N(Ck). 若列表C′∈N(Ck)未被禁忌，则调用SVR预测模型预测各作业装配质量，并采用SSGS求解模板计划；否则跳过该列表.

步骤6找出C*∈N(Ck)具有最小模板计划工期. 若Tbest>TC*，则Tbest=TC*.

步骤7令k=k+1，构建新邻域N(Ck)=N(C*).

步骤8若达到终止条件，则输出Tbest；否则，转步骤5.

3 实例应用及分析

3.1 实验平台

本文以某型号支线客机前机身、后机身和机身尾轴装配工位的部分装配流程和历史装配数据为例对算法进行验证. 上述装配流程分别包含21、32和42项装配作业，其中第一和最后道作业为虚拟作业，所涉及的装配人员按水平可划分为高级技工、中级技工和初级技工3类. 本文所有测试实验均运用python3.7编程实现，测试实验在Internet Core i7处理器，3.4GHz主频，8G内存的测试平台上进行.

3.2 SVR预测模型效果验证

为了验证SVR预测模型的准确性，本文分别从上述3个不同规模算例中选取装配作业的历史装配质量信息生成训练样本，并为装配作业建立SVR预测模型. 实验为除虚拟作业外的每一道作业生成M=1 000组训练样本Si={(Xim,Yim)|∀i∈I,m=1,2,...,M}，同时根据2.1节中总结的步骤将其输入模型中进行学习. 经交叉验证后的SVR模型平均准确率可达95%以上. 图5为3个算例S21、S32、S42的预测准确率平均值，其中当装配人员的最高水平为中级时，作业质量预测准确率最低，但与实测值相比误差仍然能够控制在5%以内. 因此，该SVR模型能够较好地用于装配作业质量的预测，为模板调度计划的制定提供可靠的依据.

图5 SVR预测模型准确率Fig.5 Accuracy of SVR prediction model

3.3 两阶段循环迭代搜索算法效果验证

为了有效地评价本文所提出的两阶段循环迭代搜索算法(记为TSD)的有效性，本文基于另外3种生成模板调度计划的方法，通过对作业的实际工件质量添加随机扰动，模拟不同场景下装配线的实际情况，并统一采用右移算法(right shift, RS)来评价各模板计划应对随机扰动时的能力. 其他3种模板调度计划生成方法包括：1)CPLEX. 通过CPLEX软件求解各算例在静态环境下，即不考虑作业发生返工；2)CPLEX-RANDOM. 保留CPLEX软件所得最优调度计划的各作业执行顺序，并采用随机规则为各作业安排装配人员，通过SVR预测模型重新计算各作业执行时间；3)CPLEX-TS. 在CPLEX-RANDOM基础上，增加2.2.2节的人员分配搜索模块优化人员配置.

本文为3个算例S21、S32、S42各生成s=1,2,...,10组实验，每组实验中各作业的工件质量服从正态分布N(ETAsi,σsi|∀s,∀i). 右移算法为实际生产中常用的一种简单有效的修复规则，所有作业顺延至各自前道作业全部完成后开始执行. 每组实验随机扰动次数设为50次. 各模板调度计划应对随机扰动的评价指标包含项目实际工期和作业开始时间偏差两类，其中作业开始时间偏差为

3.3.1 模板调度计划实验结果

CPLEX、CPLEX-RANDOM、CPLEX-TS以及TSD方法所求得的模板调度计划实验结果如表1～3所示，在模板计划工期方面，因为CPLEX仅用到静态环境下的作业执行时间信息，因此其所得Eo值最小且各组别均相等.

相较其他3种方法，TSD求解所得Eo均值最小，CPLEX-TS次之，而采用随机规则进行人员配置的CPLEX-RANDOM最大，其原因为：相比CPLEX-RANDOM，CPLEX-TS可以通过内嵌的人员分配搜索模块优化初期不合理的人员配置，减少作业因质量问题发生返工的情况，进而降低模板调度计划的工期；由于CPLEX-TS延续CPLEX在静态环境中所求得的作业最优执行顺序，而在考虑作业返工的情况下无法保证该执行顺序的最优性. 因此TSD通过基于作业列表禁忌搜索框架进一步优化作业执行顺序，从而获得最小的Eo均值.

表1 S21数值实验结果Tab.1 Numerical results of S21

注：Eo为模板计划工期；G为Eo值与CPLEX方法Eo值之间差距；TCPU为各方法的运算时间，下表同.

表2 S32数值实验结果Tab.2 Numerical results of S32

表3 S42数值实验结果Tab.3 Numerical results of S42

3.3.2 右移算法实验结果

本节实验通过生成工件质量的随机扰动，并采用右移算法获得调整后的装配计划来评价各方法所得模板计划的优劣性. 考虑到CPLEX方法事先未制定人员分配计划，因此在采用右移方法时通过随机规则为其安排装配人员. 右移算法所求得的实验结果如表4～6所示.

在装配计划实际工期方面，虽然CPLEX方法求得的模板计划工期最小，但在随机环境下其平均实际执行工期要大于CPLEX-TS和TSD，其原因在于不合理的人员分配计划导致作业的装配质量降低，从而使得作业返工现象发生频次增加，致使项目整体工期增加；而相较CPLEX-TS，TSD方法能够通过基于作业列表禁忌搜索框架优化作业的执行顺序，降低作业延期对项目整体工期的影响. 在偏差方面，在小规模算例中，CPLEX方法在随机环境下的装配计划偏差最大，CPLEX-RANDOM方法最小. 随着算例规模的增大，TSD方法求得装配计划偏差的增幅最小且在S42算例中为各方法的最小值，而其余方法均有较大的增幅.其原因在于CPLEX方法在生成模板计划时未考虑到作业质量对作业执行时间的影响，因此在随机环境下波动较大的作业实际执行时间使得装配计划偏差快速增加；对于CPLEX-RANDOM、CPLEX-TS和TSD，影响装配计划偏差的因素主要包括模板调度计划的鲁棒性和人员分配的合理性. 在算例规模较小时，模板调度计划的鲁棒性对装配计划偏差影响较大，导致CPLEX-RANDOM求解效果更为理想；随着算例规模的增加，人员分配合理性影响逐渐增大，使得TSD求得的装配计划偏差表现更优.

表4 S21右移算法数值实验结果Tab.4 Numerical results of S21 h

注：Em为调整后装配计划的实际工期；Ed为装配计划与模板装配计划之间各作业开始时间的偏差之和，下表同.

表5 S32右移算法数值实验结果Tab.5 Numerical results of S32 h

表6 S42右移算法数值实验结果Tab.6 Numerical results of S42 h

4 结 论

1)分析装配人员水平、工件质量等因素对实际飞机装配作业质量的影响，构建飞机装配质量在作业间的传递耦合关系，并以历史质量数据为基础构造SVR预测模型. 通过在SVR预测模型中引入多输出回归方法，实现对多维度输出数据的有效表达.

2)针对时间决策和资源决策相互耦合的情况，提出两阶段循环迭代搜索算法. 算法上层在作业列表编码的基础上，通过构建禁忌搜索框架来加强对作业列表的深度搜索能力；算法下层采用串行调度求解作业实际开始时间，并通过内嵌人员分配搜索模块对人员组合进行搜索，实现人员配置的优化.

3)数值实验结果表明,SVR预测模型对实际飞机装配质量的预测具有良好的适用性；两阶段循环迭代搜索算法在随机环境中具有良好的求解性能，说明了该算法的有效性和可行性，能为飞机装配过程构建合理的前摄调度计划.

4)未来可以从动态调度的角度出发，进一步研究零件加工质量和装配人员水平等质量相关因素对飞机动态调度计划的影响.