基于Dijkstra算法的航空兵器自动生产线动态调度算法的研究

刘震宇 汪越雷 周庞睿

摘要：      在航空兵器自动化生产线上， 智能车运行轨迹的选择对于提高生产线效率十分重要。 本文结合优化算法数学模型的分析， 建立基于Dijkstra算法的自动寻路模型， 利用MATLAB对最优结果进行求解。 最后， 就自动化物料加工过程中的复杂情形进行探讨。

关键词：     自动化生产线; 动态调度; 优化算法; Dijkstra算法; MATLAB

中图分类号：     TJ08 文献标识码：    A文章编号：     1673-5048（2019）03-0094-05[SQ0]

0引言

工业4.0时代的航空兵器自动化生产线上， 很大一部分都采用了数字化无人车间， 车间中所用最多的就是智能车。 智能车运行轨迹的选择对于提高生产线效率十分重要。 自动化生产线的智能车调度优化算法常结合计算机神经网络进行分析。 图1～2为智能车与自动化生产线系统示意图。

目前， 国内外许多研究人员已经从模拟退火算法[1]、 蚁群算法[2]、 启发式算法等神经网络典型算法研究移动机器人路径规划问题， 运用MATLAB建立移动机器人仿真系统， 输入相应参数， 运行程序， 即可得到合理的机器人移动方案。 而自动化生产线上的智能车具有自身固有的特点： 移动路径相对固定， 路径方案与机床上下料时间和移动时间关系密切， 对于突发情况（如机床故障）具有临时改变路径的能力等， 因此需要有更加合理有效的神经网络算法对此类问题进行优化。

1自动化加工生产线的数学模型

1.1问题理想化模型

机床加工生料时， 需要经历上料、 下料、 移动、 清洗等操作。 由于智能车匀速运动， 因此在机床间的移动时间与移动距离具有正比关系。 实际情况中， 上下料传送带既可以联动， 也能独立运动， 所以无需考虑送料拥堵问题; 由于程序设定一般已经充分考虑了操作之间转换的间隙， 因此也无需考虑时间间隔; 在开启加工线之前， 认为各机床均处于闲置状态， 智能车位于第一列机床两侧。

1.2生产线加工情况的讨论

常见的自动化加工生产线中， 存在单工序生产线和多工序生产线两种典型情况。 单工序生产线即为所有机床的加工工序一致， 智能车可以将生料移动到任何一台机床上进行加工; 多工序生产线即为机床加工存在先后关系， 智能车需将生料依次放在多台机床上进行加工才能完成任务。

根据以往研究工作得知[3]， 考虑到一台智能车管理机床范围有限， 至多只安排两道工序同时进行加工， 因此将问题简化为考察两道工序下智能车的移动路径优化问题。

1.3生产线发生故障的讨论

实际加工过程中， 常存在机器突发故障等问题， 需要临时对智能车的行进路线进行调整， 以最大化提高生产效率。 为简化问题， 考虑故障发生的概率服从二项分布， 在人工设置的故障点后用优化算法进行拟合与调整， 得到相对最优解。

2基于Dijkstra算法的智能车路径优化

2.1算法思路

Dijkstra算法由荷兰计算机科学家狄克斯特拉于1959 年提出。 该算法是从一个顶点到其余各顶点的最短路径算法， 解决的是有向图中最短路径问题。 该算法的主要特点是以起始点为中心向外层层扩展， 直到扩展到终点为止。 具体思路可以用图3所示的流程图表示。

2.2生产线上Dijkstra算法的应用

2.2.1单工序模型： 生产流程的抽象与简化

单工序的智能车运行简图如图4所示。 显然， 智能车的调度有两个子过程： 以“起始状态+上料去程+空回程”为流程的初始上料过程; 以“下料去程+上料去程+空回程”为周期的上下料过程。

分别对两个子过程建立初等数学模型[4]， 设过程1“起始状态+上料去程+空回程”智能車总耗时Tp1; 设过程2“下料去程+上料去程+空回程”一个周期智能车总耗时Tp2; 设过程1+过程2为一个周期， 智能车总耗时Tp3;

显然， 单工序加工的情况下， 智能车的运行轨迹具有周期性， 对于路径优化的限制条件相对较少。 单工序下不同加工系数T0/T1的值也会显著改变生产线的加工效率， 具体表现如表2所示。

加工系数T0/T1代表平均上下料时间与平均移动时间之比， 运行效率代表机床的闲置率。 综上， 需考虑将两者的比值设置在合理区间内， 可以使得单工序生产线的加工效率最高。

2.2.2多工序模型： 综合评价参量K的确定与机床分配

对于多工序的流水线， 需要考虑机床数量和位置的分配问题。 建立数学模型， 通过比例因子K决定各工序使用机床的数量之比。 定义K=n1/n2， 即第一道工序与第二道工序使用机床数的比值。 从实际情况出发， 将连续的K离散化处理为5/3， 1， 3/5。

下面通过一个简单的模型分析， 来确定最佳的第一、 第二道工序的分配方案。 为简化问题， 可由T1和T2时间关系确定的机床数目分配， 以及这样分配导致RGV在轨道上移动花费的实际时间mT。 定义两个权重函数σ1和σ2， 且有σ1+σ2=1， σ1>0， σ2>0， 计算结果用综合参数K表示：

对于m， 当n1=n2时有最小值， 而此时实际情况应该为T1和T2相差较大， 因此对这种情况的机器数目的分配比应当尽量靠近n1=n2， 即尽可能取距离最优情况最近的分配比; 而当两个工序在时间上相差较小时， 即T1和T2的比值较接近于1的时候， 考虑后者就少一些， 这个时候就可以近似而且合理地认为n1=n2为最优解的存在前提。

（1） 当K=1

在K=1的情形下， 工序一和工序二均分配4台机床。 根据排队论理论， 为使系统空闲概率与逗留时间最短， 应使上端2， 4， 6， 8全部是同一种工序， 下端1， 3， 5， 7也全部是同一种工序。 这样不难分析知， 流水线的工作效率与两工序的加工时间有关。 设T2a， T2b分别为CNC加工完成第一道工序、 第二道工序所需时间， 一种方式是使偶数编号的机床加工工序一， 奇数编号的机床加工工序二， 其用时

T=2Te+5To+4Tc+3Tm1+T2a+T2b; 另一种方式是对调加工机床的工序， 其用时T=2To+5Te+4Tc+3Tm1+T2a+T2b， 因此得出结论： 先给处理时间长的机床下料。

（2） 当K=5/3或3/5

由于小车从1， 2之间出发， 且经常往返于各节点之间， 因此在考虑依次排开的情况下， 优先在2机床安排工序二的工件， 同时为了保证不同工序的机床交互的便利性， 考虑如图6所示的排布方案。图中矩形为工序一， 圆角矩形为工序二。

2.2.3多工序模型： 基于Dijkstra算法的多工序加工效率

完成了机床数量和位置的分配后， 便可以基于Dijkstra算法进行加工方案的设计了， 与单工序情况类似， 多工序需要考虑两次加工过程和智能车转移物料的时间。 当K=5/3时分别代入具体数据（T1=T2=15， Tm1=10）， 用MATLAB绘制多工序的智能车运行时空关系如图7所示。

在多工序加工的情况下， 智能车的运行轨迹与加工时间以及智能车移动时间等参数有关， 对于路径优化的参数要求较高。 多工序下不同加工系数T2/T1的值也会显著改变生产线的单位时间产出， 具体表现如表3所示。

T2/T1表示工序二和工序一的加工时间之比。 综上， 需考虑将两者的比值设置在合理区间内， 可以使得单工序生产线的单位时间产出最高。

2.2.4故障模型： 二项分布下的故障应对方案

在实际加工过程中， 经常由于机床故障需要临时调整智能车的工作路线， 对于常见的故障模型， 考虑其发生的频率为二项分布， 当故障发生频率P～B（8， 0.01）时， 发生故障的概率可以近似如表4所示。

3结论

在工业4.0的背景之下， 除了航空兵器生产的质量以外， 生产的效率也尤为关键， 本文以航空兵器的生产为背景， 讨论了如何提高生产效率， 从航空兵器生产流水线的智能车调度问题入手， 着眼于方案优化， 从单工序、 多工序和故障排查对简单流水线的加工方案的确定给出了数学模型， 并基于Dijkstra算法进行计算机求解， 结果切实可行。

参考文献：

[1] 裴以建， 杨亮亮， 杨超杰. 基于一种混合遗传算法的移动机器人路径规划[J/OL]. 现代电子技术， 2019（2）： 183-186.（2019-01-22）[2019-03-04].https：∥doi.org/10.16652/j.issn.1004-373x.2019.02.042.

Pei Yijian， Yang Liangliang， Yang Chaojie. Path Planning of Mobile Robot Based on a Hybrid Genetic Algorithm [J/OL].  Modern Electronic Technology， 2019 （2）： 183-186. （2019-01-22）[2019-03-04].https：∥doi.org/10.16652/j.issn.1004-373x. 2019. 02.042.（in Chinese）

[2] 林伟民， 邓三鹏， 祁宇明， 等. 基于蚁群算法的移动机器人路径规划研究[J]. 机械研究与应用， 2018， 31（4）： 144-145.

Lin Weimin， Deng Sanpeng， Qi Yuming， et al. Research on Path Planning of Mobile Robot Based on Ant Colony Algorithm[J].Machinery Research and Application， 2018， 31（4）： 144-145.（in Chinese）

[3] 于龍振.  基于LinKernighan改进型算法的可视化TSP处理软件的实现[D].青岛： 青岛大学， 2006.

Yu Longzhen. Implementation of Visualized TSP Processing Software Based on LinKernighan Improved Algorithm [D]. Qingdao： Qingdao University， 2006.（in Chinese）

[4] 邢海涛. 基于时间Petri网的小组软件过程仿真建模研究[D].哈尔滨： 哈尔滨工程大学， 2005.

Xing Haitao. Research on Group Software Process Simulation Modeling Based on Time Petri Net[D]. Harbin： Harbin Engineering University， 2005.（in Chinese）

[5] 陈江红， 李宏光. 基于Matlab环境的Petri网的仿真方法[J]. 微计算机信息， 2003（12）： 103-104.

Chen Jianghong， Li Hongguang. Simulation Method of Petri Net Based on Matlab Environment[J]. Microcomputer Information， 2003（12）： 103-104.（in Chinese）