基于物料交货期预测的飞机装配动态调度问题

卢 斌，陆志强，张永峰

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

0 引言

对于飞机等大型复杂装备制造企业而言，建立科学合理的装配调度计划是管理者实现高效管理生产项目的重要前提[1]。飞机装配调度计划的制定与执行受到诸多因素的影响，包括装配作业间的优先级约束、各类资源的供给数量限制、作业装配模式的选择以及计划执行过程中的不确定性因素等。目前，郑倩等[2]和LU等[3]认为飞机装配调度问题需以满足可更新资源限制和作业优先顺序两类主要约束为前提，因此可将其抽象为资源受限项目调度问题(Resource Constrained Project Scheduling Problem, RCPSP)及其扩展问题，并设计相应的元启发式算法进行求解。尽管已有学者在飞机装配背景下就RCPSP问题及其相关衍生问题进行了较为充分的研究[4-7]，但相关研究工作大多致力于模板计划的制定，且均假定其物料能准时供应。然而，在实际装配过程中，飞机装配所需的零部件种类复杂且数量巨大[8]，各零部件供应商可能存在产能不足、质量缺陷、设备故障、材料短缺等问题，物料供应的准时性难以保证。此外，装配作业时常因物料缺失、损坏、不符合装配要求等突发扰动导致现场缺料而推迟执行。物料供应延期不仅影响装配作业自身，还会干扰后续作业的正常执行，使生产管理人员不得不对装配现场的原有资源配置进行调整，从而增加额外的调度成本。因此，在装配计划执行过程中，提供一种能有效应对物料供应不确定性、实现调度成本优化的反应调度方法具有重要意义。由此，本文对物料供应不确定环境下的飞机装配调度问题展开研究。

现有研究中，处理不确定性问题的方法主要包括前摄—反应调度和反应调度两类，其中前摄—反应调度通过合理安排时间缓冲来提升前摄计划的鲁棒性，在执行前摄计划阶段采用事件驱动的反应策略进行计划调整。MA等[9]考虑资源可用性不确定的项目调度问题，先以解鲁棒性为优化指标生成前摄计划，执行阶段采用反应式调度策略，以最小化与前摄计划的偏差为目标函数生成新调度计划。韩笑乐等[10]针对船舶到港时间不确定环境下的集装箱码头泊位堆场资源调度问题，设计了基于前摄—反应的鲁棒性调度方法。上述文献在制定前摄计划阶段，往往在事先假定不确定性因素服从某一概率分布的条件下进行鲁棒性优化，但无论前摄计划的鲁棒性有多高，当计划实际执行过程中的某些干扰并没有发生时，先前加入的缓冲便会造成浪费。

反应调度方法可根据干扰触发方式的不同，分为事件驱动策略、周期驱动策略和事件与周期混合驱动策略3类。

(1)事件驱动策略，即在干扰事件发生时立刻进行重调度，其主要适用于干扰因素有突发性且可预知性较差的情况。LI等[11]考虑单元式制造系统中突发的机器故障干扰，采用整数规划方法将反应调度问题描述为离散优化问题，并通过结合混合二进制粒子群算法和模拟退火算法进行求解。CHAKRABORTTY等[12]在RCPSP问题的背景下，考虑资源中断的干扰场景，建立了混合整数规划模型，提出多种启发式算法进行求解。RAHMANI等[13]针对流水线车间生产过程中插入新作业的干扰问题，建立了以最小化作业拖期时间和稳定性代理指标加权和为目标的数学模型，并设计了变邻域搜索算法进行求解。

(2)周期驱动策略，即预先定义重调度的滚动时域，然后通过获取每个滚动时域末制造系统的实际状态来确定下一滚动时域的初始条件，并进行重调度。SOURIRAJAN等[14]针对半导体制造车间实时状态不断变化的问题，采用周期性滚动时域调度策略求解加工调度子问题。

(3)事件与周期混合驱动策略则结合前两种策略，即首先在每个滚动时域初进行重调度，在时域内进行基于事件驱动的再调度。周炳海等[15]针对物料搬运系统运行中的路径冲突干扰问题，结合滚动时域方法和时域内基于事件驱动的再调度策略设计了搬运避碰调度方法。

综合上述文献发现，现有的反应调度方法往往在不确定性事件发生时或到达滚动时域节点时进行重调度处理。然而对于飞机装配过程而言，除了要考虑计划执行过程中突发的物料缺失、损坏、不符合装配要求等干扰问题以外，还应处理各供应商的物料交货期不确定的情况。事实上，由于飞机装配周期较长，各物料的供应过程易受外部不确定因素影响，物料交货期随着装配进程的推进不断变化。而现有的反应调度方法在重调度过程仅利用了决策点的确定性信息，无法有效应对不确定性因素不断改变的情况，忽视了主动改善的优势。

实际上，在全球航空制造业普遍采用“主制造商—供应商”模式的背景下，飞机制造商通过同各供应商建立起战略合作伙伴关系、打造基于信息共享与集成的供应链管控体系[16]等方法，可实现对物料供应过程的实时追踪。此外，供应商运用大量智能化的数据采集和存储设备，在获取实时监测数据的同时，积累了大量关于物料交货的历史数据。这些技术条件以及机器学习预测技术的长足发展为飞机制造商实时掌握物料供应状态、实现物料交货期预测提供了基础。由此，本文提出一种基于数据预测的决策方法。相比现有的反应调度方法，基于数据预测的决策方法能够充分利用不断变化的物料供应状态信息，预测未来可能出现的物料交货场景，并事先主动调整原有的调度计划，从而提升装配过程应对未来不确定性的能力。

现有文献已对交货期预测问题进行了较为深入的研究。孙德厂等[17]将不确定性要素分为外部环境不确定性和生产系统不确定性两类，分析了它们对交货期的影响机制并建立了交货期模型，提出了基于支持向量回归(Support Vector Regression, SVR)的交货期预测方法。朱雪初等[18]以晶圆生产为背景，将加工周期影响因素归纳为待加工工件和生产系统相关的属性与状态，并提出基于ReliefF和SVR的产品完工周期预测方法;CHEN等[19]将模糊C-均值等聚类算法同BP神经网络结合，提高了晶圆加工周期预测精度。WANG等[20]通过基于信息熵的关键因素识别方法和基于模糊C-均值聚类的BP神经网络完成晶圆交货期的预测。上述文献大多利用支持向量回归或神经网络等单个学习器对交货期进行预测，对于规模较大的复杂系统而言，其泛化性能较差，且由于此类学习器固有的浅层结构，模型参数数量会随着变量增加而增多，导致其在包含较多变量的大规模系统中的推理能力下降[21]。事实上，上述交货期预测方法仍难以满足飞机装配过程对物料交货期的预测需求。一方面，飞机装配所需物料大多涉及复杂的供应系统，物料交货期相关影响因素较多，对预测方法的适应性提出了更高要求；另一方面，由于预测所得信息将用于指导装配调度的优化决策，预测方法还应具有较优的推理能力和预测准确率。针对上述需求，本文通过研究物料交货期与物料供应过程相关因素的映射关系，提出了基于XGBoost算法的物料交货期预测模型。并以此为基础，借鉴文献[22]中的基于两阶段近似优化的动态决策框架，进一步分析物料供应不确定性对调度计划执行过程的影响形式，建立包含上述映射关系表达式在内的动态调度模型。针对模型决策逻辑，设计了双层循环迭代搜索算法进行求解。对于执行计划过程中突发的物料扰动问题，通过设计基于松弛时间的反应机制对计划进行修复。

1 问题描述与决策框架

1.1 问题描述

基于物料交货期预测的飞机装配动态调度问题，是通过确定和量化影响物料交货期的主要因素，结合物料在生产运输过程中积累的相关历史数据建立物料交货期预测模型，并以此为基础，进一步分析物料供应不确定性对调度计划执行过程的影响形式，采用基于事件与周期混合驱动的滚动决策框架，优化决策作业的开始时间和执行模式以减少其与模板计划的偏差，从而达到最小化反应调度总成本的目的。以飞机装配项目为背景，该问题涉及如下假设：

(1)装配项目包含J个装配作业和K种共享的可更新资源。装配作业间存在优先级关系，且每个作业包含若干种装配模式，特定的装配模式对应特定的作业执行工期和可更新资源需求量。将时间轴进行离散化处理，每种资源在任意时刻的需求量不应超过资源供给上限。

(2)装配项目的物料集合为Ι={1,2,…,|I|}。为了实现飞机装配线的高效运作，作业所需物料均采取齐套的方式，从中央仓库向相应装配位置进行准时化配送。

(3)在临近装配项目启动阶段，已知各物料的上线生产时间，本文将物料交货期b定义为物料从上线生产到送达飞机装配中央仓库的时间。物料交货期主要包括生产时间和运输时间两个部分。生产时间是指物料上线生产至完工的时间，运输时间是指从物料完工后至供应商送达装配中央仓库的时间。其中，影响生产时间的定性因素主要包括物料属性O(如物料的产品类型等)、车间的生产状态Q(如上线生产时各设备前的加工队列等)以及生产环节出现的异常情况U(如设备故障、材料缺失、工人短缺、返工等异常事件)；影响运输时间的定性因素主要包括运输方案S(包括运输方式、运输路线等)、运输环节出现的异常情况E(如因其他待运输产品未完工而造成的等待、天气状况恶劣、交通管制等)。由此，物料交货期b可通过上述5个主要因素的映射关系表达式来描述，即

b=F(O,Q,U,S,E)。

(1)

本文通过上述5个因素的相关历史数据建立物料交货期预测模型。将待预测数据定义为物料i∈I在某时刻采集到的5个因素相关数据，即(Oi,Qi,Ui,Si,Ei)。对于特定的飞机装配项目而言，物料属性和运输方案可通过签订采购合同的方式提前确定，且在临近装配项目启动阶段，物料上线生产时的车间生产状态可提前掌握，因此可认为Oi、Qi和Si是固定的。物料在生产、运输环节出现的异常情况会随着时间的推进而逐渐明确，即Ui和Ei是随时间不断更新的。

(4)模板装配计划已定，即任意作业的模板开始时间和模板装配模式已确定。对飞机装配项目而言，为了避免出现作业即将开始而物料尚未到达的情形，作业的实际开始时间不应早于模板计划开始时间。作业一旦出现延期执行的情况，将造成人员、配送、仓储等与之相耦合的环节发生变动而产生一定成本。作业更改原有装配模式会导致作业资源配置的重新调整，从而产生额外切换成本。因此，本文考虑的反应调度总成本包含与模板计划的偏差成本和装配模式切换成本。

1.2 物料交货期预测模型

如1.1节所述，物料交货期主要受到物料属性、车间的生产状态、运输方案、生产运输环节出现的异常情况等多方面因素的影响，因此需建立有效的预测模型来准确描述物料交货期与相关影响因素之间的映射关系。考虑到物料交货期与相关影响因素之间的非线性关系以及XGBoost算法在非线性预测应用领域的适用性[23]，本文采用XGBoost算法构建物料交货期预测模型。

XGBoost算法是基于梯度增强决策树算法演化而来的集成学习算法。该算法以决策树为基学习器，在样本特征集合中随机选择一部分特征，并通过不断地进行特征分裂来生成一棵决策树，对于生成的每一棵树都采用梯度下降法拟合先前已生成树模型的残差，拟合过程可获得当前树的预测模型，将每棵树预测的样本输出值累计相加即获得样本最终的预测值。本文以分类回归树(Classification and Regression Tree, CART)作为基学习器，使用XGBoost算法构建物料交货期的预测模型，预测过程如下：

(1)定义目标函数。

(2)

(3)

其中P表示回归树叶子节点个数，ωφ表示第φ个叶子节点的权重，系数α和λ分别为叶子树和叶子权重惩罚正则项。

(4)

式中C为常数。为找到一个能使优化目标最小的fφ(Xg)，将上式在fφ(Xg)=0处进行二阶泰勒展开：

(5)

(6)

(7)

(8)

(3)以最优值为基础，输入所有样本数据进行建树。叶子节点的分裂过程是建树的核心，在每个节点处随机选择部分样本特征，并对这些特征选择最优分裂节点。选择分裂节点时，定义增益

(9)

(4)在前一棵树的基础上重复建树，直至达到树的总量即迭代次数为止，完成XGBoost离线训练。

(5)在实际预测中，根据待预测样本的输入向量和离线训练模型逐一输出每棵回归树的预测值，并将这些预测值累计相加，得到输入向量的预测值。

1.3 物料供应不确定环境下的决策框架

由于飞机装配周期较长，管理人员需对物料供应过程中的一系列因素(如仓库的存储能力及费用、订货费用和订货次数等)进行综合考量，制定合理的物料采购订单，使供应商按规定时间向中央仓库运送待装配物料，因此物料的实际交货期通常无法在装配项目启动前全部知晓，而是随着装配项目的推进逐步明确。此外，在物料到达中央仓库以前，管理人员只能通过供应商提供的最新状态数据对物料交货期进行预先估测。基于上述特点，对于物料交货期尚未明确的作业，本文将利用其物料在生产运输过程中积累的历史数据训练物料交货期预测模型，在此基础上，根据物料在实际生产运输中的最新状态数据，对物料交货期进行实时预测。预测所得的物料交货期，将用以指导作业的调度决策；而对于物料实际交货期已经明确的作业，若出现因物料交货期延迟导致作业无法按原计划执行的情形，则需重新优化其装配开始时间和装配模式。

如图1a所示，按照物料实际交货情况对装配调度进行周期划分：将第q个调度周期的决策时刻记为Tq；在模板计划开始执行时刻(记为T1)，对于物料交货期均已明确的作业(作业1、2、3和4)，可在第1个调度周期进行固定性决策；在模板计划中，找到这些作业中最迟开始的作业(作业4)，将该作业的启动备料和配送任务时刻记为T2；当时间推进至T2时刻，按照当前物料实际交货情况重新确定在第2个调度周期参与固定性决策的作业(作业5、6、7、8和9)；当时间推进至T3时刻，再次确定在第3个调度周期参与固定性决策的作业(作业10、11、12和13)；……依此类推，直到装配项目执行完毕。综合上述分析，在任意决策时刻Tq，可将作业划分为A、B、C类3类，相应的作业集合记为JA、JB、JC。各类作业的决策逻辑描述如下：

(1)A类，备料及配送任务已经开始的作业。此类作业无需决策，按上一周期的计划执行。

(2)B类，可在当前调度周期内启动备料及配送任务的作业。此类作业的物料交货期均已明确。对于B类作业，需引入辅助决策变量uj作为延迟判定因子，用于判断作业j是否需要延迟至下一周期进行决策，具体判定方法为：若作业被延迟至下一周期决策，则uj=1，作业归入B1类；若作业在当前周期进行决策，则uj=0，作业归入B0类。B0类作业进行固定性决策，其决策结果作为新的计划，将替代该阶段的模板计划并被实际执行，B1类与C类进行相同操作。

在各个调度周期内，新的周期计划得到执行，但现场装配过程中仍会面临突发的物料缺失、损坏、不符合装配要求等扰动。出现此类扰动时，可将该作业视为一个被延期的新作业，同时要求仓库部门紧急配送问题物料的备用件或协调供应商长期派驻在装配中心的返工小组，对相应问题物料进行紧急返工后重新配送物料，可获知作业预计延期时间为dtj。为了保持新计划执行的稳定性，以避免重调度过于频繁，本文通过设计实时的反应机制来应对此类突发情况。综上所述，本文构建了一种事件与周期混合驱动的滚动决策框架如图1b所示。

1.4 数学模型

本节构建任意滚动决策时刻Tq的数学模型。模型的符号说明如表1所示。

表1 符号说明

根据上述符号及其定义，建立如下数学模型：

(10)

(11)

M(uj-1)

(12)

(13)

(14)

(15)

∀j∈J,∀h∈Pj；

(16)

∀k∈K,∀t∈T；

(17)

bi=F(Oi,Qi,Ui,Si,Ei),∀j∈JC,i∈Ij；

(18)

sj-pT≥di+bi,∀j∈JC,i∈Ij；

(19)

(20)

(21)

xjmjt∈{0,1},∀j∈J,∀mj∈Mj,∀t∈T；

面对静宁县农村饮水困难问题突出、供水工程建设任务繁重的形势，要积极谋划，发挥公共财政对水利的主导作用，在争取公共财政投资和金融支持建设主体工程的同时，多渠道筹集资金，鼓励农民自愿投资投劳建设供水入户工程，吸引社会资金投入提高供水入户标准。建立以公共财政投入和金融支持、农民投资投劳、社会资本参与为主要支撑的农村供水工程投资稳定增长机制。力争到“十三五”末彻底解决静宁县农村供水问题，全面提升饮水安全标准，为改善民生、促进经济社会又好又快发展奠定基础。

(22)

uj∈{0,1},∀j∈JB。

(23)

其中：式(10)以最小化与模板计划的偏差成本和装配模式切换成本之和为目标函数；式(11)表示对A类作业的决策变量进行赋值；式(12)为决策周期约束，利用辅助决策变量uj将B类作业划分为B0和B1两类作业，M为足够大的数；式(13)和式(14)分别表示决策变量xjmjt与sj、aj间的等式关系；式(15)表示任意作业只能选择一种装配模式且一旦开始无法变更；式(16)表示作业间优先级关系约束，即任意作业必须在其所有紧前作业完成之后才能开始；式(17)表示任意时刻下各作业对任意可更新资源的需求量不得超过资源容量上限；式(18)表示任意C类作业的物料交货期与相关影响因素间的映射关系表达式，可通过预测模型实现；式(19)和式(20)表示任意B、C类作业的开始备料时间不得早于其所有物料送达仓库的时间；式(21)表示任意作业的开始时间不得早于其模板开始时间；式(22)和式(23)表示各决策变量的定义域。

2 算法设计

为适应本文飞机装配动态调度问题存在多阶段决策的需求，设计了融合在线预测机制的双层循环迭代搜索算法，其基本思路如图2所示。首先通过TS1上层模块搜索固定性决策，其决策结果包括B0与B1类作业的划分决策以及B0类作业的开始时间和装配模式。基于上述决策结果，结合决策时刻所掌握的物料交货期相关参数和物料交货期预测模型，在线预测C类作业的物料交货期，然后利用TS2下层模块搜索B1和C类作业的预测决策结果。本文通过计算两个阶段决策结果的目标函数值来评价固定性决策的优劣性。双层循环迭代搜索算法以作业列表和模式列表的双链结构为编码方式，通过TS1、TS2两层嵌套运用禁忌搜索算法的模式搜索最优解，其具体细节在2.1节中详细阐述。此外，对于新计划执行中的突发性扰动，本文提出基于松弛时间的反应机制，其具体步骤在2.2节中详细阐述。

2.1 双层循环迭代搜索算法

考虑到禁忌搜索算法在邻域搜索及求解效率方面的优势，双层循环迭代搜索算法的上下层均以禁忌搜索算法为算法框架。具体而言，算法上层(TS1)采用作业列表和模式列表的双链编码方式对B类作业的执行顺序和相应装配模式展开搜索。同时，对搜索到的每一个编码个体，采用串行调度生成算法进行解码。串行解码过程中，可根据作业能否在当前周期安排执行，对B类作业进行进一步划分，B1类作业的决策将被延迟至预测决策阶段进行。算法下层(TS2)基于TS1作业划分的基础上，采用与TS1相同的编码方式对B1和C类作业的执行顺序和相应装配模式展开搜索。同时，对搜索到的每一个编码个体，在TS1对B0类作业的决策结果基础上采用串行调度生成算法进行解码，并计算调度计划的评价指标。双层循环迭代搜索算法框架如图3所示。

2.1.1 TS1:搜索固定性决策

算法上层TS1采用作业列表和模式列表的双链编码方式搜索固定性决策，其编码示例如图4a所示。每个编码位的数字均包含了作业的编号和装配模式编号，编码结构满足作业间的优先级关系约束，即每个作业的编码位置都应置于其直接紧后作业之前。此外，由于A类作业无需决策，将其置于编码的最高优先级位置；B类作业需在本阶段进行固定性决策，将其置于次优先级位置；C类作业不在该阶段决策，置于编码的尾部位置。初始编码按作业在模板计划中的开始时间升序排列，并将各作业的装配模式编号列入模式列表。为了充分利用双链编码的信息承载能力及其邻域构造灵活性，TS1中的邻域生成方式包含两部分：①从当前编码列表的B类作业中随机选取两个不存在优先级关系的作业进行位置互换，相应装配模式也随之互换；②从当前编码列表中随机选取一个B类作业，对其装配模式进行变异操作，即作业以一定概率重新选择装配模式并替换当前模式，作业j对模式mj的选择概率为Prjmj，

(24)

图4b和图4c分别给出单项互换、模式变异操作示例。禁忌对象为迭代过程中使目标函数最优的编码列表所对应的单项互换或模式变异操作，禁忌次数在上限tabumax和下限tabumin间随机生成，设置TS1的终止迭代次数为iter1。串行调度解码算法步骤如下：

步骤1获取当前编码的作业列表{j1,j2,…,j|J|}和模式列表{mj1,mj2,…,mj|J|}，令e←1，B1类作业集合ΩB1←∅。

步骤2若作业je为A类作业，直接安排其作业开始时间和装配模式，否则转步骤3。

步骤5若∀t∈[Tje,Tje+pjemje]，∀k∈K，rjemjek≤Rk恒成立，则令sje←Tje并转步骤7，否则转步骤6。

步骤6令Tje←Tje+1，转步骤5。

步骤7若sje-pT>Tq+1，令ΩB1←ΩB1∪je并转步骤8，否则直接转步骤8。

步骤8若e<|J|，令e←e+1，转步骤2，否则输出第1阶段固定性决策和ΩB1。

2.1.2 TS2:搜索预测决策

算法下层的TS2采用与TS1相同的编码方式搜索预测决策，其编码列表由B1和C类作业构成，图4d给出示例。TS2的编码初始化、邻域生成方式、禁忌对象和串行调度解码等操作与TS1模块类似，但需注意：在此阶段的禁忌搜索寻优过程中，对B1和C类作业的解码结果均补充自同一个固定性决策；在进行串行调度解码过程中，对于每个待解码作业的物料，需将其待预测数据输入物料交货期预测模型以获取其物料交货期的预测值，确保待解码作业的开始时间不早于其物料预计配送完成时间；对搜索到的每一个编码个体，在获得其解码结果后，需计算目标函数以评价TS1中固定性决策的优劣。设置TS2的终止迭代次数为iter2。

2.2 基于松弛时间的反应机制

在执行每个周期的固定性决策过程中，当作业受到扰动而被延期执行时，新的计划会被打乱，因此需设计一套与周期性调度框架相匹配的反应机制加以应对。基于此，本文设计了基于松弛时间的反应机制，其核心思想如图5所示。

首先将当前周期计划中作业j的松弛时间stj定义为作业j在不影响后续作业正常执行且不破坏决策周期约束情况下的最大可推迟时间。当作业j因物料缺失、损坏、不符合装配要求等突发扰动而延期执行时，可根据其预计延期时间dtj执行如下反应策略：①若dtj≤stj，将作业开始时间延后dtj个单位，并维持原有装配模式；②若dtj>stj且sj+dtj≤Tq+1，则令sj更新为sj+dtj，并按照模式切换成本升序顺序逐个安排作业装配模式，直至找到可行切换方案(即既满足资源约束又不影响后续作业正常执行的模式切换操作)为止，若遍历所有待切换模式仍无法找到可行切换方案，则直接为作业j安排最小执行工期所对应的装配模式，并通过右移策略即将后续作业的开始时间依次顺延，无法在当前周期开始的作业将被纳入下一周期的B类作业集合；③若sj+dtj>Tq+1，则直接将作业j及其直接和间接紧后作业视为下一周期的B类作业，其他作业按计划正常执行。这样既能确保被干扰作业能够尽快开始作业，又能充分利用当前周期计划中作业间的松弛时间和空闲资源，防止重调度过于频繁，使飞机装配项目调度总成本增加。

3 实例应用与分析

3.1 实验平台

为验证所提决策框架的有效性，以某型号客机前机身、后机身和机身尾翼装配工位的部分装配流程和物料交货历史数据构建实验算例。装配流程所包含的装配作业数量分别为23、32、42项，资源包括装配工人、关键装配设备、能源供应设备、线边存储空间4类，资源上限数量分别为[12,7,8,12]，每项作业存在3种装配模式。为了构建上述装配流程的模板计划算例，通过随机方式生成作业列表，并为每项作业随机选取一种装配模式，利用串行调度解码作业列表。每项作业的单位时间延期成本和模式切换成本分别在区间[0,5]和[0,8]之间随机生成，将构建的算例分别记为E23、E32、E42。物料交货期预测模型和对比算法均通过Python 3.6进行编程，测试计算机配置为Inter i7-4790U处理器，3.6 GHz，8 G内存，CPLEX软件版本号为12.6.3。

3.2 物料交货期预测模型效果验证

(25)

(26)

实验结果如表2所示，不同算例下XGBoost算法的预测准确率均值达到98.61%、97.24%、97.84%，不仅优于SVR和FCM-BPN算法，还将预测值与实际值间的平均偏差控制在3%以内，表明XGBoost算法在处理物料交货相关数据方面具有更高的预测准确性。从绝对误差的根均方差指标方面看，相比其他算法，XGBoost算法的预测误差波动程度更低，表明其具有更优的鲁棒性。此外，不同算例下XGBoost算法的单次预测平均耗时也更低，表明其预测响应时间优于其他方法。因此，本文所提方法能较好地应用于物料交货期预测，为调度决策提供可靠的依据。

表2 预测算法对比结果

3.3 滚动决策框架效果验证

本文为E23、E32、E42三个算例各生成10组实验，每组实验的随机延期干扰次数设为8，延期干扰时间在区间[5,10]中随机取值。对于每组实验，采用双层循环迭代的禁忌搜索(Double-layer-loop-iterative Tabu Search，DTS)框架进行连续5个周期的滚动决策，同时在执行每个周期的新计划阶段，采用基于松弛时间的反应机制(Slack Time based Reaction, STR)来应对干扰。为了验证本文滚动决策框架的适用性以及双层循环迭代搜索算法的有效性，每组实验在相同干扰环境下，进行如下对比方法实验：

(1)CPLEX：基于后验信息(即在提前知晓所有物料的实际交货时间和延期干扰信息的条件下)，此时可视所有作业为B类作业，使用CPLEX软件求解本文数学模型。

(2)CPLEX-STR：采用非滚动决策方式，即在决策初期利用所有作业的物料交货信息(包括决策初期获得的作业物料实际到达时间和各个物料交货期预测模型的输入数据)，以本文目标函数为优化目标，通过本文的物料交货期预测模型和CPLEX软件预先求得新的计划，在执行新计划过程中采用基于松弛时间的反应机制来应对延期扰动。

(3)GA-STR：借鉴并改编文献[9]中的前摄—反应决策框架，在决策初期利用所有作业的物料交货信息，以前摄计划的项目工期(即质量鲁棒性代理指标)与文献[9]采用的松弛时间代理指标之和为优化目标，通过本文的物料交货期预测模型和遗传算法预先求得新的计划。在执行新计划过程中采用基于松弛时间的反应机制来应对延期扰动。其中，遗传算法的染色体编码方式、种群初始化、选择、交叉、变异等操作均借鉴文献[6]中的方法。

上述各方法应对随机扰动的评价指标为装配项目实际执行后产生的反应调度总成本(记为Z)即所有作业实际开始时间与模板计划开始时间的偏差总成本与所有作业的装配模式切换总成本之和。表3～表5分别给出了E23、E32、E42三个算例的实验结果。其中：G1为本文方法(DTS)与CPLEX方法所得Z的差值百分比，G2为其他对比方法与DTS方法所得Z的差值百分比。从表中可以看出，不同算例规模下，DTS与CPLEX方法所得Z的差值百分比G1的均值分别为7.58%、6.37%、6.20%，其原因为：相比于DTS，CPLEX方法利用了后验信息进行精确求解，但在实际决策中无法提前知晓这些后验信息，因此CPLEX方法所得解是无法实现的理想解。这一结果对比不仅体现了飞机实际装配过程受物料供应不确定性的影响较大，也说明了装配项目推进过程中不确定性信息的动态变化特点使本文问题的优化求解更加复杂。不同算例规模下，CPLEX-STR方法与DTS方法所得Z的差值百分比G2的均值分别为4.44%、5.80%、6.24%，可见本文的滚动决策方式相比非滚动决策方式具有一定优势，且其优势随算例规模的增大而愈加明显，其主要原因为：相比于DTS方法在各个滚动周期借助最新获得的预测信息主动改善原有模板计划，CPLEX-STR方法仅利用了决策初期的信息来更新原有计划，其在后续执行过程中仍采取被动应对干扰策略，导致其反应调度总成本较高。在不同算例规模下，GA-STR方法与DTS方法所得Z的差值百分比G2的均值分别为4.51%、5.45%、5.51%，表明本文的滚动决策框架相比于现有的前摄—反应决策框架，具有更优的调度效果。具体来说，前摄—反应决策框架虽然在决策初期为各作业安排了一定量的时间缓冲，使生成的前摄计划具备较强的鲁棒性，但缺乏对不确定性信息不断更新的反馈措施，易导致作业间的松弛时间不足或过大的情况，使得其调度总成本较高，而DTS方法能充分利用不断更新的不确定性信息获得较优的决策结果。

表3 E23的实验结果

表4 E32的实验结果

续表4

表5 E42的实验结果

3.4 反应机制效果验证

为了进一步验证STR在应对突发扰动方面的优势，以3.3节中E42的10组实验为基础，在相同扰动环境下，补充如下对比实验：

基于双层循环迭代禁忌搜索的右移算法(Double-layer-loop-iterative Tabu-search based Right-shift, DTR)：采用与DTS方法相同的滚动决策方式，但在执行新计划过程中采用右移算法(Right Shift，RS)来修复延期扰动对新计划产生的影响。其中，右移算法作为实际生产中常用的修复规则，将发生物料延期扰动的作业推迟dtj，同时后续作业按原有执行顺序依次顺延。

表6中Zd表示所有作业实际开始时间与模板计划开始时间的偏差总成本，Zs表示所有作业的装配模式切换总成本。从表中可以发现，在同样使用滚动决策框架的情况下，STR能更有效地降低因物料突发延期扰动而产生的反应调度成本。值得注意的是，在Zd指标上，以STR作为反应规则的DTS方法优于DTR方法，但在Zs指标上，DTR方法反而具有一定优势。上述情况的主要原因为：相比于RS，STR不仅利用了周期计划中作业间的松弛时间，还利用了不同作业装配模式下潜在的空闲资源，虽然会产生更多的模式切换成本，但能使周期计划内的作业尽快开始，防止部分作业被延至下一决策周期进行重新，确保实际执行计划与原有模板计划的偏差不至于过大。

表6 STR与RS的算法性能对比

4 结束语

本文分析了飞机实际装配过程中物料交货期与相关影响因素间的映射关系，以物料的历史交货数据为基础，构建了基于XGBoost算法的物料交货期预测模型。

在预测模型基础上，研究了物料供应不确定性在飞机装配计划执行过程中的表现形式，构建了基于事件与周期混合驱动策略的滚动决策框架，在各滚动决策时刻建立了基于两阶段近似优化的周期性调度模型，并设计了双层循环迭代搜索算法进行求解。针对滚动周期内的物料突发延期扰动，设计了基于松弛时间的反应机制进行计划修复。

实验结果表明，基于XGBoost算法的物料交货期预测模型可获得较优的预测效果，能为调度决策提供可靠的依据；双层循环迭代搜索算法能有效应对物料供应不确定性在飞机装配过程中的变化，同时可获得较优的决策结果，验证了该算法的适用性和有效性；基于松弛时间的反应机制能充分利用作业间的松弛时间和潜在的空闲资源，从而降低反应调度总成本，验证了该方法的优势。

未来可进一步研究供应商实时状态对飞机采购计划、物料配送调度计划的影响情况。