文章快速检索    
  同济大学学报(自然科学版)  2019, Vol. 47 Issue (5): 723-730, 738.  DOI: 10.11908/j.issn.0253-374x.2019.05.019
0

引用本文  

陆志强, 胡鑫铭, 朱宏伟. 物料供给不确定环境下的飞机移动生产线动态调度方法[J]. 同济大学学报(自然科学版), 2019, 47(5): 723-730, 738. DOI: 10.11908/j.issn.0253-374x.2019.05.019.
LU Zhiqiang, HU Xinming, ZHU Hongwei. Dynamic Scheduling Method for Aircraft Moving Assembly Line Under Uncertain Supply of Material[J]. Journal of Tongji University (Natural Science), 2019, 47(5): 723-730, 738. DOI: 10.11908/j.issn.0253-374x.2019.05.019

基金项目

国家自然科学基金(61473211,71171130)

第一作者

陆志强(1968—),男,教授,博士生导师,工学博士,主要研究方向为物流与供应链建模与优化、生产工程等. E-mail: zhiqianglu@tongji.edu.cn

文章历史

收稿日期:2018-07-14
物料供给不确定环境下的飞机移动生产线动态调度方法
陆志强 , 胡鑫铭 , 朱宏伟     
同济大学 机械与能源工程学院,上海 201804
摘要:飞机装配所需的物料种类复杂且数量巨大,其准时供给往往存在较大的不确定性.为了有效解决物料供给不确定环境下的飞机移动生产线动态调度问题,将机器学习中的支持向量数据描述技术(SVDD)与传统的调度方法相结合,提出了基于SVDD的动态调度算法.通过软件CPLEX和元启发式算法求解不同物料供给延期情形下的调度模型,并将得到的优化结果作为样本对SVDD分类模型进行离线训练.在实时调度阶段, 根据SVDD模型实现作业的提前、延期或准时执行的分类.基于该分类结果,利用局部前瞻搜索算法进一步对提前和延期作业的具体开始执行时间做出决策.数值实验结果证明了所提出的算法在响应速度和求解效果上均能满足实际飞机移动生产线动态调度的需求.
关键词飞机移动生产线    动态调度    机器学习    支持向量数据描述    局部前瞻搜索    
Dynamic Scheduling Method for Aircraft Moving Assembly Line Under Uncertain Supply of Material
LU Zhiqiang , HU Xinming , ZHU Hongwei     
School of Mechanical Engineering, Tongji University, Shanghai 201804, China
Abstract: Due to the diversity and large quantity of material in aircraft assembly, there tend to be great uncertainties in just in time supply of material. To effectively solve the dynamic scheduling problem for aircraft moving assembly line with uncertain supply of material, the support vector data description (SVDD) in machine learning field is combined with the traditional scheduling method, and a dynamic scheduling approach based on SVDD is proposed. First, CPLEX and meta-heuristic are used to solve the mathematical model under different material supply delay conditions, and the optimized results are taken as the samples to train the SVDD classification model. In the real-time scheduling phase, the trained SVDD model is used to make the classified decisions on "advance", "delay", or "on schedule". Based on the results of classification, a local look-ahead searching method is presented to make a further decision on specific starting time of jobs advanced or delayed. The computational results prove that the proposed algorithm can meet the actual requirement of dynamic scheduling for aircraft moving assembly line in both response speed and solution effect.
Key words: aircraft moving assembly line    dynamic scheduling    machine learning    support vector data description    local look-ahead searching    

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

现有文献对确定性环境下的飞机移动生产线调度相关问题已经进行了较为充分的研究[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}.其中任意作业jJ的模板装配计划开始时间为TBS, j,执行工期为tj,完成时间TBF, j=TBS, j+tj.Pj表示作业j的紧前作业集合, TES, jTLS, jTEF, jTLF, 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, krjk表示单位时间内作业j消耗资源k的数量.

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

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

本文研究问题的动态决策变量为$ x_{jd}^{(q)} = \{ \begin{array}{*{20}{l}} 1\\ 0 \end{array}|\forall j \in J, \forall d \in D, \forall q \in Q:0, 1$变量,发生第q次扰动时,若重调度后作业j的开始时间为d,则$ x_{jd}^{(q)} = 1$; 否则$ x_{jd}^{(q)} = 0$.

1.2 数学模型

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

$ \begin{array}{l} \min Z = {w_{\rm{R}}}\left( {\sum\limits_{k = 1}^K {\sum\limits_{d = 1}^{{T_{\rm{C}}}} {{w_{{\rm{R}},k}}{R_{{\rm{E}},kd}}} } } \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;{w_{\rm{D}}}\sum\limits_{j = 1}^n {\left( {\left| {\sum\limits_{d = 1}^{{T_{\rm{C}}}} {x_{jd}^{(q)}} d - {T_{{\rm{BS}},j}}} \right|} \right)} \end{array} $ (1)
$ \begin{array}{l} {\rm{s}}.{\rm{t}}.\\ \;\;\;\;\;\;\sum\limits_{d = 1}^{{T_{\rm{C}}}} {x_{jd}^{\left( q \right)}} = 1,\forall j \in J,\forall q \in Q \end{array} $ (2)
$ \begin{array}{l} \sum\limits_{d = 1}^{{T_{\rm{C}}}} {x_{jd}^{(q)}} d \ge \sum\limits_{d = 1}^{{T_{\rm{C}}}} {x_{ad}^{(q)}} \left( {d + {t_a}} \right),\\ \;\;\;\;\;\;a \in {P_j},\forall j \in J,\forall q \in Q \end{array} $ (3)
$ \sum\limits_{d = 1}^{{T_{\rm{C}}}} {x_{jd}^{(q)}} d \ge {T_{{\rm{M}},jq}},\forall j \in J,\forall q \in Q $ (4)
$ \begin{array}{l} \sum\limits_{j = 1}^n {{r_{jk}}} \sum\limits_{\tau = d - {t_j} + 1}^d {x_{j\tau }^{(q)}} - {R_k} = {R_{{\rm{E}},kd}},\\ \;\;\;\;\;\;\;\;\forall d \in D,\forall k \in K,\forall q \in Q \end{array} $ (5)
$ \sum\limits_{d = 1}^{{T_{\rm{C}}}} {x_{jd}^{(q)}} d + {t_j} \le {T_{\rm{C}}},\forall j \in J,\forall q \in Q $ (6)
$ \begin{array}{l} \sum\limits_{d = 1}^{{T_{\rm{C}}}} {x_{jd}^q} d = \sum\limits_{d = 1}^{{T_{\rm{C}}}} {x_{jd}^{(q - 1)}} d,\\ \;\;\;\;\;\;\forall j \in {J_{{\rm{C}},q}} \cup {J_{{\rm{I}},q}},\forall q \in Q \end{array} $ (7)
$ x_{jd}^{(q)} = \{ 0,1\} ,\forall j \in J,\forall d \in D,\forall q \in Q $ (8)

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

2 动态调度方法设计

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

图 2 基于SVDD的动态调度算法基本框架 Fig.2 Framework of SVDD-based dynamic scheduling algorithm
2.1 离线训练SVDD模型 2.1.1 生成训练样本

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

$ \begin{aligned} X_{m}=&\left(j, d_{\text { dis }}, j_{\text { dis }}, w_{\mathrm{R}}, w_{\mathrm{D}}, T_{\mathrm{S}, J}-\right.\\ & d_{\mathrm{Dis}}, T_{\mathrm{M}, J}-d_{\mathrm{dis}} ) \end{aligned} $

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

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

$ {\gamma _j} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} - 1,\\ 0,\\ 1, \end{array}&\begin{array}{l} 提前执行\\ 按原计划执行\\ 延期执行 \end{array} \end{array}} \right. $

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)约束.

$ \min F\left( {{R_S},a,{\xi _l}} \right) = R_S^2 + C\sum\limits_l {{\xi _l}} $ (9)
$ {\rm{s}}.{\rm{t}}.\;{\left\| {{X_l} - a} \right\|^2} \le R_S^2 + {\xi _l},{\xi _l} \ge 0 $ (10)

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

$ \begin{array}{l} L\left( {{R_S},a,{\alpha _l},{\xi _l}} \right) = R_S^2 + C\sum\limits_l {{\xi _l}} - \\ \sum\limits_l {{\alpha _l}} \left[ {R_S^2 + {\xi _l} - {{\left( {{X_l} - a} \right)}^{\rm{T}}}\left( {{X_l} - a} \right)} \right] - \sum\limits_l {{\gamma _l}} {\xi _l} \end{array} $ (11)

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

$ \max F' = \sum\limits_l {{\alpha _l}} K\left( {{X_l},{X_l}} \right) - \sum\limits_{l,l'} {{\alpha _l}} {\alpha _{l'}}K\left( {{X_l},{X_{l'}}} \right) $ (12)
$ {\rm{s}}.\;{\rm{t}}.\;\;\sum\limits_l {{\alpha _l}} = 1,0 \le {\alpha _l} \le C $ (13)

式中:K(Xl, Xl)表示核函数.由于高斯核SVDD与其他类型SVDD相比具有较好的学习能力和泛化能力,因此本文采用高斯核函数K(Xl, Xl)=exp(-||XlXl2||/σ2).

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

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

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

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

2.2 在线实时调度决策 2.2.1 根据SVDD分类模型选择调度策略

在实时调度阶段,调度系统不断从制造执行系统(manufacturing execution system, MES)获取装配系统和物流系统的实时信息.当系统发出物料配送延迟等扰动信号后,系统将为该工位内每个未装配作业生成一个当前状态下的特征向量Xm=(j, ddis, jdis, wR, wD, TS, Jddis, TM, Jddis),并将其作为SVDD分类模型的输入.通过式(14)分别计算测试样本Ε到3个超球球心的欧式距离RΕS|S∈{SA, SP, SD},定义样本Ε到超球球心的相对距离为εΕ, S=RΕ, S2/RS2|S∈{SA, SP, SD}.通过相对距离的比较将各超球体转化为单位超球体,可避免在重合区域半径小的超球具有不合理的优先权,从而能客观反映出样本Ε在超球高维特征空间中的分布位置.计算相对距离的最小值εΕ, S*=min{εΕ, SA, εΕ, SP, εΕ, SD},则认为样本更靠近超球S*,据此给出该作业提前、按计划或是延期执行的调度策略决策.

$ \begin{array}{*{20}{c}} {{{\left\| {E - {a_S}} \right\|}^2} = K(E,E) - 2\sum\limits_l {{{\left( {{\alpha _S}} \right)}_l}} K\left( {E,{X_i}} \right) + }\\ {\sum\limits_{l,l'} {{{\left( {{\alpha _S}} \right)}_l}} {{\left( {{\alpha _S}} \right)}_{l'}}K\left( {{X_l},{X_{l'}}} \right) \le R_S^2} \end{array} $ (14)

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

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

步骤2  将作业的特征向量Xm输入到SVDD分类模型中,并通过式(14)计算各测试样本分别到3个SVDD超球模型球心的距离RΕ, SARΕ, SPRΕ, 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的开始时间.依次执行, 直至确定完全部作业的开始时间.

图 3 局部前瞻算法优化机理 Fig.3 Optimization mechanism of local look-ahead searching

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

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

步骤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, iTPR, 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, iTPR, i=TDR, i,作业可开始区间tP, i=tD, i.

步骤3  若[TPL, i, TPR, i+ti]∩[TPL, i, TPR, i+ti]≠$ \emptyset $SC, TS, j=SC, TS, jtP, itP, 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=$ \emptyset $,转步骤2.

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

下载CSV 表 1 驾驶舱装配工位模板装配计划 Tab.1 Template assembly order of cockpit assembly workstation
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所示.其中, 目标函数值一栏FRFDF分别表示各类算法得到的资源投入增量产生的成本、作业执行时间与模板计划偏差产生的成本及总成本; 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相比于传统的修复算法更具优势.

下载CSV 表 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算法可适用于不同目标权重比下的飞机移动生产线动态调度问题优化.

图 5 不同目标权重下的算法性能对比 Fig.5 Performance comparison of algorithms with different objective weights
4 结论

(1) 以飞机移动生产线为应用背景,考虑实际生产中存在的物料供给延期情形,构建了物料供给不确定环境下的飞机移动生产线动态调度问题的数学模型.

(2) 结合机器学习方法与传统的调度技术,提出了基于SVDD的动态调度算法对发生扰动的装配线进行实时重调度.数值实验证明了所提出的算法相比完全重调度算法和修复算法具有较好的求解性能和适应性,能够适用于飞机这类存在大量并行装配作业的生产线实时调度问题.

(3) 后续将进一步考虑飞机生产过程中存在的其他不确定性因素,同时结合历史数据对不确定性因素进行进一步分析,以构建更加完善的不确定环境下的飞机移动生产线动态调度模型,为飞机装配提供更高效的决策.

参考文献
[1]
ABDINNOUR S. Hawker beechcraft uses a new solution approach to balance assembly lines[J]. Interfaces, 2011, 41(2): 164 DOI:10.1287/inte.1100.0535
[2]
LU H, LIU X, PANG W, et al. Modeling and simulation of aircraft assembly line based on quest[J]. Advanced Materials Research, 2012, 569(2): 666
[3]
SHAN S, HU Z, LIU Z, et al. An adaptive genetic algorithm for demand-driven and resource-constrained project scheduling in aircraft assembly[J]. Information Technology & Management, 2017, 18(1): 41
[4]
郑倩, 奚立峰. 飞机移动生产线作业调度问题的启发式算法[J]. 工业工程与管理, 2015, 20(2): 116
ZHENG Qian, XI Lifeng. Heuristics for aircraft moving assembly line scheduling problem[J]. Industrial Engineering & Management, 2015, 20(2): 116 DOI:10.3969/j.issn.1007-5429.2015.02.018
[5]
胡鑫铭, 陆志强. 考虑物料配送的飞机移动生产线调度问题优化[J]. 北京航空航天大学学报, 2017, 43(12): 2573
HU Xinming, LU Zhiqiang. Optimization of aircraft moving assembly line scheduling problem considering material delivery[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(12): 2573
[6]
BANERJEE A G, YUND W, YANG D, et al. A hybrid statistical method for accurate prediction of supplier delivery times of aircraft engine parts[C]//Proceedings of the ASME 2015 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference. Boston: ASME, 2015: 286-295.
[7]
CAI H X, DAI M Y, YU T. Material coding for aircraft manufacturing industry[J]. Journal of Aerospace Technology & Management, 2014, 6(2): 183
[8]
ZHENG Y, HAN D, NI Y, et al. Research and application of bottom-up route-based product data conformity inspection approach for civil aircraft[J]. International Journal of Computer Integrated Manufacturing, 2014, 27(6): 591 DOI:10.1080/0951192X.2013.834464
[9]
YAO S, JIANG Z, LI N. A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals[J]. Computers & Operations Research, 2012, 39(5): 939
[10]
BENNELL J A, MESGARPOUR M, POTTS C N. Dynamic scheduling of aircraft landings[J]. European Journal of Operational Research, 2017, 258(1): 315 DOI:10.1016/j.ejor.2016.08.015
[11]
PAUL S K, SARKER R, ESSAM D. A quantitative model for disruption mitigation in a supply chain[J]. European Journal of Operational Research, 2017, 257(3): 881 DOI:10.1016/j.ejor.2016.08.035
[12]
SOBEYKO O, MONCH L. Heuristic approaches for scheduling jobs in large-scale flexible job shops[J]. Computers & Operations Research, 2016, 68: 97
[13]
SAHIN C, KUVVETLI Y. Differential evolution based meta-heuristic algorithm for dynamic continuous berth allocation problem[J]. Applied Mathematical Modelling, 2016, 40(23/24): 10679
[14]
PARK J, MEI Y, SU N, et al. An investigation of ensemble combination schemes for genetic programming based hyper-heuristic approaches to dynamic job shop scheduling[J]. Applied Soft Computing, 2018, 63: 72 DOI:10.1016/j.asoc.2017.11.020
[15]
YANG G, TANG W, ZHAO R. An uncertain furniture production planning problem with cumulative service levels[J]. Soft Computing, 2017, 21: 1041 DOI:10.1007/s00500-015-1839-6
[16]
NASIRI M M, YAZDANPARAST R, JOLAI F. A simulation optimisation approach for real-time scheduling in an open shop environment using a composite dispatching rule[J]. International Journal of Computer Integrated Manufacturing, 2017, 30(46): 1239
[17]
WANG K, CHOI S H, QIN H, et al. A cluster-based scheduling model using SPT and SA for dynamic hybrid flow shop problems[J]. International Journal of Advanced Manufacturing Technology, 2013, 67(9/10/11/12): 2243
[18]
ZHOU B H, XU J H. An adaptive SVM-based real-time scheduling mechanism and simulation for multiple-load carriers in automobile assembly lines[J]. International Journal of Modeling Simulation & Scientific Computing, 2017, 8(4): 1
[19]
LIU X, LI M J, SUN Y L, et al. Support vector data description for weed/corn image recognition[J]. Journal of Food Agriculture & Environment, 2010, 8(1): 214
[20]
DUAN L, XIE M, BAI T, et al. A new support vector data description method for machinery fault diagnosis with unbalanced datasets[J]. Expert Systems with Applications, 2016, 64: 239 DOI:10.1016/j.eswa.2016.07.039
[21]
VERBEECK C, PETEGHEM V V, VANHOUCKE M, et al. A metaheuristic solution approach for the time-constrained project scheduling problem[J]. Or Spectrum, 2017, 39(2): 353 DOI:10.1007/s00291-016-0458-7