物料供给不确定环境下的飞机移动生产线动态调度方法

2019-06-04陆志强胡鑫铭朱宏伟

同济大学学报（自然科学版） 2019年5期

陆志强，胡鑫铭，朱宏伟

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

基于精益思想的飞机移动式装配生产线已成为飞机生产的新模式，其具有装配效率高、生产连续稳定等优点，近年来被各大飞机制造企业竞相采用.飞机总装是多学科集成的系统工程，装配作业的科学调度及实现资源优化配置对于提高我国飞机制造行业的生产能力具有重要意义.

现有文献对确定性环境下的飞机移动生产线调度相关问题已经进行了较为充分的研究[1-5]，然而这些文献中的模型与算法主要是为了制定飞机移动生产线的模板装配计划，在决策各装配作业的开始时间时假定所有的物料都能准时供给，而没有考虑实际装配中物料配送可能出现延期等不确定性因素.在实际装配环境下，飞机装配所需的零部件种类复杂且数量巨大，需要由分布在不同地区的上千家供应商分别提供[6].由于存在供应商产能不稳定、零部件质量缺陷、配送延期等影响因素，装配现场常常出现物料没有按计划准时送达,导致装配作业不得不推迟执行、甚至生产线停线的情况.物料供给延期和装配现场缺料已成为当前飞机制造企业提高生产能力的瓶颈[7-8].因此在装配线的实时运作过程中，提供与模板装配计划相适应的反应调度方法,以应对物料供给的不确定性,具有重要的理论与实际意义.基于该实际需求，本文对物料供给不确定环境下的飞机移动生产线动态调度问题进行了研究.

传统的动态调度方法可以分为3类：精确算法[9-10]，启发式规则[11-12],元启发式算法[13-15].近年来，随着人工智能技术的快速发展，机器学习算法得到了包括生产调度领域在内的各领域学者们的极大关注.基于机器学习的动态调度算法优势在于将复杂的计算过程从在线调度阶段转移到离线学习阶段，使得在线调度阶段可以根据当前生产系统的实时状态快速得到高效的调度方案.Nasiri等[16]将人工神经网络(artificial neural network,ANN)应用于开放式车间动态调度问题中，结合离散事件仿真、数据包络分析等方法为每台机器确定最优的调度规则以最小化平均等待时间.Wang等[17]在混合流水线调度问题中首次提出层次聚类算法，该算法将混合流水线分解为多个具有随机特性的机器群，并执行基于决策树(decision tree,DT)的分配程序选择合适的调度方法.Zhou等[18]针对汽车装配线的物料配送问题，设计了一种基于支持向量机(support vector machine,SVM)的实时调度方法，首先通过物料搬运仿真系统生成样本离线训练支持向量机模型，然后在实时调度阶段根据现场状态参数对小车的搬运或等待进行快速决策.

本文研究的动态调度问题中，装配作业的提前、延期或按计划执行与数据多分类问题具有一定的相似性，机器学习算法相比于传统调度算法更具优势.SVDD(support vector data description)技术是支持向量机的一类变体，其主要思想为通过非线性映射将训练样本映射到高维的特征空间,并在特征空间中寻找一个包含全部或大部分训练样本且体积最小的超球体，以此对训练样本进行分类.SVDD技术在训练样本数不平衡问题和多分类问题等环境中均具有较好的通用性，目前已在故障诊断、图像识别等领域得到了广泛的应用[19-20].然而由于本文问题的复杂性，直接应用SVDD技术还无法得到最终的重调度计划，因此还需要结合其他算法进行进一步的决策.

综合上述分析，本文以物料供给不确定环境下的飞机移动生产线装配作业动态调度问题为研究对象，结合SVDD技术与局部前瞻搜索算法，提出了基于SVDD的动态调度算法(DS-SVDD),对飞机移动生产线中出现物料配送延期的情况快速有效地进行实时重调度，并以资源投入的增量和与模板计划的偏差为目标函数,建立评价指标.最后,以某型号支线客机驾驶舱装配工位的实时调度为应用背景，验证了所提出算法的有效性.

1 问题描述及数学模型

1.1 问题描述

物料供给不确定环境下的飞机移动生产线动态调度问题，是在物料配送延期或现场物料不符合要求等对装配作业按计划执行产生影响的突发情况下，通过实时重调度优化决策未装配作业的开始执行时间，以减少与模板装配计划的偏差和由此产生的额外资源投入，从而达到最小化重调度成本的目标.物料供给不确定环境下的飞机移动生产线动态调度问题的假设与说明如下：

(1)如图1所示，飞机移动生产线被划分为多个连续的虚拟大工位，为了保证生产线有序稳定运行，每架飞机在进入下一工位前必须完成当前工位内的全部装配作业J={1,2,…,n}.其中任意作业j∈J的模板装配计划开始时间为TBS,j，执行工期为tj，完成时间TBF,j=TBS,j+tj.Pj表示作业j的紧前作业集合,TES,j、TLS,j、TEF,j和TLF,j分别表示基于关键路径法得到的作业最早开始时间、最晚开始时间、最早完成时间和最晚完成时间.增加作业0和作业n+1表示虚作业，虚作业执行时间为0，且不占用任何资源.

图1 飞机移动生产线布局图Fig.1 Layout of aircraft moving assembly line

(2)对时间进行离散化处理，时间集合为D={1,2,…,TC}，TC表示移动生产线的生产节拍.

(3)飞机装配过程中需要多类可更新资源，包括装配工人、各种工装设备、现场物料配送工具以及线边存放空间等，记可更新资源种类为R={1,2,…,K}，任意时刻第k种资源总量为Rk，消耗资源k的单位成本为wR,k，rjk表示单位时间内作业j消耗资源k的数量.

(4)设一个生产节拍内出现的物料供给延期扰动集合用q∈Q={0,1,2,…,γ}表示，定义q=0为没有扰动产生，生产线执行模板装配计划.第q次扰动发生的时刻为dq，JC,q、JI,q和JU,q分别表示第q次扰动产生时刻已完成的作业集合、正在执行的作业集合和未开始的作业集合.假设第q次扰动信号产生后，物料预计可送达时间更新为TM,jq.重调度后，资源k超出原有资源上限的需求量为RE,kd.

(5)本文仅考虑扰动产生后物料送达时刻不超过作业最晚开始时间TLS,j的情形.若某项作业的物料供给晚于TLS,j，则在相应的工位内无法为该装配作业安排可行的装配开始时间，生产线必须减速甚至停线进行应急处理.

1.2 数学模型

本节构建了物料供给不确定环境下的飞机移动生产线动态调度问题的数学模型，其中目标函数如式(1)所示，要求动态调度后装配计划与模板装配计划的偏差产生的成本和增加的资源投入成本最小.根据企业的实际需求可为两类成本设定不同的权重系数wR和wD，并采用加权求和的标量化方法将两类量纲不同的目标值转化为单目标函数.其中wR表示额外增加的单位资源成本，wD表示与模板装配计划的单位时间偏差成本.目标函数受式(2)～(8)的约束.

(1)

s.t.

(2)

a∈Pj,∀j∈J,∀q∈Q

(3)

(4)

∀d∈D,∀k∈K,∀q∈Q

(5)

(6)

∀j∈JC,q∪JI,q,∀q∈Q

(7)

(8)

式(2)表示作业一旦开始不允许抢占，必须连续执行直到完成；式(3)定义了作业间的时序约束关系，一项作业必须在其所有的紧前作业全部完成后才能执行；式(4)表示作业必须在其物料可获得后才能开始装配；式(5)计算了任意时刻所有执行的作业对资源的需求量超出该资源供应上限的值；式(6)约束了该工位的任意作业必须在生产节拍内完成；式(7)表示产生扰动的时刻已完成和正在执行的装配作业不受影响，其开始时间等于前一次产生扰动后重调度得到的装配计划开始时间；式(8)定义了动态决策变量的可行域.

2 动态调度方法设计

针对物料供给不确定环境下飞机移动生产线动态调度问题的特点，结合SVDD技术与局部前瞻搜索算法，提出了基于SVDD的动态调度算法(DS-SVDD).该算法的基本框架包括离线SVDD模型的训练和在线实时调度两部分.其核心思想为：离线阶段，通过CPLEX和元启发式算法对不同物料延期情况下的模型进行求解，得到的优化结果作为样本将装配作业分为延期、提前和按计划执行3类策略,并训练3个相应的SVDD超球模型；在线阶段若出现物料供给延期,则利用训练好的模型并结合当前装配系统和物流系统的实时状态,决策装配作业的最佳策略是延期、提前或按原计划执行，然后对延期和提前的作业通过局部前瞻搜索算法进行重调度，从而获得更新后的作业调度方案.基于SVDD的动态算法框架如图2所示，具体模块在下文详细阐述.

2.1 离线训练SVDD模型

2.1.1生成训练样本

在离线阶段，系统通过物料延期扰动模拟器对装配系统的模板装配计划产生随机扰动，即模拟物料配送的延期过程，从而得到相应的动态调度模型.求解该模型的最优或近优解，可以获得任意未装配作业j∈JU,q在该系统状态下的特征向量Xm(m=1,2,…,Μ)对应的最优(近优)重调度方案Ym，将其作为一组训练样本(Xm,Ym).

图2 基于SVDD的动态调度算法基本框架Fig.2 Framework of SVDD-based dynamic scheduling algorithm

式中:ddis和jdis分别表示产生物料供给延迟的时刻及其对应的装配作业;TS,J-ddis=[TS,1-ddis,TS,2-ddis,…,TS,n-ddis]，表示各作业的计划开始时刻与扰动发生时刻的差值;TM,J-ddis=[TM,1-ddis,TM,2-ddis,…,TM,n-ddis]，代表作业的预计送达时刻与发生扰动时刻的差值;TS,J-ddis和TM,J-ddis综合反映了扰动产生后若各作业按原计划执行其物料供给时间的紧张程度.

Ym=γj|γj∈{-1,0,1}，其数值分别代表作业j在重调度后的最优(近优)方案中的执行策略.

Ym首先采用CPLEX软件对动态模型进行求解，但由于该问题属于NP-hard问题，CPLEX无法保证所有训练样本在合理时间内获得最优解.为了提高训练样本的生成效率，若CPLEX计算时间超过0.5 h(1 800 s)则调用文献[21]设计的免疫算法求解近优解.特别说明，由于文献[21]的优化目标仅为资源投入的增量，为了符合本文的目标函数，在免疫算法迭代过程中，以资源投入的增量和与模板计划的偏差双目标作为适应度函数.Μ个样本形成训练样本集Str={(Xm,Ym)|m=1,2,…,Μ}.

2.1.2训练SVDD模型

根据重调度后Ym值所对应的3种不同方案，对训练样本集Str通过SVDD分类模型进行学习,可以分别得到3个超球体SA(提前执行的作业集合)、SP(按原计划执行的作业集合)和SD(延期执行的作业集合).SVDD的基本原理为对给定的训练数据集Str={X1,X2,…,XΜ}在高维空间中寻找一个如式(9)所示包含所有数据的最小超球面，且要求该超球的半径RS尽可能小，其中a为超球球心，C为折衷参数.为了防止过拟合，通过引入松弛变量ξl允许训练集的部分异常点落在超球面外，即满足式(10)约束.

通过拉格朗日乘子法构造拉格朗日函数

(11)

从而可得原问题的对偶问题如式(12)和(13)所示.

(12)

(13)

综上所述，SVDD分类模型的训练主要包括以下步骤：

步骤1 选择输入的特征向量Xm，收集训练样本集Str.

步骤2 根据训练样本集Ym值所对应的3种不同重调度策略，将作业的特征向量Xm映射到高维空间中，并通过求解式(12)和(13)分别得到3种不同调度策略下SVDD超球模型的球心aSA、aSP、aSD，半径RSA、RSP、RSD和支持向量αSA、αSP、αSD.

步骤3 通过步骤2得到的模型参数分别建立提前执行、按计划执行和延期执行的装配作业SVDD超球模型.

2.2 在线实时调度决策

2.2.1根据SVDD分类模型选择调度策略

(14)

SVDD分类模型选择调度策略的具体步骤如下：

步骤1 在物料供给延期的扰动点为每个未开始装配的作业生成特征向量Xm.

步骤2 将作业的特征向量Xm输入到SVDD分类模型中，并通过式(14)计算各测试样本分别到3个SVDD超球模型球心的距离RΕ,SA、RΕ,SP、RΕ,SD并据此计算相对距离εΕ,SA、εΕ,SP、εΕ,SD.

步骤3 取3个相对距离中的最小值确定测试样本所属的SVDD超球，从而对作业的提前、按计划或延期执行做出相应的决策.

2.2.2局部前瞻搜索算法

经过SVDD模型分类后，所有未装配的作业根据输出的Ym值被重新分为提前执行(Ym=-1)、按原计划执行(Ym=0)和延期执行(Ym=1)3类，因此下一步需要给出Ym=-1和Ym=1两类作业的具体提前和延期时长.本文设计了局部前瞻搜索算法对作业提前和延期的时间进行决策，其优化机理如图3所示.图3a为某工位10项作业的模板装配计划，其中作业4的物料在时刻d=2出现了配送延期(即ddis=2);经过SVDD模型分类后各装配作业的重调度方案如图3b所示，其中作业4、7、10需要延期装配，作业5需要提前装配，其余作业按原计划装配，因此仅需要对作业4、5、7、10的具体提前/延期时间进行决策.对于作业4，由于其在装配时间上可能与作业5、7存在重叠，因此将这3个作业的开始时间的全部可能组合列举如图3c所示.对所有的组合计算局部最优目标函数值，选择局部目标函数值最小的组合中作业4的开始时间TS,j=4=7作为作业4的开始时间.同理，对于作业5，考察在装配时间上可能与其发生重叠的作业7、10，对这3个作业进行局部前瞻搜索,从而确定作业5的开始时间.依次执行,直至确定完全部作业的开始时间.

a 模板装配计划甘特图

b SVDD分配模型重调度策略

c 装配开始时间组合方式

定义符合SC,TS,J为作业集合J的可开始执行时间组合，STS,J为作业集合J重调度后的开始执行时间.前瞻搜索算法的具体步骤如下：

步骤1 从SVDD分类模型获取需要提前/延期的作业集合Ω，并按原计划开始时间进行升序排列.Ω={jU,i|i=1,2,…,I}.令i=1，SC,TS,j=∅.

步骤2 令i′=i+1.若jU,i为需要提前的作业，在关键路径(CPM)和物料供给时间等其他约束下的最大提前期TAL,i=max{TES,i,TM,i,ddis}，最小提前期TAR,i=TBS,j，提前区间tA,i=[TAL,i,TAR,i]，令TPL,i=TAL,i，TPR,i=TAR,i，作业可开始区间tP,i=tA,i；若jU,i为需要延期的作业，最小延期时刻TDL,i=max{TBS,i+1,TM,i}，最大延期时刻TDR,i=TLS,j，延迟区间tD,i=[TDL,i,TDR,i]，令TPL,i=TDL,i，TPR,i=TDR,i，作业可开始区间tP,i=tD,i.

步骤3 若[TPL,i,TPR,i+ti]∩[TPL,i′,TPR,i′+ti′]≠∅，SC,TS,j=SC,TS,j∪tP,i∪tP,i′，转步骤4；否则直接转步骤4.

步骤4 若i<|Ω|-1且i′<|Ω|，i′=i′+1，转步骤3；若i<|Ω|-1且i′=|Ω|，转步骤5；若i=|Ω|-1，转步骤6.

步骤5 计算SC,TS,j中所有组合的局部目标最优值，选择目标函数最小的组合Copt,TS,J中作业i的开始时间作为重调度后作业i的开始时间，i=i+1，SC,TS,j=∅，转步骤2.

步骤6 计算SC,TS,j中所有组合的局部目标最优值，选择目标函数最小的组合Copt,TS,J中作业i和i′的开始时间作为重调度后作业i和i′的开始时间，转步骤7.

步骤7 输出所有未装配作业重调度后的开始时间STS,J.

3 实例应用及分析

3.1 实例参数和实验平台

本文以某型号支线客机驾驶舱装配工位的实时调度为例对算法进行验证.该工位共包含41项装配作业，其中作业1与作业41表示虚作业，模板装配计划及作业间的时序约束关系如表1所示.本文主要考虑人力资源R1、关键设备资源R2、物料配送能力R3和线边空间存储能力R4等4类对飞机生产过程影响较大的资源类型，各类资源的上限分别为[12,7,8,12].本文所有实验均通过程序MATLAB(2016b)平台进行，计算机配置为Intel i7-4790处理器，3.60 GHz主频，8G内存.获取训练样本使用的CPLEX软件版本号为12.7.1.

表1 驾驶舱装配工位模板装配计划Tab.1 Template assembly order of cockpit assembly workstation

注：紧后作业一栏中的作业为简写，例如作业2表示作业编号为AO140002的作业.

3.2 SVDD模型分类效果验证

通过2.1.1节描述的模拟器产生随机扰动与优化算法结合的方式，共生成Μ=100 000组训练样本STR={(Xm,Ym)|m=1,2,…,Μ}，同时根据2.1.2节总结的步骤将其输入SVDD分类模型中进行学习.决定SVDD分类模型效果的两个重要参数高斯核函数σ和拒绝率Rej均通过十折交叉验证(cross validation)确定，经交叉验证后的模型分类准确率可达88.04%.运用训练好的SVDD分类模型对飞机移动生产线动态调度问题进行测试，单次扰动情况下分类的CPU运行时间均值为0.26 s.因此，该SVDD分类模型在准确率和响应时间上均能较好地适用于实际生产调度.

3.3 调度性能比较

为了有效地评价本文所提出的DS-SVDD算法的有效性，根据装配线的实际情况，对系统随机产生物料配送延期扰动，并通过DS-SVDD算法进行求解，同时将得到的结果与其他两种典型算法求解的结果进行对比.TR(total rescheduling)表示完全重调度算法，算法核心思想与文献[21]类似，当物料配送延期发生后，通过免疫算法重新对所有未装配作业的开始时间进行搜索,以获得较优的作业开始时间组合；RS(right shift)表示右移算法，为实际生产中常用的一种简单有效的修复规则，将发生物料延期的作业的开始时间推迟至物料送达时刻，同时后续所有作业也依次顺延至各自紧前作业全部完成后开始执行.在其余条件相同情况下，分别考虑扰动发生的次数、调度目标间的权重等影响因素，结合目标函数值对3类算法进行评价.

3.3.1单次扰动环境下的算法性能对比

取wR=0.5，wD=0.5.进行10组试验，每组试验在装配周期内为生产线随机产生1次物料配送延期扰动，3类算法的数值实验对比结果如表2所示.其中,目标函数值一栏FR、FD、F分别表示各类算法得到的资源投入增量产生的成本、作业执行时间与模板计划偏差产生的成本及总成本；GAP栏分别记录了TR和RS两类对比算法与本文提出的DS-SVDD算法总成本差值百分比.通过DS-SVDD算法与TR算法的对比可以看出，DS-SVDD算法在求解绝大部分算例时结果优于TR算法，将由物料供给不确定引起的总成本增量均值降低了2.64%，说明DS-SVDD算法对作业进行重调度具有一定的优势.同时，相比TR算法耗时较长的缺陷，DS-SVDD算法平均仅需要1.82 s即可得到重调度的结果，其在实际的生产环境中具有更好的快速响应能力.在与RS算法对比中，DS-SVDD算法的成本均值降低了28.30%，在某些特殊算例中甚至高达84.05%，而其CPU计算时间均值仅增加了1 s，说明DS-SVDD相比于传统的修复算法更具优势.

表2 单次扰动环境下的算法性能对比Tab.2 Performance comparison of algorithms for single disruption

3.3.2多次扰动环境下的算法性能对比

由于飞机移动生产线的生产节拍较长，在1个生产节拍内可能出现多个作业所需物料延迟配送的情况.据此，本文对生产线模拟产生多次物料配送延期，以测试算法在多次扰动环境下的调度性能.取wR=0.5，wD=0.5，进行10组试验，每组试验在装配周期内为生产线随机产生8次物料配送延期扰动，记录10组试验中每类算法重调度的目标函数均值，数值实验对比结果如图4所示.从图4可以看出，DS-SVDD算法在各次扰动后得到的结果均优于TR和RS算法的调度结果.随着扰动次数的增多，DS-SVDD算法与RS算法求解结果差距越来越明显.另一方面，DS-SVDD算法在求解效率远高于TR算法的情况下，仍然能够得到略优于TR算法的目标函数值，进一步证明了DS-SVDD算法在多次扰动环境下求解效率和效果上的双重优势.

图4 多次扰动环境下的算法性能对比Fig.4 Performance comparison of algorithms for a series of disruptions

3.3.3不同目标权重比下的算法性能对比

在实际进行重调度决策时，额外的资源投入成本和与模板装配计划偏差产生的成本权重往往不是固定的，需要根据企业的实际需求确定.因此，本节通过改变目标函数中两类成本的权值，对DS-SVDD算法的适应能力进行测试.设定两类成本的权重之和为1，将资源投入成本从0逐渐增大至1，同时记录3种算法求得的目标函数均值以及相应的两类成本均值，对比结果如图5所示.由图5可得，随着资源投入成本权重的增加，目标函数值均逐渐降低.DS-SVDD算法在不同权重比下得到的目标函数均值整体优于TR算法和RS算法.当资源投入成本权重为0时，即仅以重调度计划与模板偏差作为单目标函数时，3类算法求得的结果相差不大，DS-SVDD算法没有明显的优势.当资源投入成本权重为1时，即仅以资源增加的成本作为单目标函数时，DS-SVDD算法和TR算法均具有较好的调度效果，且远优于RS算法.而当两类目标的权重比较为均衡时，DS-SVDD算法在求解性能上相比其他两类算法具有一定的优越性.因此，DS-SVDD算法可适用于不同目标权重比下的飞机移动生产线动态调度问题优化.