陆志强,朱宏伟,廖怡娜
(同济大学 机械与能源工程学院, 上海 201804)
摘要:
为有效描述装配人员水平、工件质量等因素对飞机装配作业质量的影响,并为飞机装配过程建立合理的前摄调度计划,提出支持向量回归（SVR）预测模型和两阶段循环迭代搜索算法. 采集相关历史质量数据,以装配人员水平和工件质量等数据为输入,作业质量为输出训练SVR预测模型. 基于已训练的SVR预测模型,采用基于作业列表禁忌搜索框架对作业列表进行邻域搜索,并通过内嵌人员分配搜索模块的串行调度实现人员配置的优化. 数值实验结果表明:采用SVR预测模型求得的作业质量预测值相较实测值的误差能够控制在5%以内,预测精度最高达到97.38%；两阶段循环迭代搜索算法求解所得模板计划与CPLEX偏差均值保持在9.99%~ 27.54%,与其他前摄调度生成方法相比偏差最小；在不确定性环境中,右移算法在两阶段循环迭代搜索算法所得模板计划中能取得最优或次优的平均装配工期和平均计划偏差. SVR预测模型能够对飞机装配作业质量进行有效预测,而两阶段循环迭代搜索算法则能满足构建飞机装配前摄调度计划的需求.
关键词: 飞机装配 质量预测 人员配置 支持向量回归 禁忌搜索
DOI：10.11918/201908116
分类号:F273
文献标识码:A
基金项目:国家自然科学基金(61473211)
Modeling and algorithm for proactive scheduling problem considering quality prediction
LU Zhiqiang,ZHU Hongwei,LIAO Yina
(School of Mechanical and Energy Engineering, Tongji University, Shanghai 201804, China)
Abstract:
To effectively describe the influence of factors such as the assembly personnel level and the workpiece quality on the job quality of aircraft assembly and establish a reasonable proactive schedule for the assembly process, a support vector regression (SVR) prediction model and a two-level iterative search algorithm are developed. Firstly, with collecting relevant historical quality data, a SVR prediction model is trained by taking the data of assembly personnel level, workpiece quality and so on as input and job quality as output. On the basis of the trained SVR prediction model, a job list-based tabu search framework is adopted to search the neighborhood of job list, and the optimization of personnel allocation is achieved through the serial scheduling generation scheme with embedded personnel assignment search module. The results of numerical experiments show that the predicted value of job quality obtained by the SVR prediction model can be controlled within 5% in comparison with the measured value, and the highest prediction accuracy is 97.38%. The mean deviation between the two-level iterative search algorithm and CPLEX is between 9.99% and 27.54%, which is the smallest among proactive scheduling generation methods. In the uncertain environment, the right shift algorithm can obtain the optimal or sub-optimal mean makespan and mean deviation in the baseline schedules obtained by the two-level iterative search algorithm. The SVR prediction model can effectively predict the job quality of aircraft assembly, and the two-level iterative search algorithm can meet the requirement of constructing proactive scheduling for aircraft assembly.
Key words: aircraft assembly quality predication personnel arrangement support vector regression tabu search
陆志强, 朱宏伟, 廖怡娜. 考虑质量预测的前摄调度问题模型与算法[J]. 哈尔滨工业大学学报, 2020, 52(7): 96-104. DOI: 10.11918/201908116.
LU Zhiqiang, ZHU Hongwei, LIAO Yina. Modeling and algorithm for proactive scheduling problem considering quality prediction[J]. Journal of Harbin Institute of Technology, 2020, 52(7): 96-104. DOI: 10.11918/201908116.
基金项目 国家自然科学基金(61473211) 作者简介 陆志强(1968-), 男, 教授, 博士生导师 通信作者 陆志强, zhiqianglu@tongji.edu.cn 文章历史 收稿日期: 2019-08-23
Abstract Full text Figures/Tables PDF
考虑质量预测的前摄调度问题模型与算法
陆志强
, 朱宏伟, 廖怡娜 同济大学 机械与能源工程学院, 上海 201804
收稿日期: 2019-08-23
基金项目: 国家自然科学基金(61473211)
作者简介: 陆志强(1968-), 男, 教授, 博士生导师
通信作者: 陆志强, zhiqianglu@tongji.edu.cn
摘要: 为有效描述装配人员水平、工件质量等因素对飞机装配作业质量的影响, 并为飞机装配过程建立合理的前摄调度计划, 提出支持向量回归(SVR)预测模型和两阶段循环迭代搜索算法.采集相关历史质量数据, 以装配人员水平和工件质量等数据为输入, 作业质量为输出训练SVR预测模型.基于已训练的SVR预测模型, 采用基于作业列表禁忌搜索框架对作业列表进行邻域搜索, 并通过内嵌人员分配搜索模块的串行调度实现人员配置的优化.数值实验结果表明:采用SVR预测模型求得的作业质量预测值相较实测值的误差能够控制在5%以内, 预测精度最高达到97.38%;两阶段循环迭代搜索算法求解所得模板计划与CPLEX偏差均值保持在9.99% ~ 27.54%, 与其他前摄调度生成方法相比偏差最小; 在不确定性环境中, 右移算法在两阶段循环迭代搜索算法所得模板计划中能取得最优或次优的平均装配工期和平均计划偏差. SVR预测模型能够对飞机装配作业质量进行有效预测, 而两阶段循环迭代搜索算法则能满足构建飞机装配前摄调度计划的需求.
关键词: 飞机装配 质量预测 人员配置 支持向量回归 禁忌搜索
Modeling and algorithm for proactive scheduling problem considering quality prediction
LU Zhiqiang
, ZHU Hongwei, LIAO Yina School of Mechanical and Energy Engineering, Tongji University, Shanghai 201804, China
Abstract: To effectively describe the influence of factors such as the assembly personnel level and the workpiece quality on the job quality of aircraft assembly and establish a reasonable proactive schedule for the assembly process, a support vector regression (SVR) prediction model and a two-level iterative search algorithm are developed. Firstly, with collecting relevant historical quality data, a SVR prediction model is trained by taking the data of assembly personnel level, workpiece quality and so on as input and job quality as output. On the basis of the trained SVR prediction model, a job list-based tabu search framework is adopted to search the neighborhood of job list, and the optimization of personnel allocation is achieved through the serial scheduling generation scheme with embedded personnel assignment search module. The results of numerical experiments show that the predicted value of job quality obtained by the SVR prediction model can be controlled within 5% in comparison with the measured value, and the highest prediction accuracy is 97.38%. The mean deviation between the two-level iterative search algorithm and CPLEX is between 9.99% and 27.54%, which is the smallest among proactive scheduling generation methods. In the uncertain environment, the right shift algorithm can obtain the optimal or sub-optimal mean makespan and mean deviation in the baseline schedules obtained by the two-level iterative search algorithm. The SVR prediction model can effectively predict the job quality of aircraft assembly, and the two-level iterative search algorithm can meet the requirement of constructing proactive scheduling for aircraft assembly.
Keywords: aircraft assembly quality predication personnel arrangement support vector regression tabu search
对于飞机、船舶等大型设备装配制造企业而言，建立合理的调度计划是实现管理者高效管理装配过程的重要前提[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.
3) 在飞机装配过程中，装配质量在作业间存在传递耦合效应，即当前作业的装配质量Qi可能与前道作业的装配质量Qipre有关.此外，作业的装配质量还取决于装配人员所具备的最高水平lmax以及工件质量Qipart.可以通过图 1来描述作业质量的传递过程.因此，装配质量Qi可以通过装配人员最高水平lmax、工件质量Qipart和前道作业的装配质量Qipre的函数表达式来描述，即
${{\boldsymbol Q}_i} = F({l_{\rm max }}, {\boldsymbol Q}_i^{\rm part}, {\boldsymbol Q}_i^{\rm pre}).$
Fig. 1
图 1 作业质量传递过程 Fig. 1 Transfer process of job quality 4) 考虑到实际装配作业质量受到上述人员水平等因素的影响，实际装配现场以工件修配等返工的形式来应对作业质量不合格情况的发生.此时，作业质量Qi为作业i实际工期的“因变量”.综合装配人员最高水平lmax、工件质量Qipart和前道作业装配质量Qipre等装配质量影响因素，表达作业i的实际工期
${d_i} = G({l_{\max }}, {\boldsymbol Q}_i^{\rm part}, {\boldsymbol Q}_i^{\rm pre}).$
5) 将时间离散化，记时间集合T={1, 2, ..., z}，t∈T为离散时间节点.
1.2 数学模型基于以上分析，建立问题数学模型如下：
$\min \sum\limits_{t = 1}^T {{x_{It}}{\rm{\cdot}}t, } $ (1)
$s.t.\sum\limits_{t = 1}^T {{x_{jt}}{\rm{\cdot}}t + {d_j} \le } \sum\limits_{t = 1}^T {{x_{it}}{\rm{\cdot}}t, } \;\forall j \in {P_i}, \;\forall i \in I;$ (2)
$\sum\limits_{t = 1}^I {\sum\limits_{t = 1}^{t + {d_i} - 1} {{x_{it}}{\rm{\cdot}}} } {r_{ik}} \le {R_k}, \;\;\forall k \in k;$ (3)
$\sum\limits_{t = 1}^T {{x_{it}} = 1, \;\;} \forall i \in I;$ (4)
$\sum\limits_{t = 1}^I {\sum\limits_{t = 1}^{t + {d_i} - 1} {{x_{it}}{\rm{\cdot}}} } {y_{im}} \le 1, \;\;\forall t \in T, \;\;\forall m \in M;$ (5)
${d_i} = G({l_{\max }}, {\boldsymbol Q}_i^{part}, {\boldsymbol Q}_i^{pre}), \;\;\forall i \in I\;;$ (6)
${x_{it}} = \{ 0, 1\} , \;\;\;i \in I, \;\;\;\forall t \in T;$ (7)
${y_{im}} = \{ 0, 1\} , \;\;\forall \;i \in I, \;\;\;\forall m \in M.$ (8)
式中：m为第m个装配人员；t为离散时间节点；Pi为作业i的前道作业集合；di为作业i实际工期；Qipart为作业i待安装零部件质量；Qipre为影响作业i质量的前道作业质量；决策变量xit代表若作业i在t时刻开始则取1，否则取0；决策变量yim代表若把装配人员m分配给作业i则取1，否则取0.
式(1)表示生成前摄调度计划的目标函数为最小化项目工期；式(2)代表作业间的时序约束，即任一作业不得早于其前道作业结束之前开始；式(3)代表资源约束，即任一时刻资源用量不得多于资源总供应量；式(4)代表作业一旦开始就不能中断；式(5)代表任一装配人员在同一时刻最多只能参与一个作业；式(6)为作业实际工期与人员水平、工件质量及前道作业质量间的映射关系，通过预测模型实现；式(7)和(8)分别代表了xit与yim的取值范围.
2 算法设计针对质量预测前摄调度问题的特点，提出考虑人员水平的SVR预测模型和两阶段循环迭代搜索算法.算法核心包括：结合装配作业历史质量数据，以装配人员水平、工件质量和前道作业装配质量等数据为输入，作业装配质量为输出，构建考虑人员水平的SVR预测模型.在SVR预测模型基础上构建两阶段循环迭代搜索算法.算法上层为基于作业编码的禁忌搜索算法，优化作业执行顺序；算法下层在SVR预测模型的基础之上，设计基于人员分配编码的禁忌搜索算法，通过优化人员配置提升作业质量，从而减少作业返工的发生，降低项目整体工期.
2.1 SVR预测模型设SVR预测模型中任意作业i的特征向量为Xim(其中m=1, ..., M为编号索引)，其对应的实际作业加工质量数据为Yim.其中，Xim={lmax, Qipre, Qipart}，lmax为当前分配给作业i的装配人员所具备的最高水平，Qipart={dipart, sipart, oipart}分别为该作业待装配零件的公称要求、公差和实际误差，Qipre={Δxj1, Δyj1, Δzj1, ..., Δxjn, Δyjn, Δzjn}分别为对当前作业具有最大影响的前道作业j完成后需要进行检测的点1~n在相对于名义坐标上的偏差，Yim={Δxi1, Δyi1, Δzi1, ...Δxin, Δyin, Δzin}分别为作业i实际在Xim的条件下完成后需要进行检测的点1~n在相对于名义坐标的偏差.对于任意作业i，将Si={(Xim, Yim)|m=1, ..., M}作为样本对其相关的SVR模型进行训练和测试.
SVR的基本原理为将给定的训练数据集映射到高维特征空间，在高维特征空间中寻求一个最优超平面f(x)使得样本点Ym(此处Yim和Xim省略下标i)离超平面的总方差不大于误差ε则为回归无损，即满足|Ym－f(Xm)|≤ε, ?m. SVR标准状态形式为：
$\begin{array}{l}\mathop {\min }\limits_{b, \varpi , \xi _m^ \vee , \xi _m^ \wedge } \;\frac{1}{2}{\boldsymbol{\varpi} ^T}\boldsymbol{\varpi} + C\sum\limits_{m = 1}^M {(\xi _m^ \vee + \xi _m^ \wedge )} , \\s.t.\;\;\; - \varepsilon - \xi _m^ \vee \le {{\boldsymbol Y}_m} - {{\boldsymbol \varpi} ^T}{{\boldsymbol X}_m} - b \le \varepsilon + \xi _m^ \wedge , \\\xi _m^ \vee \ge 0, \xi _m^ \wedge \ge 0(m = 1, ..., M).\end{array}$
式中：ω和b为超平面参数，两者共同决定了超平面的位置；C>0为误差惩罚参数，表示对超出误差ε的样本的惩罚程度；ξm∨和ξm∧为松弛因子，当样本划分有误差时，ξ∨m和ξ∧m都大于0.通过引入拉格朗日函数得到原问题的对偶问题：
$\begin{array}{l}\max \sum\limits_{m = 1}^M {(\alpha _m^ \vee - \alpha _m^ \wedge )} {Y_m} - \frac{1}{2}\sum\limits_{m, p = 1}^M {(\alpha _m^ \vee + \alpha _m^ \wedge )} (\alpha _p^ \vee - \alpha _p^ \wedge )k({X_m}, {X_p}) + \varepsilon \sum\limits_{m = 1}^M {(\alpha _m^ \vee + \alpha _m^ \wedge )} , \\s.t.\;\;\;\sum\limits_{m = 1}^M {(\alpha _m^ \vee - \alpha _m^ \wedge )} = 0, \\0 \le \alpha _m^ \vee , \alpha _m^ \wedge \le C(m = 1, ..., M).\end{array}$
式中：am∨、am∧≥0为拉格朗日乘子，K(Xm, Xp)为核函数.由于飞机产品的复杂性以及高度的非线性，因此本文采用高斯径向基函数为核函数.
为了解决传统SVR仅输出单个目标的问题，本文引入多输出回归(multi-output regression，MOR). MOR将原来的多输入多输出样本集合(Xim, Yim)拆分为3n个多输入单输出的子样本集合(Xim, Δxi1), (Xim, Δyi1), ..., (Xim, Δzin)，通过SVR模型对这些子样本集合的学习，分别得到各单一输出对应输入特征向量的3n个超平面.在实际预测中，根据训练时得到的3n个超平面与输入的特征向量逐一得到各输出预测值Δx′i1, Δy′i1, ..., Δz′in，最后将这些预测值进行整合，得到Y′im={Δx′i1, Δy′i1, Δz′i1, ...，Δx′in, Δy′in, Δz′in}，如图 2所示.
Fig. 2
图 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所示.
Fig. 3
图 3 两阶段循环迭代搜索算法流程 Fig. 3 Flow chart of two-level iterative search algorithm 2.2.1 基于作业列表禁忌搜索框架基于作业列表禁忌搜索框架采用作业列表生成第一阶段的作业执行顺序决策.作业列表的编码例子如图 4a所示，每一编码位的数字代表作业编号，编码过程要求：1)第一个编码位和最后一个编码位分别为虚拟初始作业和虚拟结束作业；2)后一编码位中不得包含前一编码位的直接或间接前道作业.只有前一编码位的作业被执行完成后，后一编码位的作业才可以安排开始.
Fig. 4
图 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* < Sbest，则Sbest=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 < STj < FTi或STj < STi < FTj，则作业i和作业j可以组成待调整作业组合(i, j).
对于任意待调整作业组合(i, j)，作业间任意可行的装配人员交换操作都是一次可能的移动.由于装配人员交换操作有多种可能性，为了提升效率，本文将装配人员交换操作限制在待调整作业组合(i, j)中具有最高水平的装配人员M*，即R′i=Ri－Mi*+Mj*，R′j=Rj－Mj*+Mi*.
将每一阶段解码后模板计划工期最优的装配人员交换操作作为下一步交换操作的禁忌对象，禁忌次数在[tabu2min, tabu2max]间随机生成，设置禁忌搜索最大循环次数为iter2.
算法具体步骤如下：
步骤1??输入作业列表L.记最优模板计划工期为Tbest=M(M为足够大的数).
步骤2??令阶段k=1采用HQL规则生成初始装配人员分配方案Ck.
步骤3??调用SVR预测模型预测各作业装配质量，其中工件质量Qipart取对未来工件质量评估的期望值.若作业i装配质量合格，则di=difixed，否则di=difixed+dirework.
步骤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模型能够较好地用于装配作业质量的预测，为模板调度计划的制定提供可靠的依据.
Fig. 5
图 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次.各模板调度计划应对随机扰动的评价指标包含项目实际工期和作业开始时间偏差两类，其中作业开始时间偏差为
$\sum\limits_{i = 1}^I {\left| {S{T_i} - ST_i^{BS}} \right|} .$
其中STi为作业i的实际开始时间，STiBS为作业i在模板调度计划中的开始时间.
相较其他3种方法，TSD求解所得Eo均值最小，CPLEX-TS次之，而采用随机规则进行人员配置的CPLEX-RANDOM最大，其原因为：相比CPLEX-RANDOM，CPLEX-TS可以通过内嵌的人员分配搜索模块优化初期不合理的人员配置，减少作业因质量问题发生返工的情况，进而降低模板调度计划的工期；由于CPLEX-TS延续CPLEX在静态环境中所求得的作业最优执行顺序，而在考虑作业返工的情况下无法保证该执行顺序的最优性.因此TSD通过基于作业列表禁忌搜索框架进一步优化作业执行顺序，从而获得最小的Eo均值.
3.3.1 模板调度计划实验结果CPLEX、CPLEX-RANDOM、CPLEX-TS以及TSD方法所求得的模板调度计划实验结果如表 1~3所示，在模板计划工期方面，因为CPLEX仅用到静态环境下的作业执行时间信息，因此其所得Eo值最小且各组别均相等.
表 1
表 1 S21数值实验结果 Tab. 1 Numerical results of S21 组别CPLEXCPLEX-RANDOMCPLEX-TSTSDEo/h G/% TCPU/s Eo/h G/% TCPU/s Eo/h G/% TCPU/s oE/h G/% CPUT/s
1 34 0 253.85 44 29.41 259.32 40 17.65 259.45 37 8.82 469.40
2 34 0 253.85 39 14.71 259.38 39 14.71 262.87 36 5.88 527.17
3 34 0 253.85 46 35.29 259.24 42 23.53 261.60 37 8.82 560.43
4 34 0 253.85 47 38.24 259.32 44 29.41 262.04 37 8.82 603.47
5 34 0 253.85 46 35.29 259.23 44 29.41 260.75 38 11.76 521.77
6 34 0 253.85 49 44.12 259.26 51 50.00 260.58 39 14.71 562.05
7 34 0 253.85 44 29.41 259.11 44 29.41 261.03 37 8.82 585.86
8 34 0 253.85 46 35.29 259.22 46 35.29 260.96 42 23.53 489.85
9 34 0 253.85 50 47.06 258.87 40 17.65 260.98 35 2.94 623.63
10 34 0 253.85 40 17.65 259.03 40 17.65 262.54 36 5.88 584.40
均值 34 0.00 253.85 45 32.65 259.20 43 26.47 261.28 37 9.99 552.80
注：Eo为模板计划工期；G为Eo值与CPLEX方法Eo值之间差距；TCPU为各方法的运算时间，下表同.
表 1 S21数值实验结果 Tab. 1 Numerical results of S21
表 2
表 2 S32数值实验结果 Tab. 2 Numerical results of S32 组别CPLEXCPLEX-RANDOMCPLEX-TSTSDEo/h G/% TCPU/s Eo/h G/% TCPU/s Eo/h G/% TCPU/s oE/h G/% CPUT/s
1 51 0 431.75 67 31.37 437.25 67 31.37 443.26 56 9.80 618.48
2 51 0 431.75 76 49.02 437.73 74 45.10 447.37 61 19.61 652.90
3 51 0 431.75 68 33.33 437.18 65 27.45 445.19 60 17.65 576.51
4 51 0 431.75 80 56.86 437.58 72 41.18 446.52 67 31.37 645.86
5 51 0 431.75 82 60.78 437.05 82 60.78 443.63 70 37.25 567.48
6 51 0 431.75 64 25.49 437.03 64 25.49 445.26 57 11.76 600.49
7 51 0 431.75 82 60.78 437.22 77 50.98 448.50 69 35.29 699.59
8 51 0 431.75 67 31.37 437.08 67 31.37 445.28 60 17.65 608.46
9 51 0 431.75 70 37.25 437.27 67 31.37 444.17 66 29.41 603.94
10 51 0 431.75 77 50.98 437.31 73 43.14 445.56 65 27.45 631.93
均值 51 0 431.75 73 43.72 437.27 71 38.82 445.47 63 23.72 620.56
表 2 S32数值实验结果 Tab. 2 Numerical results of S32
表 3
表 3 S42数值实验结果 Tab. 3 Numerical results of S42 组别CPLEXCPLEX-RANDOMCPLEX-TSTSDEo/h G/% TCPU/s Eo/h G/% TCPU/s Eo/h G/% TCPU/s oE/h G/% CPUT/s
1 69 0 831.65 99 43.48 842.05 100 44.93 847.03 87 26.09 872.91
2 69 0 831.65 100 44.93 842.22 102 47.83 845.06 87 26.09 717.24
3 69 0 831.65 89 28.99 842.42 85 23.19 847.51 78 13.04 812.58
4 69 0 831.65 105 52.17 842.50 95 37.68 849.37 90 30.43 798.94
5 69 0 831.65 108 56.52 842.57 106 53.62 850.81 90 30.43 861.08
6 69 0 831.65 106 53.62 842.23 98 42.03 847.47 92 33.33 810.64
7 69 0 831.65 106 53.62 841.69 92 33.33 846.06 92 33.33 819.07
8 69 0 831.65 103 49.28 842.06 101 46.38 848.46 89 28.99 864.45
9 69 0 831.65 102 47.83 842.12 101 46.38 847.61 86 24.64 896.27
10 69 0 831.65 108 56.52 841.59 96 39.13 847.19 89 28.99 810.96
均值 69 0 831.65 103 48.70 842.15 98 41.45 847.66 88 27.54 826.41
表 3 S42数值实验结果 Tab. 3 Numerical results of S42
3.3.2 右移算法实验结果本节实验通过生成工件质量的随机扰动，并采用右移算法获得调整后的装配计划来评价各方法所得模板计划的优劣性.考虑到CPLEX方法事先未制定人员分配计划，因此在采用右移方法时通过随机规则为其安排装配人员.右移算法所求得的实验结果如表 4~6所示.
表 4
表 4 S21右移算法数值实验结果 Tab. 4 Numerical results of S21? h组别CPLEXCPLEX-RANDOMCPLEX-TSTSD
Em Ed Em Ed Em Ed Em Ed
1 44.72 98.56 50.06 4.20 44.96 10.08 44.00 26.98
2 53.46 148.10 44.22 8.14 43.68 14.42 41.96 20.70
3 50.76 86.46 46.30 2.76 44.66 11.34 43.16 20.20
4 45.24 92.66 48.68 2.32 46.82 8.66 45.44 23.64
5 40.14 126.60 50.26 10.48 48.82 12.80 45.00 15.44
6 52.66 163.48 49.52 7.80 51.76 9.92 44.84 21.28
7 42.02 52.08 45.18 10.56 45.04 12.74 44.00 24.02
8 44.12 66.74 48.72 9.48 48.72 9.78 47.56 25.76
9 49.34 74.08 50.00 0.48 40.40 4.46 41.00 18.78
10 49.24 103.76 41.18 11.26 41.16 13.50 43.00 16.44
均值 47.17 101.25 47.41 6.75 45.60 10.77 44.00 21.32
注：Em为调整后装配计划的实际工期；Ed为装配计划与模板装配计划之间各作业开始时间的偏差之和，下表同.
表 4 S21右移算法数值实验结果 Tab. 4 Numerical results of S21?
表 5
表 5 S32右移算法数值实验结果 Tab. 5 Numerical results of S32? h组别CPLEXCPLEX-RANDOMCPLEX-TSTSD
Em Ed Em Ed Em Ed Em Ed
1 67.16 338.12 67.56 2.96 67.60 2.64 61.38 17.04
2 76.14 378.90 76.16 4.80 74.50 13.12 66.24 32.80
3 72.36 300.18 70.18 55.20 67.40 61.78 63.84 26.80
4 72.12 327.48 83.62 14.14 74.16 20.60 74.92 16.84
5 78.22 438.62 83.26 20.10 82.76 15.72 77.80 28.24
6 75.54 334.48 65.86 57.60 66.22 55.44 62.08 18.10
7 79.60 417.12 82.88 5.72 77.44 12.96 75.42 20.32
8 69.88 282.68 69.88 29.36 69.76 26.72 65.56 22.56
9 68.26 191.54 70.38 6.28 67.06 6.72 67.21 16.60
10 74.10 299.64 77.24 0.72 73.32 1.22 68.00 15.34
均值 73.34 330.88 74.70 19.69 72.02 21.69 68.25 21.46
表 5 S32右移算法数值实验结果 Tab. 5 Numerical results of S32?
表 6
表 6 S42右移算法数值实验结果 Tab. 6 Numerical results of S42? h组别CPLEXCPLEX-RANDOMCPLEX-TSTSD
Em Ed Em Ed Em Ed Em Ed
1 97.04 593.26 99.20 7.82 100.50 12.26 92.00 19.22
2 96.78 584.58 104.22 113.68 103.08 38.76 98.00 38.00
3 85.34 355.66 90.86 23.90 87.94 70.80 83.56 31.46
4 106.92 577.12 105.00 5.72 95.50 5.16 95.24 34.56
5 102.74 712.58 109.98 75.48 107.22 56.62 94.42 20.00
6 115.90 686.62 107.96 28.70 100.16 46.26 103.00 24.28
7 87.04 349.20 110.06 38.68 94.06 43.30 96.00 32.12
8 94.60 549.40 107.34 30.60 101.56 6.90 94.52 26.06
9 107.00 721.44 102.28 7.90 101.48 10.74 96.00 22.00
10 99.04 388.40 109.82 25.12 99.78 39.68 96.00 27.06
均值 99.24 551.83 104.67 35.76 99.13 33.05 94.87 27.48
表 6 S42右移算法数值实验结果 Tab. 6 Numerical results of S42?
在装配计划实际工期方面，虽然CPLEX方法求得的模板计划工期最小，但在随机环境下其平均实际执行工期要大于CPLEX-TS和TSD，其原因在于不合理的人员分配计划导致作业的装配质量降低，从而使得作业返工现象发生频次增加，致使项目整体工期增加；而相较CPLEX-TS，TSD方法能够通过基于作业列表禁忌搜索框架优化作业的执行顺序，降低作业延期对项目整体工期的影响.在偏差方面，在小规模算例中，CPLEX方法在随机环境下的装配计划偏差最大，CPLEX-RANDOM方法最小.随着算例规模的增大，TSD方法求得装配计划偏差的增幅最小且在S42算例中为各方法的最小值，而其余方法均有较大的增幅.其原因在于CPLEX方法在生成模板计划时未考虑到作业质量对作业执行时间的影响，因此在随机环境下波动较大的作业实际执行时间使得装配计划偏差快速增加；对于CPLEX-RANDOM、CPLEX-TS和TSD，影响装配计划偏差的因素主要包括模板调度计划的鲁棒性和人员分配的合理性.在算例规模较小时，模板调度计划的鲁棒性对装配计划偏差影响较大，导致CPLEX-RANDOM求解效果更为理想；随着算例规模的增加，人员分配合理性影响逐渐增大，使得TSD求得的装配计划偏差表现更优.
4 结论1) 分析装配人员水平、工件质量等因素对实际飞机装配作业质量的影响，构建飞机装配质量在作业间的传递耦合关系，并以历史质量数据为基础构造SVR预测模型.通过在SVR预测模型中引入多输出回归方法，实现对多维度输出数据的有效表达.
2) 针对时间决策和资源决策相互耦合的情况，提出两阶段循环迭代搜索算法.算法上层在作业列表编码的基础上，通过构建禁忌搜索框架来加强对作业列表的深度搜索能力；算法下层采用串行调度求解作业实际开始时间，并通过内嵌人员分配搜索模块对人员组合进行搜索，实现人员配置的优化.
3) 数值实验结果表明, SVR预测模型对实际飞机装配质量的预测具有良好的适用性；两阶段循环迭代搜索算法在随机环境中具有良好的求解性能，说明了该算法的有效性和可行性，能为飞机装配过程构建合理的前摄调度计划.
4) 未来可以从动态调度的角度出发，进一步研究零件加工质量和装配人员水平等质量相关因素对飞机动态调度计划的影响.
参考文献
[1] BROWNING T R, YASSINE A A. Resource-constrained multi-project scheduling: priority rule performance revisited[J]. International Journal of Production Economics, 2010, 126(2): 212. DOI:10.1016/j.ijpe.2010.03.009
[2] 陆志强, 杨超. 基于项目网络拆分决策的多项目协同调度问题建模[J]. 上海交通大学学报, 2017, 51(2): 193.
LU Zhiqiang, YANG Chao. Modeling of resource constrained multi-project scheduling problem based on project splitting[J]. Journal of Shanghai Jiaotong University, 2017, 51(2): 193. DOI:10.16183/j.cnki.jsjtu.2017.02.010
[3] 朱宏伟, 陆志强. 考虑资源转移时间的项目可拆分资源受限多项目调度问题[J]. 计算机集成制造系统, 2019, 25(3): 586.
ZHU Hongwei, LU Zhiqiang. Modeling and improved algorithm for resource constrained multi-project scheduling problem based on project splitting with resource transfer time[J]. Computer Integrated Manufacturing Systems, 2019, 25(3): 586. DOI:10.13196/j.cims.2019.03.006
[4] CHEN Rong, LIANG Changyong, GU Dongxiao, et al. A multi-objective model for multi-project scheduling and multi-skilled staff assignment for IT product development considering competency evolution[J]. International Journal of Production Research, 2017, 55(21): 6207. DOI:10.1080/00207543.2017.1326641
[5] ELSAYED S, SARKER R, RAY T, et al. Consolidated optimization algorithm for resource-constrained project scheduling problems[J]. Information Sciences, 2017, 418/419: 346. DOI:10.1016/j.ins.2017.08.023
[6] BIBIKS K, HU Y F, LI J P, et al. Improved discrete cuckoo search for the resource-constrained project scheduling problem[J]. Applied Soft Computing, 2018, 69: 493. DOI:10.1016/j.asoc.2018.04.047
[7] KE Hua, WANG Lei, HUANG Hu. An uncertain model for RCPSP with solution robustness focusing on logistics project schedule[J]. International Journal of e-Navigation and Maritime Economy, 2015, 3: 71. DOI:10.1016/j.enavi.2015.12.007
[8] 崔南方, 赵雁, 胡雪君. 鲁棒性项目调度中缓冲设置方法[J]. 控制与决策, 2014, 29(2): 368.
CUI Nanfang, ZHAO Yan, HU Xuejun. Buffer management in robust project scheduling[J]. Control and Decision, 2014, 29(2): 368. DOI:10.13195/j.kzyjc.2012.1605
[9] 徐小峰, 郝俊, 邓忆瑞. 考虑多因素扰动的项目关键链缓冲区间设置及控制模型[J]. 系统工程理论与实践, 2017, 37(6): 1593.
XU Xiaofeng, HAO Jun, DENG Yirui. Project critical chain buffer setting and control model considered multiple factors disturbance[J]. Systems Engineering Theory and Practice, 2017, 37(6): 1593. DOI:10.12011/1000-6788(2017)06-1593-09
[10] CHAKRABORTTY R K, SARKER R A, ESSAM D L. Resource constrained project scheduling with uncertain activity durations[J]. Computers & Industrial Engineering, 2017, 112: 537. DOI:10.1016/j.cie.2016.12.040
[11] AL-FAWZAN M A, HAOUARI M. A bi-objective model for robust resource-constrained project scheduling[J]. International Journal of Production Economics, 2005, 96(2): 175. DOI:10.1016/j.ijpe.2004.04.002
[12] ABBASI B, SHADROKH S, ARKAT J. Bi-objective resource-constrained project scheduling with robustness and makespan criteria[J]. Applied Mathematics & Computation, 2006, 180(1): 146. DOI:10.1016/j.amc.2005.11.160
[13] TIWARI V. Scheduling projects with heterogeneous resources to meet time and quality objectives[J]. European Journal of Operational Research, 2009, 193(3): 780. DOI:10.1016/j.ejor.2007.11.005
[14] MAGHSOUDLOU H, AFSHAR-NADJAFI B, NIAKI S T A. Multi-skilled project scheduling with level-dependent rework risk: three multi-objective mechanisms based on cuckoo search[J]. Applied Soft Computing, 2017, 54: 46. DOI:10.1016/j.asoc.2017.01.024
[15] 刘伟东, 宁汝新, 刘检华, 等. 机械装配偏差源及其偏差传递机理分析[J]. 机械工程学报, 2012, 48(1): 156.
LIU Weidong, NING Ruxin, LIU Jianhua, et al. Mechanism analysis of deviation sourcing and propagation for mechanical assembly[J]. Journal of Mechanical Engineering, 2012, 48(1): 156. DOI:10.3901/JME.2012.01.156
[16] 江平宇, 王岩, 王焕发, 等. 基于赋值型误差传递网络的多作业加工质量预测[J]. 机械工程学报, 2013, 49(6): 160.
JIANG Pingyu, WANG Yan, WANG Huanfa, et al. Quality prediction of multistage machining processes based on assigned error propagation network[J]. Journal of Mechanical Engineering, 2013, 49(6): 160. DOI:10.3901/JME.2013.06.160
[17] DI PASQUALE V, MIRANDA S, NEUMANN W P, et al. Human reliability in manual assembly systems: a systematic literature review[J]. IFAC PapersOnLine, 2018, 51(11): 675. DOI:10.1016/j.ifacol.2018.08.396
[18] 唐文斌.飞机非线性装配偏差分析与容差协同分配方法研究[D].西安: 西北工业大学, 2015
TANG Wenbin. Non-linear assembly deviation analysis and tolerance co-allocation for aircraft[D]. Xi'an: Northwestern Polytechnical University, 2015
[19] RUI Jianwen, ZHANG Hongbing, ZHANG Dailu, et al. Total organic carbon content prediction based on support-vector-regression machine with particle swarm optimization[J]. Journal of Petroleum Science and Engineering, 2019, 180: 699. DOI:10.1016/j.petrol.2019.06.014
