基于树的粮食物流工艺流程选择算法的实现
2021-09-01魏鹏飞张凯锋
◎ 魏鹏飞,张凯锋
(郑州中粮科研设计院有限公司,河南 郑州 450001)
随着粮食物流企业仓容的逐年扩大,粮食物流自动化控制系统的规模日益庞大。当项目分期建设时,由于分期项目工艺流程设计的整体性,需要对多期项目整体考虑,这就极大的增加了控制系统工艺流程选择的复杂程度。
1 流程选择现状
对于小型的粮食物流控制系统(工艺流程条数300条以下),采用流程矩阵算法[1]进行流程的选择,完全可以实现,目前已经有多个项目成功的案例。但是当控制系统受控设备数量的进一步增多时,流程矩阵规模呈指数级增长,人工处理和统计的难度大大增加,既降低了系统开发的效率,同时也增大了后期系统扩容和维护的成本。
对于中型的粮食物流控制系统(工艺流程条数300~1 000条),采用基于二叉树的流程选择算法[2],通过对工艺流程中设备关系的预处理,实现对工艺流程的选择,目前已在工程项目中成功应用。当然,对于小型系统也适用。但是对于更大规模的控制系统,设备关系的预处理过程就变得比较烦琐,不利于缩短系统开发周期。因此,需要寻找应用更加广泛的流程选择算法,用来方便地解决大规模控制系统的工艺流程选择问题。
2 理论基础
本文通过对粮食物流工艺流程中的设备及上下游关系进行抽象,将树中的结点与工艺流程中的设备进行一一对应,基于成熟的计算机树理论和遍历算法,实现了基于树的粮食物流工艺流程选择算法。
3 数据库设计
为方便结点数据和流程信息的存储,本文选择MySQL作为数据库进行存储和记录。
数据库包括2张表[3]:①结点表,用于存储以设备作为结点的树结构,如表1所示。②流程表,用于存储自动生产的流程信息表和相关控制信息,如表2所示。
表1 结点表
表2 流程表
4 算法设计与实现
4.1 算法分析
根据粮食物流进出仓工艺流程图,梳理设备及上下游关系,可以得到类似下图1所示的树结构[4],填入表1所示结点表,这里以包含两个根结点树结构为例。
图1 工艺流程树图
显然,从根结点到任意一个叶子结点所经历的所有结点形成的有向路径即构成了一条工艺流程。
以R1为根结点,得到如下流程:①R1→B→H。②R1→B→E→H。③R1→C→F。④R1→C→G。⑤R1→D。
以R2为根结点,得到如下流程:①R2→H。②R2→E→H。
综上,可以归纳获得图1的所有工艺流程的算法步骤:①获取所有根结点。②以一个根结点为切入点,通过递归算法得到从该结点到所有叶子结点的所有路径。③遍历所有根结点,得到所有路径,即为图1包含的所有工艺流程路线,流程及相关控制信息保存到表2所示流程表。
4.2 算法流程图
这里以图1所示树结构为例进行讨论。R1、R2为根结点,B、C、E为子结点,D、F、G、H为叶子结点,算法实现如下。
(1)获取树结构的根结点列表。
(2)遍历所有根结点。选取第一个根结点,这里取R1。从R1结点出发,通过递归依次找寻该结点的子结点,孙子结点等,直到找到叶子结点,进而获取从R1开始的所有路径。
(3)以R2为根结点,获取从R2开始的所有路径。
(4)R1、R2开始的所有路径即为图1所示树结构的表示的所有流程。
限于篇幅,算法的主要流程如图2所示。
图2 算法流程图
4.3 算法实现
本文使用java语言,通过循环和递归算法得到了树结构从根结点到叶子结点的所有有向路径,即列举了所有工艺流程。核心的算法程序如下[5]。
4.3.1 结点实体类实现
5 小结与实践
5.1 理论小结
通过将工艺流程中的设备及设备之间的关系抽象为如图1类似的树结构,实际当中更为复杂,可以使用树理论的算法自动罗列出存在的工艺流程路径。
对于生成的工艺流程路径,结合生产中的实际应用,一部分工艺路径在实际中并没有实际的意义。因此,需要对自动罗列出的流程路径按照关键设备组合自动进行剔除,以得到对于实际应用更为有意义流程线路。
对于大规模的工艺流程选择,该算法既避免了基于流程矩阵算法的矩阵规模的指数级增长,同时也不像二叉树算法那样,需要对工艺流程的设备关系进行烦繁琐的预处理。
与二叉树工艺流程选择算法不同的是,基于树理论的选择算法,使用的范围更为广泛,对于中小规模的粮食物流控制系统同样适用。但是,由于根结点的不唯一性和树结构子结点的数量不确定性,导致在流程选择过程中,不仅需要选择根结点和叶子结点,还需要增加部分子结点,才能确定唯一的流程路径。此外,增加结点的不同权重,既有利于流程路线的选择,同时也有利于企业生产过程中的节能和提质增效。
5.2 工程实践
基于树理论的粮食物流选择算法已经在多个新建或续建的粮食物流自动化控制项目当中成功应用。通过流程首尾设备和关键设备的选择,即可唯一确定相对应的流程。
特别的,对于之前已经使用该算法的项目,其续建项目的流程扩容将更加方便,只需通过适当地更改原来结点表,即可自动生成新的流程控制信息。基于多个粮食物流项目应用的成功经验,目前流程选择算法正在进一步使用、完善和推广当中。