基于质量预测的飞机装配动态调度问题研究

陆志强 朱宏伟 廖怡娜

摘   要：为提高飞机装配调度计划应对装配质量不合格的能力，首先以两阶段近似动态决策为框架，研究装配质量与相关因素的映射关系和不确定性因素在不同决策周期的表现形式，并以最小化基于场景的项目工期期望值为目标函数建立整数规划模型;然后基于构建的飞机装配质量预测模型，设计了多层循环迭代搜索算法，算法第一层基于任务列表的编码方式优化任务执行顺序，第二层通过装配人员分配列表优化人员配置，第三层根据人员配置结果求解目标函数. 数值实验结果显示在工件质量预测值与实际值不一致的情况下，多层循环迭代搜索算法在任务开始时间偏差能够保持在2以下，表明该算法能够适应不确定性因素的变化，满足构建飞机装配动态调度计划的需求.

关键词：飞机装配;动态调度;人员配置;质量预测;多层循环迭代搜索算法

中图分类号：F273                                   文献标志码：A

Dynamic Scheduling Problem of Aircraft

Assembly Based on Quality Prediction

LU Zhiqiang?，ZHU Hongwei，LIAO Yina

（School of Mechanical and Energy Engineering，Tongji University，Shanghai 201804，China）

Abstract：To improve the ability of aircraft assembly schedule to deal with unqualified assembly quality，the mapping between assembly quality and quality-related factors and the expression of uncertainty in different decision-making cycles are studied，and the integer programming model is established with the objective function of the scenario-based project expected value. Moreover，based on the trained prediction model of aircraft assembly quality，a multi-layer cyclic iterative search algorithm is designed. The first layer optimizes the execution order of activity based on the activity list coding; The second layer optimizes the personnel allocation through the assembler allocation list; The third layer solves the objective function according to the result of personnel allocation. The numerical results show that the multi-layer cyclic iterative search algorithm can keep the deviation of activity start time below 2 when the predicted workpiece quality is inconsistent with the actual value，which indicates that it is adaptable to the changes of uncertainty factors and can meet the requirements of constructing dynamic schedules for aircraft assembly.

Key word：aircraft assembly;dynamic scheduling;personnel allocation;quality prediction;multi-layer iterative search algorithm

對飞机等大型设备装配制造企业而言，建立合理的装配调度计划是有效提高装配效率的途径之一[1]. 许多因素影响着调度计划的制定，包括各类资源供给限制、任务间的时序约束以及装配过程中出现的各种不确定性因素等. 目前，已有学者对飞机装配调度及相关衍生问题开展研究. 对于确定性问题，Lu[2]和朱宏伟[3]等认为飞机装配过程主要涉及资源约束和任务顺序关系两类确定性约束，因此可以将飞机装配调度问题抽象为资源受限项目调度问题（resource constrained project scheduling problem，RCPSP）及其扩展问题，并且可以通过构建启发式或元启发式算法[4-5]对问题进行有效求解. 在不确定性问题方面，现有研究主要涉及资源和任务相关的不确定性因素，包括物料到达不确定、任务工期不确定以及装配质量缺陷等[6-8]. 其中，廖怡娜等[9]考虑任务因质量缺陷而导致的返工对计划变动性的影响，以最小化项目工期与任务开始时间变动性为目标构建问题模型. 处理不确定性问题的方法主要包含反应式调度和前摄调度两类，其中前摄调度通过添加时间或资源缓冲来提升前摄调度计划的鲁棒性，以预防不确定性事件导致的计划中断[10].

实际上，各质量相关因素对装配或加工质量的影响以质量偏差传递过程的形式体现，而两者的映射关系可以通过质量预测模型来建立. 贾峰等[11]采用复杂网络建模理论构建叶片加工误差传递网络，以说明误差在加工特征和工况要素间的传递过程. 王秋明等[12]通过灰色理论和反向传播神经网络实现各工序的质量预测. 鞠萍华等[13]提出一种基于GRA和AHP的广义回归神经网络零件失效概率预测方法.

飞机装配周期长，与资源、任务相关的不确定性因素随着装配进程的推进不断变化，因此实际管理上更适合采用周期性的决策框架构建调度计划，其中包括滚动时域法. Lee等[14]以滚动时域为框架解决短期调度问题. 张洁等[15]针对工时不确定的混合流水车间动态调度问题，提出基于交货期偏差容忍度的滚动时域框架.

综观现有研究发现，现有调度方法往往在不确定性事件发生后进行被动处理且仅利用决策初期的信息，从而忽略了主动改善的优势，同时也无法有效应对装配过程中不确定因素不断改变的情况.现有文献虽然已经对质量偏差传递机理和预测方法进行了详细的分析，但实际上，装配人员的技能水平在很大程度上影响着飞机装配的可靠性与稳定性，是产生质量缺陷的重要原因之一[16]，因此现有研究与真实的飞机装配质量传递过程仍存在偏差. 滚动时域法则仅利用各决策点上的确定性信息，没有充分考虑到不确定性因素对计划构建的影响，而韩笑乐等[17]提出基于两阶段近似的动态决策框架能够充分利用未来不确定性场景来辅助评价当前决策优劣，提升调度计划应对未来不确定性因素的能力.

针对上述不足，本文分析了包括装配人员技能水平在内的质量因素对任务装配质量影响情况，建立飞机装配质量映射关系和预测模型;以此为基础，结合两阶段近似的动态决策框架，研究包括工件质量在内的不确定性因素对当前决策周期飞机装配调度计划构建的影响形式，建立基于不确定性场景的混合整数规划模型;最后，针对问题多阶段的特性，以禁忌搜索为框架构建多层循环迭代搜索算法进行求解.

1   问题描述及数学模型

1.1   问题描述

飞机装配涉及的零部件多种多样、数量庞大且工艺复杂，装配任务的完工质量是否能够达到规定标准除了与当前任务的待装配零部件质量、前序任务的完工质量有关以外，装配人员的技能水平也是影响质量的重要因素之一[13]，因此，在本文的研究中，将装配人员技能水平l作为影响任务质量的主要因素之一，使其与待装配零部件质量Qpart、前序任务完工质量Qpre一同决定各飞机装配任务的完工质量，并以此为基础对装配项目进行调度.

由于飞机装配周期较长，因此在实际的装配项目中，装配中心往往需要对供应链上的一系列因素，包括仓库的存储能力及费用、订货费用和订货次数等进行综合考量，制定合理的零部件采购计划，使得待装配零部件按照一定时间从供应商处分批次运送至装配中心进行加工制造，因此装配项目中各任务的待装配零部件质量状况通常无法在项目开始前全部知晓，而是随着装配项目的推进逐渐明确、又基于前文可知，待装配零部件质量Qpart是影响各装配任务完工质量的主要因素之一，因而装配项目中各任务的实际装配质量将随着待装配零部件质量的已知进而确定.

韩笑乐等[17]基于船舶调度背景提出的集装箱进出口码头泊位-堆场协同分配的动态决策问题与本文研究问题具有诸多共性：首先从目标来说，两者均是在特定背景下试图得到较优的调度结果;其次，两者均具备进行周期划分的条件，前者假设每一周期内部分船舶的确切到港时间可提前已知，后者则基于实际情况假设各装配任务的待装配零部件分批次到达，零部件到达后其质量情况才能够已知;然后在调度因素方面，前者需要对码头和堆场资源进行协同决策，后者则需要对装配任务的开始时间、包括装配人员在内的可更新资源进行联合分配;最后，后续不确定性场景均对两者的调度计划产生影响，对前者则影响整体调度计划中的船舶在港总时间，对后者则影响整体调度计划的项目工期. 基于上述共性，参考韩笑乐等[17]提出的两阶段近似的动态决策框架，对本文研究问题进行抽象.

综合上述分析，本文在两阶段近似动态决策框架的基础上，将任务质量引入调度决策中，考虑后续不确定性场景对整体调度计划的影响，得到滚动时域框架下基于任务质量预测的飞机装配动态调度问题，该问题具体描述如下.

装配项目J中包含n个装配任务i∈J和m种资源k∈K;任务的工期为d，与任务的完工质量有关，将在后文中详述;单位时间内消耗各类资源量为r，每种资源任意时刻供给上限记为R;各任务之间存在时序关系，任务一旦开始就不允许中断. 将整个装配过程分成多个阶段进行决策，同时装配任务可以根据其零部件质量状况Qpart在决策时间点处是否已知进行区分. 对于在决策时间点处零部件质量未知的任务，其零部件质量状况存在多种不同情况，可表示为多个不确定性场景. 如图1所示，在飞机装配动态决策问题中，在任一决策點对任务进行调度时可分为两个阶段，第一阶段是对当前决策阶段中的各个任务进行安排，为固定性决策;第二阶段是对后续决策阶段的各个任务进行安排，为调整决策. 由于后续决策阶段中存在多个不确定性场景，因此调整决策为临时的，仅用于辅助评估第一阶段的固定性决策. 固定决策阶段和调整决策阶段分别针对不同的任务进行调度，在任一决策时间点，可将各任务分为A、B、C 3类，对于不同类别的任务，将其归于上述不同的决策阶段. 各类任务分类信息及其与不同决策阶段之间的关系如下：

1）已开始任务（A类任务）. 对于该类任务，已知的确定参数包括：任务执行时间dA、装配人员需求rA、工件质量情况Qpart，A、任务开始时间xA和装配人员分配情况yA. 该类任务无不确定参数，无需决策，仅需按照事先制定的计划完成剩余任务即可.

2）可在当前决策周期内开始执行的任务（B类任务）. 已知的确定参数包括：装配人员需求情况rB和工件质量情况Qpart，B. 可根据是否延迟到当前周期后执行而分为B0类和B1类任务. 对于B0类任务需进行第一阶段的固定性决策，包括为其分配具体的任务开始时间xB0和装配人员分配情况yB0，并通过装配质量映射关系间接确定其任务执行时间工期dB0. 对于B1类任务，由于其保留在下一周期再次决策的机会，因此进行第二阶段的调整性决策，具体决策过程与C类任务相似.

3）在当前决策周期k后开始执行的任务（C类任务）. 已知的确定参数为装配人员需求情况rC，不确定参数为各场景下的工件质量情况Qpart，C

m         . 此时需要进行第二阶段各场景下的调整决策，包括与场景相关的任务开始时间xC

m和装配人员分配情况yC

m. 调整决策在决策点k+1处仍有进一步调整的机会.

如前文所述，任意装配任务i的完工质量由3个因素决定，分别为装配人员技能水平l、待装配零部件质量Qpart以及前序相关任务完工质量Qpre. 其中，由于任务间的时序约束以及传递耦合效应，使得当前装配任务i的装配质量受到前序相关任务的完工质量Qpre的影响，同时质量情况也通过任务时序网络进行传递，任务完工質量传递关系如图2所示. 为了提升算法搜索效率，对研究问题进行了简化，对于装配人员技能水平因素，当前装配任务i所配备的装配人员集合中具备最高技能水平的装配人员对任务质量起主要作用，并将所配备的最高技能水平记为lmax . 另外，在实际情况下，由于飞机装配质量的传递过程具有高度非线性，任务完工质量和影响质量状况的因素之间的具体关系通常不存在显式表达，在本文中，将通过SVR机器学习模型结合上述3种影响因素对各任务完工质量进行预测，因此，任意任务的完工质量与3种影响因素之间的映射关系表示为Q = f（lmax，Qpart，Qpre）.

装配任务的质量情况是本文研究问题中影响调度计划的不确定性因素，其对调度计划的影响在于装配质量的不合格会引起任务工期d的变化，具体而言，若装配任务完工质量合格，则其实际工期仅为提前已知的正常执行工期，即d = dflxed;若装配任务完工质量不合格，为了保证其后续任务的质量，需要对当前质量不合格的装配任务进行返工，表现为在原本正常执行工期的基础上添加一段返工工期drework，此时，当前任务的实际工期为d = dflxed + drework. 又基于上述任务完工质量Q是由所配备的装配人员具有的最高技能水平lmax、待装配零部件质量状况Qpart和前序相关任务完工质量Qpre 3因素决定的，故任务实际工期d与这3种质量影响因素之间的关系可表示为d = F（lmax，Qpart，Qpre）.

1.2   数学模型

参数：

Cm：场景[ω] 中的装配项目工期;

i∈I = {1，…，I }：装配人员集合;

r∈R = {1，…，R}：资源集合，其中装配人员集合为资源集合的子集，即M?R;

k∈K = {1，…，K}：资源种类集合;

l∈L = {1，…，L}：装配人员水平集合;

t∈T = {1，…，T}：离散化的时间段集合;

[ω] ∈Ω = {1，…，Ω}：场景集合;

Pi：任务i的紧前任务集合;

di：场景[ω] 中任务i的实际装配时间;

IA，IB，IC：3类任务的子集合;

Qpart

i    ：任务i待安装零部件质量;

Qpre

i    ：影响任务i质量的前道任务质量.

决策变量：

xit，ω：场景[ω] 中，若任务i在t时刻开始则取1，否则取0;

yim，ω：场景[ω] 中，若把装配人员m分配给任务i则取1，否则取0;

ui：若任务i∈IB且任务被延迟至周期k之后开始执行则取1，否则=0.

模型：

其中目标函数（1）为最小化决策点时各场景下的项目工期期望值;约束（2）确保任一任务的开始时间不早于其前序任务的结束时间;约束（3）为资源约束;约束（4）代表任务开始后不允许中断;约束（5）限制任意装配人员在某时刻最多操作一个任务;由于飞机装配传递过程的高度非线性导致装配质量和影响其的3个因素之间的具体关系未知，因此通过约束（6）（7）表示装配质量、任务实际工期与人员水平、工件质量及紧前任务质量间的映射关系，装配任务的完工质量将通过预测模型实现;约束（8）～（14） 确保各类别任务在不同场景下决策的一致性;（15）～（17）代表了决策变量的取值范围.

2   算法描述

为适用飞机装配动态决策问题存在多阶段决策的情况，本文依据问题模型特点和决策逻辑，提出多层循环迭代搜索算法. 算法主要思路为：结合装配任务历史质量数据，以装配质量相关参数为输入、装配质量为输出，构建飞机装配质量预测模型. 以飞机装配质量预测模型为基础，构建多层循环迭代搜索算法. 算法第一层基于任务列表的编码方式，以禁忌搜索算法为框架优化任务执行顺序;第二层通过设计装配人员分配列表的编码方式完成第一阶段固定性决策;第三层仍采用任务列表编码方式搜索第二阶段调整性决策，并通过计算各场景下的项目工期均值来评价整体决策的优劣性. 具体步骤在2.1节和2.2节中详细阐述.

2.1   飞机装配质量预测模型

如第1节中所描述，飞机装配质量受到包括装配人员分配情况、工件质量等多方面因素综合的影响，因此需要构建有效的预测模型来准确描述装配质量传递效应. 考虑到飞机质量传递过程具有高度的非线性[18]以及支持向量回归（SVR）在非线性预测领域的适用性[19]，本文采用支持向量回归（SVR）构建飞机装配质量预测模型.

基于前文分析，任务质量状况由该任务所配备装配人员具备的最高技能水平lmax、待装配零部件质量情况Qpart以及前序相关任务质量状况Qpre决定，因此将该3种质量影响因素作为质量预测模型的输入，当前任务完工质量状况作为质量模型的输出构建质量预测模型样本，进而建立用于装配任务完工质量预测的SVR支持向量回归模型. 质量预测模型样本构成具体为：对于任意任务i，记样本为Si = {（Xim，Yim）}（其中m = 1，…，M为编号索引）. 其中Xim = {lmax，Qpre

i    ，Qpart

i     }为输入向量，lmax表示任务i所分配装配人员的最高水平，Qpart

i     = {dpart

i     ，spart

i     ，opart

i     } 表示装配任务所需工件的公称要求、公差和实际误差，Qpre

i    = {Δxj1，Δyj1，Δzj1，…，Δxjn，Δyjn，Δzjn}表示对当前任务具有最大影响的紧前任务j在检测点1 ～ n上测量所得相對于名义坐标的偏差;Yim = {Δxi1，Δyi1，Δzi1，…，Δxin，Δyin，Δzin}为输出向量，表示实际情况下任务i以Xim为质量传递输入时在检测点1 ～ n上测量所得相对于名义坐标的偏差.

SVR的基本原理为根据给定的训练数据集在高维特征空间中寻求一个最优超平面，使得所有样本点离超平面的总方差不大于预先给定的误差. 此外，为适用飞机装配质量为多个输出值的情况，本文引入多输出回归，将原来的多输入多输出样本集合（Xim，Yim）拆分为3n个多输入单输出的子样本集合（Xim，Δxi1），（Xim，Δyi1），…，（Xim，Δzin），通过SVR模型对这些子样本集合的学习，分别得到各单一输出对应输入特征向量的3n个超平面. 最后通过测试样本对训练所得SVR模型进行预测准确性的检测. 飞机装配质量预测模型训练及预测过程可由图3表示.

2.2   多层循环迭代搜索算法

不同于以往飞机调度问题决策过程，以下两类特点使得本问题的决策难度显著提升：不同装配人员之间的水平分级使得本问题在保留以往飞机调度问题中所涉及的时间决策的基础上，进一步耦合了资源决策需求;于此同时，相较于单场景模型，基于场景的混合整数规划模型进一步扩大了各决策时间点上的决策规模. 因此，本文采用多层循环迭代搜索算法在各决策时间点上构建装配计划. 其中，鉴于禁忌搜索算法在邻域搜索及求解效率的优势，多层循环迭代搜索算法各层均采用禁忌搜索算法作为算法框架. 具体而言，算法第一层（TS1）借鉴陆志强等[20]所采用的任务列表编码方式对任务执行顺序展开搜索;算法第二层（TS2）采用装配人员分配编码方式构建人员分配搜索模块，搜索可能的人员配置情形，并在此基础上通过串行调度算法区分B0、B1和C类任务;算法第三层（TS3）基于TS2任务区分的基础上，在各场景下搜索较优调度计划，计算调度计划的评价指标. 多层循环迭代搜索算法框架如图4所示.

计算各场景的评价目标均值作为

L2′评价目标值输出][串行调度解码，选择最小工期

作为场景θ评价目标值][获得L1′评价目标值][选择具有最优评价目标值的L1*∈N（Lk）][基于任务列表编码禁忌搜索算法（TS1）][初始化优先级列表L1][基于人员分配编码禁忌搜索算法（TS2）][是][否][生成邻域N（L1）][选择L′

2.2.1   TS1：基于任务列表编码禁忌搜索算法

任务列表编码用于算法第一层TS1中的任务执行顺序决策. 任务列表编码包括A类任务和B、C类任务两类任务集合，图5（a）给出编码的示例. 其中，每一编码位的数字代表任务编号，编码过程要求：1）虚拟开始任务和虚拟结束任务分别放入最开始的码位和最后的码位;2）后一码位中的任务与前一码位中的任务不能为直接或间接紧前关系;3）由于A类船无需决策，因此A类船置于列表中最高的优先级位置;4）B、C类任务具有等效的优先程度，因此在任务列表中混编. 初始任务列表由随机规则产生.

TS1中禁忌搜索算法的邻域通过选取编码中两个B、C类任务并对其进行单项互换操作来实现，其主要过程包括：从当前任务列表的B、C类任务中随机选取两个不存在直接或间接紧前关系的任务，对两任务在列表中的位置进行互换. 图5（b）给出单项互换操作的示例. TS1每一阶段的禁忌对象为通过TS2和TS3解码后评价指标最优的任务列表所对应的单项互换操作. 设置禁忌搜索算法的最大循环次数为iter1，禁忌次数在上限tabumax

1     和下限tabumin

1     间随机生成.

2.2.2   TS2：基于人员分配编码禁忌搜索算法

不同的人员分配方案不仅会影响任务执行时间，同时也会间接的影响B0、B1和C类任务的划分情况. 因此，本文设计人员分配编码用于人员分配方案的决策. 初始人员分配编码通过最高人员水平（highest quality level，HQL）规则生成. 采用HQL规则时，待安排任务会被分配剩余装配人员集合中装配水平最高的人员. 人员分配编码过程为：从待调整的任务集合中随机选取待调整任务组合 （i，j），其中必须保证任务i、 j之间不存在紧前关系且两任务的开始和结束时间满足STi < STj < FTi或STj < STi < FTj（如图6（a）所示）.

邻域生成通过对待调整任务组合（i，j）间的装配人员交换操作实现，其中考虑到潜在的人员交换操作有很多，因此本文仅考虑任务组合（i，j）的最高水平装配人员M *交换操作，即R′

i. TS2每一阶段的禁忌对象为通过TS3解码后最优评价指标所对应的人员交换操作. 设置禁忌搜索算法的最大循环次数为iter2，禁忌次数在上限tabumax

2     和下限tabumin

2     间随机生成.

2.2.3   TS3：基于任务列表编码评价目标生成算法

评价目标的生成算法同样采用任务列表为编码方式，使用HQL规则生成人员分配方案. 在由TS1所构建的任务列表和TS2所构建的人员分配列表生成最终评价目标时，基于任务列表编码评价目标生成算法首先对在各场景ω下由B1和C类船构成的部分列表进行单项互换操作，然后采用基于HQL规则的串行调度算法求解该场景下的较优项目工期，最后通过求解所有场景下的项目工期期望来获得评价目标.

TS3中单项互换操作与TS1中类似，各场景ω下的禁忌对象为上一步移动的互换操作. 设置禁忌搜索算法的最大循环次数为iter3，禁忌次数在上限tabumax

3     和下限tabumin

3     间随机生成.

3   数值实验

3.1   测试环境

为验证所提决策框架的有效性，以某型号支线客机前机身、后机身和机身尾轴装配工位的部分装配流程和历史装配数据构建实验算例. 上述装配流程所包含装配任务数量分别为21、32和42项，所构建算例分别记为C21、C32和C42. 装配过程所涉及装配人员的技能水平可划分为高级、中级和初级3种. 上述质量预测模型和各对比算法均通过python3.7编程实现，数值实验在Internet Core i7处理器，3.4 GHz主频，16 G内存的计算平台上进行.

3.2   飞机装配质量预测模型效果验证

从上述C21、C32和C42 3类算例中选取装配任务的历史装配质量信息构建预测模型训练样本和测试样本，并通过交叉验证法对比装配质量预测值与实际值间的偏差，以验证飞机装配质量预测模型的准确性. 模型训练过程为每一道任务（除去虚拟任务）生成M = 1 000组训练样本Si = {（Xim，Yim）|?i∈I，m =1，2，…，M }，并按照图2中的步骤训练SVR模型. 选取5折为交叉验证法折数. 此外，为进一步说明SVR预测的适应性，将SVR与BP神经网络[21]预测准确率进行对比.

预测准确率均值如表1所示. 在所有算例中，SVR在任意技能水平所对应装配质量预测准确率经交叉验证后可以达到95%以上，远优于BP神经网络的预测准确率. 可以看出，本文所构建的飞机装配质量预测模型能够比较准确地根据质量输入信息对任务装配质量进行预测.

3.3   多层循环迭代搜索算法效果验证

为了验证周期性决策框架的适用性以及多层循环迭代搜索算法（记为TSM）的有效性，本文采用预设的质量分布参数构建实际工件质量场景，并提出另外3种调度计划生成算法作为对照，对比各调度计划生成算法所建调度计划应对随机扰动的能力. 设多层循环迭代搜索算法的决策周期跨度p = 10. 其他3种调度计划生成算法均采用非动态决策框架，即在决策初期为所有任务构建模板调度计划，且在实际装配过程中不进行更改. 各算法具体构建方式如下.

CPLEX-RANDOM：首先在不考虑任务返工的情况下通过CPLEX软件求解各算例，在保留CPLEX软件所得最优模板计划的任务执行顺序的基础上，为装配任务随机安排装配人员，并通过飞机装配质量预测模型重新确定任务执行时间.

CPLEX-TS：在CPLEX-RANDOM基础上，通过增加基于人员分配编码禁忌搜索算法（TS2）优化人员配置.

TSD：双层循环迭代算法，其中上层采用基于任务列表编码禁忌搜索算法（TS1），下层在基于人员分配编码禁忌搜索算法（TS2）的基础上进行改编，即通过串行调度算法构建模板调度计划.

本文为C21、C32、C42 3个算例各生成c = 5组实验，每组实验随机扰动次数设为50次. 在构建工件质量场景时，每组实验中任务i的工件质量服从正态分布N（ETAsi，σsi|?s，?i）. 在评价模板调度计划应对随机扰动的能力时，本文采用右移算法（Right Shift）修复随机扰动对模板计划产生的影响. 右移算法作为常见的修复规则，其在保留原有任务执行顺序的同时将受影响任务的开始时间依次顺延. 采用右移算法时采取的评价指标包含项目实际工期和任务开始时间偏差. 其中，任务开始时间偏差表示为所有任务实际开始时间STi与模板计划开始时间ST BS

i的偏差绝对值之和：

STi - ST BS

i

3.3.1   实验1：工件质量预测值与实际值一致的情况

在该实验中，考虑工件质量的预测值与实际值一致的情况，即决策初期预估的工件质量分布在项目执行过程中不发生改变. 各算法在随机环境下右移算法所得结果如表2所示. 其中Em表示右移算法所得项目实际工期;Ed表示右移算法所得任务开始时间偏差.

由表2可以看出，在项目实际工期方面，TSD经右移算法所得平均实际执行工期依次优于CPLEX-TS和CPLEX-RANDOM，其原因包含两方面：首先，基于人员分配编码禁忌搜索算法（TS2）能够实现人员分配的优化，从而减少任务因人员分配不合理而导致返工的情况发生;其次，通过基于任务列表编码禁忌搜索算法（TS1）对任务执行顺序实现优化，从而进一步降低任务延期对实际项目工期的影响. 此外，多层循环迭代搜索算法所得平均实际执行工期优于CPLEX-TS而较劣于TSD，其主要原因在于TSD为单次决策，即在决策点为所有任务构建的邻域，其搜索范围要大于多层循环迭代搜索算法.

在偏差方面，多层循环迭代搜索算法求得的计划能够取得最优或较优的任务开始时间偏差值. 在多数情况下，CPLEX-RANDOM虽然能够取得最优任务开始时间偏差值，但这一结果是CPLEX-RANDOM牺牲项目工期评价指标而为任务设置大量时间缓冲所致. 多层循环迭代搜索算法所得平均最优计划偏差值虽劣于CPLEX-RANDOM，但该算法能兼顾模板调度计划在项目实际工期和任務开始时间偏差的综合表现. 在3种规模算例下，多层循环迭代搜索算法所得项目实际工期和任务开始时间偏差均优于CPLEX-TS.

3.3.2   实验2：工件质量预测值与实际值不一致的

情况

在该实验中，考虑工件质量的预测值与实际值不一致的情况，即在项目执行过程中工件质量分布 N2（ETAsi，σsi）与决策初期预估的工件质量分布N1（ETAsi，σsi）不同. 在此情形下各算法所得结果如表3所示.

由表3可以看出，在工件质量的预测值与实际值不一致的情况下，各算法所得项目实际工期和任务开始时间偏差与实验1中具有相同的规律：TSD能够取得最优的平均项目实际工期，多层循环迭代搜索算法次之，而CPLEX-RANDOM所得平均项目实际工期最劣;在任务开始时间偏差方面，多层循环迭代搜索算法依旧能够取得较优的表现，而TSD所得平均任务开始时间偏差最劣. 然而，比较表2和表3，能够发现各算法虽然在项目实际工期方面变化不大（均值保持在1以内），但不同算法在任务开始时间偏差方面的变化情况不同，因此需要进一步分析.

图7给出各算法分别在工件质量预测值与实际值一致与不一致情况下，任务开始时间偏差的变化情况（即表2和表3中Em和Ed的差值）. 能够发现，在所有规模算例下，CPLEX-RANDOM、CPLEX-TS和多层循环迭代搜索算法在任务开始时间偏差变化均较小，能够保持在2以下，而TSD的任务开始时间偏差变化在C21和C32算例中均为最大，且3个算例中均超多层循环迭代搜索算法. 上述情况的主要原因在于：CPLEX-RANDOM和CPLEX-TS在构建模板计划时为任务设置大量时间缓冲，因此其模板计划鲁棒性较大，但也导致平均项目工期增大;TSD以工件质量的预测值构建模板计划，因此在工件质量的实际值与预测值不一致的情况下，其任务开始时间偏差的变化较大;多层循环迭代搜索算法利用两阶段近似动态决策框架的优势，在每一决策周期保留了调整模板计划的机会，且基于场景的决策目标也使得计划的调整以不确定性信息的变化情况为依据.

4   結   论

1）本文以飞机装配质量映射关系和预测模型为基础，研究包括工件质量在内的不确定性因素对飞机装配调度计划构建的影响形式，建立飞机装配过程的两阶段近似动态调度模型. 其中动态调度模型以基于不确定性场景的项目工期期望为优化目标.

2）针对该问题耦合了时间决策与资源决策，且

因涉及不确定性场景而导致搜索规模增大的情况，提出了多阶段循环迭代搜索算法. 算法第一层对任务列表进行搜索，以获得较优的任务执行顺序;算法第二层基于人员分配编码对人员分配方案进行搜索，实现人员配置的优化;算法第三层通过搜索剩余任务所组成的任务列表，确保评价指标的有效性.

3）数值实验结果表明多阶段循环迭代搜索算法在不确定性环境中具有良好的求解性能，同时能够有效应对不确定性因素在飞机装配过程中的变化，验证了该算法的有效性和可行性.

4）未来可以进一步研究设备状态、设备维护计划与飞机动态调度计划的相互影响情况.

参考文献

[1]    BROWNING T，YASSINE A. Resource-constrained multi-project scheduling：priority rule performance revisited[J]. International Journal of Production Economics，2010，126（2）：212—228.

[2]    LU Z，REN Y，WANG L，et al. A resource investment problem based on project splitting with time windows for aircraft moving assembly line[J]. Computers & Industrial Engineering，2019，135（1）：568—581.

[3]    朱宏伟，陆志强. 考虑资源转移时间的项目可拆分资源受限多项目调度问题[J]. 计算机集成制造系统，2019，25（3）：586—597.

ZHU H W，LU Z Q. 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—597. （In Chinese）

[4]    ZAMANI R. A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem[J]. European Journal of Operational Research，2013，229（2）：552—559.

[5]    CHEN R. Particle swarm optimization with justification and designed mechanisms for resource- constrained project scheduling problem[J]. Expert Systems with Applications，2011，38（6）：7102—7111.

[6]    卢辉，王红卫，李锋，等. 考虑供应不确定性与需求非平稳性的项目调度与材料供应集成优化[J]. 系统工程理论与实践，2019，39（3）：647—658.

LU H，WANG H W，LI F，et al. Integrated scheduling and material supply planning under nonstationary stochastic demand and random supply yield[J]. Systems Engineering-Theory & Practice，2019，39（3）：647—658. （In Chinese）

[7]    GUTJAHR W. Bi-objective multi-mode project scheduling under risk aversion[J]. European Journal of Operational Research，2015，246（2）：421—434.

[8]   MAGHSOUDLOU H，AFSHAR-NADJAFI B，NIAKI S. Multi-skilled project scheduling with level-dependent rework risk;three multi-objective mechanisms based on cuckoo search[J]. Applied Soft Computing，2017，54（1）：46—61.

[9]    廖怡娜，陆志强. 考虑作业返工的资源受限项目调度问题[J]. 计算机集成制造系统，2019，25（11）：2762—2774.

LIAO Y N，LU Z Q. Resource-constrained project scheduling problem with reworking[J]. Computer Integrated Manufacturing Systems，2019，25（11）：2762—2774. （In Chinese）

[10]  崔南方，趙雁，胡雪君. 鲁棒性项目调度中缓冲设置方法[J]. 控制与决策，2014，29（2）：368—372.

CUI N F，ZHAO Y，HU X J. Buffer management in robust project scheduling[J]. Control and Decision，2014，29（2）：368—372. （In Chinese）

[11]  贾峰，江平宇，刘道玉，等. 叶片批量加工过程的误差传递控制方法[J]. 计算机集成制造系统，2012，18（1）：76—86.

JIA F，JIANG P Y，LIU D Y，et al. Error propagation control method for multistage batches machining processed of blades[J]. Computer Integrated Manufacturing Systems，2012，18（1）：76—86. （In Chinese）

[12]  王秋明，刘科成，高慧颖. 基于灰色理论与BP神经网络的工序质量预测研究[J]. 北京理工大学学报，2011，31（2）：249—252.

WANG Q M，LIU K C，GAO H Y. Research of procedure quality forecast based on the grey theory and BP neural networks[J]. Transactions of Beijing Institute of Technology，2011，31（2）：249—252. （In Chinese）

[13]  鞠萍华，柯磊，冉琰，等. 基于GRA和AHP的GRNN神经网络零件失效概率预测方法[J].湖南大学学报（自然科学版），2019，46（4）：34—40.

JU P H ，KE L，RAN Y，et al.  Failure probability prediction method on parts of generalized regression neural network based on GRA and AHP[J]. Journal of Hunan University（Natural Sciences），2019，46（4）：34—40. （In Chinese）

[14]  LEE D，FUKASAWA R，RICARDEZ-SANDOVAL L. Bi-objective short-term scheduling in a rolling horizon framework：a priori approaches with alternative operational objectives[J]. Computers & Operations Research，2019，111（1）：141—154.

[15]  张洁，秦威，宋代立. 考虑工时不确定的混合流水车间滚动调度方法[J]. 机械工程学报，2015，51（11）：99—108.

ZHANG J，QIN W，SONG D L. Rescheduling algorithm based on rolling horizon procedure for a dynamic hybrid flow shop with uncertain processing time[J]. Journal of Mechanical Engineering，2015，51（11）：99—108. （In Chinese）

[16]  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—680.

[17]  韩笑乐，鞠留红，钱丽娜，等. 集装箱进出口码头泊位-堆场协同分配的动态决策[J]. 上海交通大学学报，2019，53（1）：69—76.

HAN X L，JU L H，QIAN L N，et al. Dynamic decision making for the integrated allocation of berth and yard resources at import/export container terminals[J]. Journal of Shanghai Jiaotong University，2019，53（1）：69—76. （In Chinese）

[18]  唐文斌. 飛机非线性装配偏差分析与容差协同分配方法研究[D]. 西安：西北工业大学机电学院，2015：1—135.

TANG W B. Non-linear assembly deviation analysis and tolerance co-allocation for aircraft[D]. Xian：School of Mechanical Engineering，Northwestern Polytechnical University，2015：1—135. （In Chinese）

[19]  RUI J，ZHANG H，ZHANG D，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（1）：699—706.

[20]  陆志强，杨超. 基于项目网络拆分决策的多项目协同调度问题建模[J]. 上海交通大学学报，2017，51（2）：193—201.

LU Z Q，YANG C. Modeling of resource constrained multi-project scheduling problem based on project splitting[J]. Journal of Shanghai Jiaotong University，2017，51（2）：193—201. （In Chinese）

[21]  隋惠惠. 基于BP神经网络的短期电力负荷预测的研究[D]. 黑龙江：哈尔滨工业大学电气工程与自动化学院，2015：1—57.

SUI H H. Research on short-term electric load forecasting based on BP neural network[D]. Heilongjiang：School of Electrical Engineering and Automation，Harbin Institute of Technology，2015：1—57. （In Chinese）