一种改进的多级型BOM遍历算法

1、研究与探讨工程设计CAD与智能建筑2002(965在工业制造业中,BOM(BillofMaterial , 即物料清单, 是系统中最基本的资料。 它是一种描述装配件结构的零件表,其中包括所有子装配件、 零件、 原材料的清单, 以及制造一个装配件所需要 的所有物料的数量与层次关系。 BOM是制造业信息 系统的一个核心部件, 企业的原材料和产成品都将 通过 BOM建立逻辑上的相关关系。 物料清单是联系 与沟通各业务部门的纽带,它涉及企业内部的销 售、计划、生产、供应、物料、成本、设计、工艺 等部门,它体现了企业内的数据共享和信息集成。 同时,BOM 也为 CAD 和计算机辅助生产管理提供了 一个信

2、息集成的桥梁。 BOM用于描述产品组成的数 量、层次关系。通过 BOM 多级遍历, 可以使企业在 实际生产经营管理中查询某个产品都由哪些原材料 组成 ; 同时, BOM遍历结果也是企业编制生产计划、 进行产品配套、 生产领料和加工过程跟踪的依据 ; 也是企业计算产品成本进行市场报价的参考 ; 通过 BOM 遍历,还可使企业对产品的设计系列化、 标准 化、通用化。因此, 设计一种快速有效的 BOM 遍历 算法就显得尤其重要。本文在总结多级型 BOM 遍历的两种算法 (递归 查找法、 分层查找法 的实现原理基础上, 提出了 一种改进的BOM遍历算法以及用此算法编制的软件 系统及其应用实例。 1BO

3、M 的结构BOM是指构成产品所需零部件的明细表及其结 构。 采用计算机辅助企业进行生产管理, 首先要使 计算机能够读出企业所制造产品的构成和所有要涉及的物料。 为了便于计算机识别,必须把用图示表 达的产品结构(BOM 树转化成某种数据格式(多 级 BOM 表 。BOM 树是由产品、部件、零件等组成的树型结 构。 它按层次展开, 体现了产品的物料结构、 零部 件之间的相互依赖关系及数量关系。多级BOM表是BOM树在计算机中的存储方式, 它 展现了待遍历物料的所有的父子关系和层次关系。 在多级 BOM 表中, 各层次是缩排式显示的, 最高层 次位于左边, 低层次位于右边, 这种排列可直观地 显示出

4、父子项的关系。 由于多级BOM表直观地展现 了物料间的父子关系, 因此更有利于进行物料结构 的取代、料件的删除以及检查物料结构的嵌套错 误。图 1和表 1分别以 BOM 树和多级 BOM 表对产品 A 进行物料表示。 如图 1所示, 制作一个产品A, 需 要B部件一个、 C零件两个、 D部件三个, 依此类推。 2多级型 BOM 遍历的两种算法2.1BOM 遍历的递归算法采用先根遍历的方法, 以树中物料是否有下一 层物料为递归条件,针对图 1所示产品 A 的遍历顺 序为 A (1 、B(1 、 C(1 、 E(2 、C (2 、F (4 、 C(2 、D(3 、G(6 、F(9 。递归算法采用先

5、根 遍历 , 因此较好地展现了物料间的层次关系和 BOM 树的结构;利用堆栈操作, 其优点是程序简单; 但 正因为其堆栈操作, 使得在递归调用过程中, 程序 在执行的每一步都需要将临时节点的信息压入堆 栈,在进行大规模物料遍历时,系统资源消耗大,一种改进的多级型 B O M 遍历算法杜杰陆金桂南京工业大学信息工程学院【摘要】 本文总结了多级型BOM 遍历的两种算法:递归查找法、 分层查找法。 在介绍这两种算法实现原理的 基础上, 提出了一种改进的多级型BOM 遍历算法。 文章最后介绍了采用此算法的软件系统及其应用实例。【关键词】 多级型BOM遍历算法研究与探讨 工程设计CAD与智能建筑2002

6、(966甚至有可能导致系统崩溃。2.2BOM 遍历的分层算法分层遍历算法就是从 BOM 树的根节点出发, 按 层次一层一层的往下遍历, 类似于数据结构中树的 层次遍历过程。针对图 1所示产品 A 的遍历顺序为 A(1 、B(1 、C(2 、D(3 、C(1 、E(2 、G (6 、F(9 、C(2 、F(4 。分层遍历采用临时表 存放 BOM树中某一层物料的信息, 克服了递归算法 中堆栈的使用, 使用较为方便, 能较好的按层次遍 历一个大规模的 BOM树结构 ; 但是由于其按层次搜 索的特点, 其物料的存放顺序未能展现物料间的父 子关系, 而在进行物料结构的取代、 删除以及检查 物料的嵌套错误

7、时,需要知道物料间的父子关系, 因而 BOM 遍历的分层算法将无法进行以上操作。3 改进的 BOM 遍历算法该改进算法的目标为 :既能像分层算法那样处 理一个大规模的 BOM结构, 又能像递归算法那样能 较好地展现物料间的父子关系、 数量关系以及BOM 树的整体结构, 以利于进行物料结构嵌套错误检查 等操作。3.1该 BOM 多级遍历的思想我们仍以图 1所示的产品 A 为例来说明该遍历 算法的思想。 首先构造一个临时表BomTempory, 其 字段信息如表 2所示;然后以倒序的顺序将 A 的下 一层物料的信息添加进临时表的末尾,此处为 D (3 、C(2 、 B(1 ;当临时表的记录数大于零

8、时,取出临时表中的最后一条物料信息 BOMInfo,即 B (1 ;其父物料的代码 ParentNo 为 A,子物料的代 码 SonNo 为 B,对 B(1确定它的层次 Sonlevel、 用量 SonNumber 后,将 B(1保存在结果数据表 BomMultilayer的末尾 ; 接着在临时表中删除B (1 这条信息;由于 B 部件仍有下一级物料信息, 所以 仍以倒序的顺序将B的下一层物料的信息添加进临 时表的末尾, 进而再判断临时表的记录数是否大于 零, 如此循环直到临时表的记录数为零, 到此遍历 结束。3.2该 BOM 多级遍历算法的伪代码funcBomDispose (stringP

9、arentNo /*多级遍历 物料代码为ParentNo的物料*/begin构造临时表BomTempory ;在临时表BomTempory的末尾以倒序的顺序存放BOM树 中需遍历物料的下一层物料信息 ;while (临时表BomTempory 中的记录数0 begin取出临时表的最后一行记录, 该记录对应的物料信息 为 BOMInfo ;确定BOMInfo中子物料SonNo的层次Sonlevel和用量 SonNumber ;将BOMInfo添加进结果表BomMultilayer 的末尾 ;表 1产品 A 的多级 B O M 表表 2 临时表 B o m Tempor y 的字段信息父物料的代码

10、 子物料的代码 子物料的层次 子物料的用量 ParentNoSonNoSonLevelSonNumber研究与探讨 工程设计CAD与智能建筑2002(967删除临时表中的BOMInfo ;若BOMInfo 中SonNo 仍有下一层物料,将SonNo对应的下一层物料的信息以倒序的顺序添加进临时表 BomTempory 的末尾 ;endend实践证明, 采用此遍历算法能较好的展 现BOM树的结构关系。 如果需要针对查找结果 统计物料需求的汇总信息,可以根据遍历结 果表中的物料编码字段进行合并操作。针对 物料结构的取代、删除以及物料嵌套错误的 检查可以基于此算法进行开发。 4应用实例我们编制了一套企

11、业制定生产计划的软件系 统, 采用的开发软件为Powerbuilder7.0, 数据库 软件采用的是 SQLServer2000。其中的 BOM 查询 模块正是采用本文中所介绍的改进算法,在此算法 的基础上 ,我们还编制了物料的替换、 删除以及嵌 套检查等模块。图 2为压缩气体干燥器中干燥塔部件的 BOM 树结构, 所形成的BOM多级遍历的结果如图3所示。 在 输入物料信息时, 系统将按照输入物料的类型 (产 品、部件、零件进行分类管理,在进行 BOM 多级 遍历时, 用户只需选择待遍历的物料, 系统将自动 完成BOM多级遍历, 并将结果显示于图3所示的BOM 多级遍历表中。参考文献2 严志强

12、等 . 多级型 BOM 的遍历 . 机械设计与制造工程, 2001.3图 3干燥塔的多级 B O M 遍历表南京电视台 6类布线验收圆满成功2002年 8月 8日, 南京电视台演播中心大楼结构化布线系统圆满完成了验收, 来自南京电视台、 美国 西蒙公司、该项目的弱电总包方、布线系统集成商及部分其他行业的用户代表出席了验收仪式。南京电视台演播中心大楼高 21层,是一座高标准的专业化电视节目制作演播中心,总建筑面积 34000m 2,楼内设有信息点近 2000点(包括超 5类和 6类,其中大部分是 6类信息点 ,并预置了 125个 光纤至桌面信息点。布线系统选择了著名专业布线厂商美国西蒙公司的超 5类、6类及光纤布线产品。 楼 内水平线缆采用超 5类、6类非屏蔽双