基于神经网络和知识库的物料配送动态调度

周炳海 朱柘鑫

摘   要：为有效地解决汽车混流装配线中多载量小车物料配送的动态调度问题，提出基于知识库和神经网络的调度方法. 首先，对汽车装配线物料配送的动态调度问题进行描述，建立以装配线产量和多载量小车的物料搬运距离作为衡量指标的目标函数. 然后通过Plant Simulation软件生成针对汽车混流装配线的仿真数据并对神经网络模型进行离线训练，在实时阶段利用神经网络模型和知识库实现多载量小车最优调度规则的选取. 实验结果表明：所提出的调度规则选取方法选择的调度规则大多为最优调度规则，以较低的调度规则计算复杂性确保了调度的实时性能，能够很好地应对动态环境的变化，从而有效提升了多载量小车的动态调度水平.

关键词：汽车混流装配线;动态调度;物料搬运;神经网络;人工智能

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

Abstract：In order to tackle the dynamic scheduling problem of tow trains in mixed-model assembly lines， a scheduling approach is proposed based on the knowledge base and neural network. Firstly， the dynamic scheduling problem of material delivery in the automotive assembly line is formally described. The throughput of the assembly line and the total delivery distances are selected as components of the objective function. After that，the sample data of mixed-model assembly lines are generated by the Plant Simulation software and are used to train the neural network model offline. Finally， the trained neural network model and the knowledge base are adopted in the real-time scheduling process to select the optimal scheduling rule for tow trains. The experimental results indicate that the scheduling rules selected by the selection method proposed in the paper are mostly the optimal ones. The lower computational complexity of scheduling rules ensures the real-time performance of scheduling. It can cope well with changes in the dynamic environment， thus effectively improving the dynamic scheduling of tow trains.

Key words：mixed-model assembly line;dynamic scheduling;material handling;neural network;artificial intelligence

随着产品与客户需求复杂化、市场多样化等竞争压力的不断增加，汽车制造企业多采用多载量小车（tow train）进行物料配送[1]，提升多载量小车的动态调度水平，实现汽车混流装配线的准时化物料配送，已成为降低汽车制造企业成本的有效措施之一.

制造系统中的物料配送调度问题通常分为静态与动态两个方面[2]. 静态调度指假定在调度前已知所有物料搬运需求，通过运筹学等决策分析方法解决调度的最优化问题. 其中启发式算法以其求解较大规模问题的时间优越性，近年来受到国内外学者的广泛关注. Emde等[3]提出了开放式启发算法及禁忌搜索算法来解决电动小车（Electric Vehicle，EV）厂内循环的物料准时配送问题;文献[4-6]以最小化汽车装配线线边库存和配送次数为目标，研究了物料配送中多载量小车的装载和调度问題，分别提出了基于模拟退火的启发式算法、基于蚁群优化的启发式算法以及改进型粒子群算法.

虽然上述静态调度方法在中大问题规模中能够找到近似最优解，但因其对于制造系统较差的抗干扰性，致使该方法难以应用到实际物料搬运系统的调度中，因此动态调度得到越来越广泛的关注[7]. 其中，机器学习（Machine Learning，ML）作为人工智能的重要分支被广泛应用于动态调度中. 文献[8]和文献[9]均将遗传算法与人工神经网络（Artificial Neural Network，ANN）相结合来解决制造系统中的动态调度问题，并证明了混合算法的有效性与优越性. Zang等[10]开发出一种混合深度ANN调度器，利用其泛化能力处理车间中的调度问题. 文献[2]提出了一种基于支持向量机的方法对多载量小车是否执行搬运任务做出决策.

上述文献主要研究了制造系统中资源分配和派遣决策等问题，对于多载量小车在汽车装配线中搬运任务的动态选择与排序决策问题鲜有涉及. 因此，本文利用神经网络出色的学习能力以及预测准确性[11-12]，结合知识库，引入果蝇优化算法（Fruit Fly Optimization Algorithm，FOA）[13]与广义回归神经网络（General Regression Neural Network，GRNN）[14]，以装配线产量和多载量小车的物料搬运距离作为衡量指标建立数学模型，提出了针对多载量小车的最优调度规则动态选取方法，有效地解决了小车的发车决策、物料配送任务选择决策与物料配送任务排序决策问题.

1   问题描述与模型建立

1.1  问题描述

图1展示了汽车混流装配线的物料搬运系统，暂存于物料超市中的物料由一辆或多辆多载量小车多批次、小批量地送至临近工位. 本文对于多载量小车的动态调度包含以下3方面的决策问题：

1）发车决策问题.当多载量小车位于零件库存区处于“空闲”状态时，调度系统需要决定多载量小车何时处理搬运任务，出发进行物料配送. 最小批量法（Minimum Batch Size rule，MBS-x）[12]为解决此类问题的一个经典规则，表示只有在当前需要执行的搬运任务数量超过最小批量x时，多载量小车才开始出发执行配送任务，否则一直在物料超市等候.

2）物料配送任务选择决策问题.即调度系统做出让多载量小车发车的决策后，如果配送任务的数量超出多载量小车的搬运能力Nc，那么调度系统就需要选择搬运任务进行物料配送.

3）物料配送任务排序决策问题.若调度系统在物料配送任务选择决策中选择了多于一个配送任务，由于本文所述的多载量小车受LIFO约束，所以调度系统必须在搬运过程开始前确定所有零件的配送次序.

由于针对不同的决策问题可以采用相应的调度规则，因此在解决本文的多载量小车动态调度问题时，可在已有的针对各决策问题的调度规则中寻找合适的调度规则组合.

令λ = （α，β，ε），（?α∈A，β∈B，ε∈E）表示上述的调度规则组合，其中α、β、ε表示分别用于发车决策问题、物料配送任务选择决策问题以及物料配送任务排序决策问题的调度规则，A、B、E分别为对应决策问题的调度规则集. λ = （MBS-2，FRFP，SDFD）表示如果搬运任务数量不少于2，那么多载量小车开始执行搬运任务;如果当前搬运任务数量超出多载量小车的搬运能力，它将使用先订购先选择规则（First Reorder First Picked，FRFP）选取搬运任务;最后，在选择了多个搬运任务的情况下，它将使用（Shortest Distance First Delivered，SDFD）规则确定这些任务的搬运次序. 令Λ = {（α，β，ε），（?α∈A，β∈B，ε∈E）}表示存储这种调度规则组合的调度规则集.

1.2  数学模型

为简化此类调度问题，做出如下基本假设：

1）多载量小车在搬运过程中行驶速度v恒定，且不考虑故障或阻塞问题;2）多载量小车由一辆牵引车头和多辆送料车组成，一辆送料车一次只能装载一种零件，且数量一定，记为SPQ（Supply Quantity），对于每种零件，多载量小车每次最多使用一辆送料车;3）空闲的多载量小车在装配线由于缺少零件而停止装配时，立即从物料超市出发执行配送任务;4）多载量小车的装料时间LDT（Loading Time），卸料时间UDT（Unloading Time）（卸料时剩余零件的数量≤0.1SPQi）和UDT′（卸料时剩余零件的数量>0.1SPQi）都为定值，且UDT′ > UDT;5）搬运过程不可中断;6）采用再订购点法作为物料搬运任务生成的方法.

为深入分析问题并进行模型表述，对相关符号及变量定义如下：

装配线可进行M1，M2，…，MH种型号的车辆装配，产品配比m = （ρ1，ρ2，…，ρH），ρ1 + ρ2 +…+ ρH = 1;装配过程需要的零件记为Pi（i = 1，2，…，I）;物料搬运的开始时间为t0;调度的终止时间为tend;调度系统在第k个决策点tk（k = 0，1，2，…，K）时刻，产品配比mk = （ρ1，ρ2，…，ρH）或调度目标权重ωk = （ωM，ωD）发生变化，调度策略需重新调整，其中ωM和ωD分别为装配线产量M 和多载量小车的行驶距离即物料搬运距离 D的权重，且ωM>>ωD;bk = （Mk，Dk）为调度期间[tk，tk+1]中的调度性能，其中Mk、Dk分别为调度期间[tk，tk+1]中的装配线产量和物料搬运距离;IL（i，t）为零件Pi在时刻t的线边库存;csi为零件Pi的平均消耗速度;Pi的再订购点Ri =csi[（di + 2dmax）/v + Nc（LDT + UDT）]，其中di、dmax分别为搬运零件Pi的行驶距离及最远行驶距离;在t时刻，若系统发出Pi的搬运需求，则fi（t） = 1，否则fi（t） = 0;在t时刻，若Pi被选中作为即将开始搬运的零件类型，则gi（t）=1，否则gi（t） = 0;stj为第j次搬运开始的时刻;J为多载量小车在[t0，tend]中所有的物料搬运过程.

由于本文选取装配线产量和多载量小车的物料搬运距离这两个有冲突的衡量指标建立目标函数，因此引入调度目标权重ωk=（ωM，ωD），产量的目标ωM 取正值表示产量越高，调度性能越好;物料搬运距离的目标权重ωD取负值表示距离越长，调度性能越差. 根据权重和的标量化方法，调度目标函数为：

式（1）为该调度模型的目标函数，表示最大化整个调度期间的产量和物料搬运距离的标量化权重和;式（2）表示调度系统的每个调度决策时刻都应早于调度期间的结束时刻;式（3）表示多载量小车每次搬运过程中装载的料箱数不超过它的搬运能力;式（4）表示多载量小车在每次搬运任务执行前都收到不少于一个搬运任务;式（5）表示所有的调度规则组合都从备选调度规则集中选取.

2   动态调度方法

当产品配比和调度目标权重发生变化时，系统采取不同的调度規则会有不同的性能表现[13]，调度性能在所有条件下都最佳的调度规则并不存在. 因此，当动态环境中的产品配比或调度目标权重发生变化时，为了解决本文物料配送系统的动态调度问题，从给定的调度规则集中选择一个使当前装配线调度性能呈最优的调度规则是可行方案.

由于装配线在整个调度期间的调度性能（产量和物料搬运距离）是由产品配比、调度规则及总生产时间决定的，与调度目标权重无关，因此假定总的生产时间以及相关因素不变，调度性能与产品配比和调度规则之间的关系可以表示为（mk←λ）→（M，D）. 对于给定的一条装配线，若各调度期间的产品配比为mk，物料搬运调度系统采用的调度规则为λ，则该装配线的装配产量预计为M，物料搬运距离预计为D. 假定存在一知识库，对所有可能的产品配比以及调度规则的组合存储上述关系，那么对于任意给定的产品配比或调度目标权重，都可通过检索知识库的数据记录，选取最合适的调度规则λ. 然而，产品配比的值域是连续的，知识库中不可能存储全部产品配比所对应的关系式，并且在相等的装配时长中，两个相似的产品配比采取同一调度规则时会得到相似的装配线产量和物料搬运距离. 因此，对于任意未存储在知识库中的给定产品配比mk，可先在知识库中找到与mk最相似的产品配比m，然后利用知识库确定mk在调度目标权重ωk条件下的最优（即使目标函数最大）λ，作为mk在ωk条件下的最优调度规则λk.

为更好地实施上述方案，鉴于由输入层、模式层、求和层和输出层构成且执行Parzen非参数估计的GRNN具有良好的非线性逼近性能和训练方便性，本文提出了一个基于知识库和逻辑混沌初始化的果蝇优化算法（VSCFOA）改进型GRNN调度规则选取方法（VSCFOA-GRNN），如图2所示，其中VSCFOA主要用来优化GRNN平滑因子. 主要包括离线VSCFOA-GRNN训练和基于VSCFOA-GRNN实时决策两个阶段. 在离线训练阶段，调度系统通过仿真获取调度性能指标（产量和物料搬运距离）与产品配比和调度规则之间的关系，构建一个存储此关系的知识库并训练VSCFOA-GRNN神经网络;在实时决策阶段，调度系统通过神经网络选取与当前给定的产品配比mk最相似且存储于知识库中的产品配比m′，检索知识库中记录有关调度性能记录数据，找出使得目标值最大的调度规则λ*，即为最优调度规则.

2.1   离线VSCFOA-GRNN神经网络训练

2.1.1   VSCFOA-GRNN的构建

在离线阶段，由于相似的产品配比在使用同一调度规则时使得装配线呈现相似的调度性能，所以可根据不同产品配比条件下的装配线性能来定义产品配比之间的相似程度：

式中：mk为需要匹配的产品配比;mall为知识库中存储的所有产品配比的集合;为了提高匹配效率，可以将产品配比的搜索范围缩小至mk的θ范围;δ（mk，m）为mk与m的欧氏距离，即在欧氏空间中两点的真实距离.

由式（6）和式（8）可知，为了计算两个产品配比间的相似度从而进行相似性检索，首先需要确定函数，但由于制造系统中产品配比和调度性能间的复杂关系，qλ（mk）的表达式很难准确地给出. 在这种情况下，鉴于广义回归神经网络较强的非线性映射能力与果蝇优化算法的全局寻优能力，本文采用VSCFOA-GRNN对qλ（mk）函数进行逼近. VSCFOA算法通过混沌搜索找到初始最优值，利用步长找到最优味道浓度判定值Si，将Si作为GRNN的平滑因子Spread，通过对GRNN的训练得到输出值，计算输出值与目标值之间的均方误差MSE，MSE的值越小，说明预测模型描述实验数据的性能越好. 通过迭代寻找最优味道浓度值代入GRNN进行函数拟合. 具体步骤如下：

2.1.2   知识库的构建

为了得到相应产品配比与调度规则对应装配线调度性能的关系式，通过Plant Simulation建立了针对装配线物料搬运系统的仿真模型，如图3所示.

该汽车装配线共生产3种车型M1、M2、M3，仿真设19个装配工作站S1 ～ S19，32种零件P1 ～ P32. 该装配线上所有工作站的装配周期为120 s，各工作站的平均失效间隔MTBF为56 min，平均修复时间MTTR为14 s. 多载量小车的数量为3，搬运能力Nc = 3，速度v = 1.48 m/s，LDT = 35.5 s，UDT = 46.6 s，UDT′ = 132.7 s. 将值域连续的产品配比m向量空间均匀离散化为s组不同的产品配比，每个产品配比 mi与不同的调度规则λj作为仿真模型的输入获得相应的装配线产量Mij和物料搬运距离Dij作为仿真结果，并且将（mi λj Mij Dij）作为一组数据存入知识库以备后续检索.    由于不同的λj会导致装配线不同的性能表现，所以对VSCFOA-GRNN进行训练时只可采用同一λj为调度规则的数据.

2.2   实时VSCFOA-GRNN神经网络调度决策

在离线阶段通过仿真构建知识库和训练VSCFOA-GRNN神经网络后，可进入实时阶段进行装配线的物料搬运调度.

在每个调度决策点tk时刻，调度目标权重或装配系统的产品配比发生改变，触发物料搬运系统进行决策，假设此时的产品配比为mk，调度目标权重ωk =（ωM，ωD），那么调度系统可以通过VSCFOA-GRNN神经网络找到与mk最相似的产品配比st（mk）∈mall. 检索知识库得到不同的调度规则在产品配比为st（mk）条件下得到的装配线产量和多载量小车的物料搬运距离，根据式（1）得到目标函数值，选择令目标函数值最大的调度规则λk，即：

3   算法性能仿真分析

3.1   仿真案例参数

参照文献[2]和文献[15]中的相关参数，ωM和ωD的取值分别服从区间[2，4]和[-0.004 5，-0.001 8]内的均匀分布. 产品配比的取值空间离散化为 66 个点，每类产品的生产比例间隔为0.1，即第一类产品的生产比例为ρ1 = 0，0.1，0.2，…，1;第二類产品的生产比例为ρ2 = 0，0.1，0.2，…，1 - ρ1;第三类产品的生产比例为ρ3 = 0，0.1，0.2，…，1 - ρ1 - ρ2. 设定仿真的实验时间为72 h，包含8 h的预热时间. 对各组产品配比和调度规则分别进行5次实验.

3.2   备选调度规则之间的对比

为了进一步说明当产品配比发生改变时，不同的调度规则会对调度性能产生极大的影响，在比较VSCFOA-GRNN神经网络和其他调度方法的性能之前，先对备选调度规则的调度性能进行分析比较. 将66个产品配比每隔两点取出一个，形成22组产品配比，其使用各备选调度规则时的装配线产量和物料搬运距离如图4所示.

3.4   对比VSCFOA-GRNN神经网络与其他神经

网络

神经网络方法可以用来预测不同调度方法的性能，并依此进行调度方法的选择. 为了验证VSCFOA-GRNN方法对不同调度规则性能预测的准确性，利用仿真实验对比VSCFOA-GRNN和基于果蝇优化算法优化的广义回归神经网络（FOA-GRNN）、标准的广义回归神经网络（GRNN）与基础神经网络径向基神经网络（RBF），如表3所示. 改变决策点的个数，即通过增加产品配比和调度目标权重的组数来扩大问题规模，每两个决策点之间的调度期间时长为72 h，每个决策点中的各个神经网络进行10次实验，目标函数取平均值.

对神经网络在不同决策点的平均目标函数值进行对比，通过各神经网络与VSCFOA-GRNN的百分比偏差（PD）来比较其有效性. 由表3可知，VSCFOA-GRNN的预测准确性明显优于其他3种对比网络. 随着问题规模扩大，决策点个数增加，mk和ωk发生变化，此时调度系统利用神经网络在知识库中选取st（mk）. 由于预测偏差导致的st（mk）与实际选取的产品配比mk存在一定误差，理论最优目标函数值与实际目标值则存在偏差，且随着问题规模的扩大，累积偏差值逐渐增大. 由于各神经网络预测性能不同，其对应目标函数值之间的PD随着问题规模的扩大而不断增加. 由此说明，随着问题规模的扩大，VSCFOA-GRNN神經网络的预测优越性愈发明显.

本案例仿真数据为美国通用汽车公司S区部分汽车装配线的真实数据[15]，本节中大规模问题的决策点范围即针对实际生产管理设置. 由图6可知，在实际问题规模中，VSCFOA-GRNN在最优调度规则选取率上呈现出明显的平稳性与高效性. 其在寻优率方面远超其他3种对比神经网络，百分比偏差自衍生的小问题规模向实际问题规模逐步增大，最大差距达19.18%. 同时，VSCFOA-GRNN在最优调度规则选择比率上持平85%以上，下降趋势呈平缓状态，其在实际问题规模中的实用性达标. 通过以上横纵两向对比，VSCFOA-GRNN在解决实际生产中多载量小车动态调度决策问题的有效性得以验证.

4   结   论

本文以多载量小车为主要研究对象，考虑调度目标权重和产品配比可变环境下的动态调度问题，即当产品配比和调度目标权重发生变化时，对多载量小车采取何种调度规则进行决策. 以产量和物料搬运距离作为衡量指标建立目标函数，通过调度性能指标（装配线产量和搬运距离）与产品配比和调度规则之间的关系，利用神经网络寻找与给定产品配比最相似且存储于知识库中的产品配比，利用知识库中的数据进行最优调度规则的选取. 经过实验验证，本文提出的动态调度方法准确率高，调度效果好，对本文的动态环境具有较好的适应能力. 但是，本文仅着眼于单个物流区域中多载量小车的动态调度问题，今后将对多个物流区域相互关联的调度问题进行探讨，并分析和改善其相互作用情况.

参考文献

[1]    CHANG Q，PAN C Y，XIAO G X，et al. Integrated modeling of automotive assembly line with material handling [J]. Journal of Manufacturing Science and Engineering，2013，135（1）：011018.

[2]    周炳海，徐佳惠.基于支持向量机的多载量小车实时调度[J].吉林大学学报（工学版），2016，46（6）：2027—2033.

ZHOU B H，XU J H. SVM-based real-time scheduling approach of multi-load carriers [J]. Journal of Jilin University （Engineering and Technology Edition），2016，46（6）：2027—2033. （In Chinese）

[3]    EMDE S，ABEDINNIA H，GLOCK C H. Scheduling electric vehicles making milk-runs for just-in-time delivery [J]. IISE Transactions，2018，50（11）：1013—1025.

[4]    FATHI M，ALVAREZA M J，RODR?GUEZB V，et al. A multiobjective optimization algorithm to solve the part feeding problem in mixed-model assembly lines [J]. Mathematical Problems in Engineering，2014，11（1）：809—812.

[5]    FATHI M，RODR?GUEZ V，ALVAREZ M J. A novel memetic ant colony optimization-based heuristic algorithm for solving the assembly line part feeding problem [J]. International Journal of Advanced Manufacturing Technology，2014，75（1）：629—643.

[6]    FATHI M，RODR?GUEZ V，FONTES D B M M，et al. A modified particle swarm optimisation algorithm to solve the part feeding problem at assembly lines [J]. International Journal of Production Research，2015，54（3）：878—893.

[7]    SHIUE Y R，LEE K C，SU C T. Real-time scheduling for a smart factory using a reinforcement learning approach [J]. Computers & Industrial Engineering，2018，125：604—614.

[8]    SEKER A，EROL S，BOTSALI R. A neuro-fuzzy model for a new hybrid integrated process planning and scheduling system [J]. Expert Systems with Applications，2013，40（13）：5341—5345.

[9]    FAGAN D，FENTON M，LYNCH D，et al. Deep learning through evolution：a hybrid approach to scheduling in a dynamic environment[C]// International Joint Conference on Neural Networks. Anchorage，Alaska：Institute of Electrical and Electronics Engineers，2017：775—782.

[10]  ZANG Z L，WANG W L，SONG Y H，et al. Hybrid deep neural network scheduler for job-shop problem based on convolution two-dimensional transformation [J]. Computational Intelligence and Neuroscience，2019，2019（2）：1—19.

[11]  SONG Y，SHI G，CHEN L Y，et al. Remaining useful life prediction of turbofan engine using hybrid model based on autoencoder and bidirectional long short-term memory [J]. Journal of Shanghai Jiaotong University （Science），2018，23（S1）：85—94.

[12]  ZHUO P C，ZHU Y，WU W X，et al. Real-time fault diagnosis for gas turbine blade based on output-hidden feedback elman neural network [J]. Journal of Shanghai Jiaotong University （Science），2018，23（S1）：95—102.

[13]  WANG L，SHI Y L，LIU S. An improved fruit fly optimization algorithm and its application to joint replenishment problems [J]. Expert Systems with Applications，2015，42（9）：4310—4323.

[14]  SPECHT D F. A general regression neural network [J]. IEEE Transactions on Neural Networks，1991，2（6）：568—576.

[15] CHEN C，XI L F，ZHOU B H，et al. A multiple-criteria real-time scheduling approach for multiple-load carriers subject to LIFO loading constraints [J]. International Journal of Production Research，2011，49（16）：4787—4806.