基于LLC进行BOM展开的改进算法

1、制造业信息化机电产品开发与创新Development &Innovation of M achinery &E lectrical P roductsVol.23,No.2Mar .,2010第23卷第2期2010年3月收稿日期:2009-12-29基金项目:湖南省自然科学基金资助项目(07JJ6141作者简介:方霞(1972-,女,湖南常德人,讲师,硕士研究生。主要从事计算机应用,智能控制与优化研究;潘梅森(1972-,男,副教授,博士生。主要研究方向:人工神经网络。0引言BOM 的数据结构及展开计算是ERP 系统数据模型的核心。BOM 展开及计算复杂的主要原因是存在着同一种物料同时出现在产

2、品不同层次,称为多层次通用件。多层次通用件可能出现在同一产品的不同层次上,也可能出现在不同产品的不同层次上,在计算净需求时需要重新计算和处理不同层次上的总需求量,容易出现重复或遗漏计算问题,极大影响ERP 工作效率。传统的BOM 遍历算法有递归算法、分层查找法等。根据不同存储结构有一系列的BOM 改进遍历算法,如采用综合单层BOM 结构和多层BOM 结构方法的复合式BOM 构造方法,并采用存储过程来实现BOM 的遍历1;针对BOM 结构中出现的多对多关系利用邻接表建立联系,构造相关表单结构,对于一般网状数据关系BOM 通用2;引入低层码LLC (Low Level Code 能有效解决BOM

3、展开灵活性问题3,4。本文在此方法基础上提出一种新的基于LLC 的BOM 展开算法,主要针对比较复杂的产品结构,解决多层次通用件的计算问题。1物料清单BOM 表构造产品结构树直观的表达了成品、标准件、零部件、原材料等物料之间的从属关系和数量构成关系,把设计图表达的产品结构转化成某种数据格式,这种以数据格式来描述产品结构的文件就是物料清单,也即BOM 是定义产品结构的技术文件,又称为产品结构树、产品结构表或BOM 表。如图1所示是一棵4级A 产品结构树。综合BOM 多层结构和层次码结构的优缺点,对于产品A 创建复合BOM 数据表,内容见表1。复合式BOM 结构与多层结构相似,添加了层次字段,该字

4、段初始为空,利用BOM 结构生成其层次码,然后获得低层码LLC 。所谓低层码是指某个物料在所有产品结构树中所处的最低层次码,每个物料有且仅有一An Improved BOM Expanded Algorithm Based on the Lower Level CodeFANG Xia 1,PAN Mei-Sen 2(1.Department of Computer Science and Technology,Hunan University of Arts and Science,Changde Hunan 415000,China ;2.School of Traffic &Transp

5、ortation,Beijing Jiaotong University,Beijing 100044,ChinaAbstract :This paper described the structure and normally used expanded algorithms of BOM.For the difficulty in calculating the multi-level generic pieces,this paper proposed an improved BOM expanded algorithm based on LLC.After checking the l

6、egitimacy of BOM,this algorithm designed a temped queue table to finish the information in the main table of BOM such as llc etc.It can effectively realize the BOM level traversal and the computation.Freeed from the recursive method,the algorithm has more advantages along with the increasing complex

7、ity of the product structure.Key words:ERP(Enterprise Resource Planning;BOM(Bill Of Material;LLC(Lower Level Code;Queue基于LLC 进行BOM 展开的改进算法方霞1,潘梅森2(1.湖南文理学院计算机学院,湖南常德415000;2.北京交通大学,北京100044摘要:简述了BOM 的产品结构形式,以及常用的BOM 展开算法。针对BOM 结构中多层次通用件计算的复杂性,提出一种基于低层码(LLC 结构的BOM 展开改进算法。算法在合法性检查基础上设计了辅助队列表,将BOM 主表层次

8、码等信息填充完整,有效实现BOM 层次遍历展开及计算。算法不受递归的限制,随着产品结构复杂程度增加,该算法更具有优越性。关键词:企业资源计划;物料清单;低层码;队列中图分类号:TP391文献标识码:A文章编号:1002-6673(201002-100-03100制造业信息化表1产品A 的复合式BOM 表结构Tab.1Compound BOM structure of product A记录号父项代码子项代码用量层次号低层码叶子其他1A B 211F 2A C 113T 3A D 311F 4B E 223T 5B F 422F 6D G 223T 7D H 322F 8F C 133T 9F

9、G 333T 10H E 233T 11H C 133T个低层码。如图1中物料C 分别处于产品结构树的第1层和第3层,于是C 的低层码为3。产品A 对应表1中F (T 表示叶子结点,为BOM 展开算法所用。通过LLC可以控制ERP 计划的编制顺序,使得各物料的ERP 运算不重不漏,提高系统的效率。2BOM 遍历算法ERP 系统包含一些BOM 的基本操作,如展开查询、多级查询、以及工艺文件的制定,还有物料需求计划的反查、BOM 物料数量的计算等,都需要在BOM 结构表中检索数据。为了确保相关计算的顺利和有效进行,首先要进行BOM 的合法性检查,然后计算生成相关数据,因此对BOM 树进行遍历采用一

10、种好的算法相当重要。常用的BOM 展开算法有深度优先的递归算法,或层次遍历算法5。2.1BOM 合法性检查ERP 系统由管理人员将图纸信息录入,然后读取CAD 电子图纸中设计BOM 所需要的零部件信息,并将之存储到相应的数据结构中。利用树根结点不能在后续子孙结点中出现的基本特性,采用自顶向下逐层分解的方式进行检查。合法性检查算法1(略。外循环算法标志tag 用来判断当前轮次树根结点有无变化,如果没有改变则表示当前存在环,如果改变则表示有新的子树产生,需要进行下一轮次的循环。各个表的具体结构内容以及算法功能分析已经在文献6中进行了详细探讨。2.2改进的基于LLC 的BOM 遍历算法文献4针对递归

11、遍历进行改进,通过设计一个堆栈表来实现非递归的深度遍历,算法本质是深度优先。在这里,基于广度优先的思想,对常用层次遍历进行改进。算法采用上述改进的BOM 结构主表,初始状态令层次号、低层码域都为空,设计一个临时表TempQ (队列用来计算相应层次码以及低层码LLC ,通过如下改进算法得到各种物料的层次号,可以有效解决后续计算中多层次通用件的重复和遗漏问题。展开算法2描述如下:/基于LLC 的展开改进算法2创建临时数据TempQ (father,son,level;表1中层次号、低层码字段均置0;将待查物料展开第一层物料信息依次放入临时表TempQ 中;/与表1中父项代码、子项代码对应置临时表T

12、empQ 中该层物料的level 均为1;While 表TempQ 中数据不空删除表TempQ 中当前物料记录;/出队把当前结点的所有子结点依次放入表TempQ,子结点lev -el 均增值1;如果没有子结点则置表1中的叶子标志为T;更新表1对应物料层次号=level;/反填在表1中查看子结点相同信息的非0层次号结点,更新其低层码为level;结合图1的产品A ,该算法的低层码计算结果如表1所示。算法运行过程中依次出队序列为BCDE -FGHCGEC ,是典型的层次遍历BOM 展开结果。在此基础上结合用量字段的计算,然后分类汇总即可得出每一种物料的详细数量。3算法性能分析在ERP 功能模块的开

13、发中,结合BOM 的展开计算功能对上述算法进行了应用。3.1时间复杂度分析时间复杂度方面,运行速度也提高了许多。为了便于分析,类似于二叉树,假设产品结构树为满r 叉树,定义k 为树的深度,则对于递归的BOM 展开算法,可以得到算法分析递推式:T(1=1,T(k=rT(k-1+1扩展并计算此递推式得到T(k=(rk-1/(r-1:得到的时间复杂度为T(k=O(rk,随着树的深度k 呈指数增长趋势;实际应用中r 在各自的物料分解上数量不相等,产品结构树也并不是理想中的满r 叉树。选取合适的物料分支数量r 以及控制整棵产品树的深度k 需要慎重考虑。另外,内存堆栈的开辟需要操作系统分配时间,只是该项工

14、作对用户透明而已。而堆栈的大小与树图1A 的产品结构树Fig.1Structure tree of product A101制造业信息化(4指定默认VLAN(可选,即当Trunk失效后,允许哪一个VLAN使用Trunk链路继续通信。即可指定某一个VLAN,也可指定一个VLAN范围。访问VLAN 不能作为本地VLAN使用。Switch(config-if#switchport access vlan vlan_id(5为802.1Q Trunk指定本地VLAN。若不指定本地VLAN,默认将使用VLAN1。Switch(config-if#switchport trunk native vlan

15、vlan_id(6配置Trunk上允许的VLAN列表。默认状态下,Trunk端口允许所有VLAN的发送和接收传输。当然,根据需要,也可以拒接某些VLAN通过Trunk传输,从而限制该VLAN与其它交换机的通信,或者拒绝某些VLAN对敏感数据的访问。Switch(config-if#switchport trunk allowed vlan add|all|except|removevlan-list(7返回至特权配置模式。Switch(config-if#end(8查看并校验配置。Switch#show interface interface_id switchportSwitch#show

16、interfaces interface_id trunk(9保存VLAN配置。Switch#copy running-config startup-config若欲允许所有VLAN都通过该Trunk,可以使用no switchport trunk allowed vlan接口配置命令。3结束语在设计VLAN时,考虑网络安全性能和传输速度的同时VLAN间的通信问题也是十分重要的一个环节,由于网络产品的开发和应用速度相当快,目前VLAN间的通信还没有统一的标准,各厂家生产的网络设备在实现VLAN间通信的技术上各有所长,因此在具体的网络规划中应根据网络设备的特点和具体的网络应用情况来决定采用那种方

17、式。参考文献:1刘晓辉,李利军.交换机路由器防火墙M.电子工业出版社,2008.2雷震甲.网络工程师教程M.清华大学出版社,2006.的深度k密切相关。改进的遍历算法只需要一次循环就可以完成,所以时间复杂度T(n=O(n。有效解决了递归的问题。3.2空间复杂度分析改进算法和常用算法相比,其空间复杂度很明显。常用递归算法需要内存堆栈,空间辅助一般为O(logrn,当BOM的复杂度增加,特别是物料数量n增大时,会造成系统崩溃;常用非递归算法需要使用临时数据表,一般为O(n。改进算法的辅助空间里采用了数据库的创建索引思想,充分利用主表信息,减少信息冗余,临时表空间最大是O(3n/m,m表示BOM数据

18、主表的字段数。3.3实例数据运行环境操作系统是WinXP,数据库采用SQLServer2000。通过视图的使用,单个产品实验数据一般不超过3万条记录,层次在15层以内。结合相关试验数据比较见表2。在不同的计算机上由于性能配置的差异可能导致结果少许不同,但在同一台机器上的运行可以看到改进算法在实际的应用中取得了明显的效果,极大的提高了系统的效率,减少了数据库系统资源的占用,提高了数据库的性能和响应能力。4结论(1通过总结BOM核心计算相关算法的实现,提出新的一种基于低层码的改进算法。充分利用队列的基本操作特性及相关字段设置标志,简化了算法的复杂度。(2实例研究及计算表明,该方法在运行速度和空间复杂度方面均取得了明显的效果,极大的提高了系统的效率,具有通用性和实用性。参考文献:1张媛,等.ERP的BOM结构设计及算法研究J.机床与液压,2008,1.2张军,等.一种多对多BOM结构的实现J.计算机应用,1999,6.3程控,等.MRPII/ERP原理与应用M.北京:清华大学出版社,2006.4余锐林,吴顺祥.一种改进的BOM展开及低层码生成算法J.计算机工程与应用,2005,27.5Gany