基于识别关键件的子装配体识别方法

董士龙,古天龙,徐周波

(桂林电子科技大学计算机科学与工程学院,广西桂林 541004)

基于识别关键件的子装配体识别方法

董士龙,古天龙,徐周波

(桂林电子科技大学计算机科学与工程学院,广西桂林 541004)

为避免在复杂产品装配序列规划过程中出现过度的组合爆炸,同时基于产品无向连接图和子装配体约束要求,提出一种新的子装配体识别方法。通过产品零件的无向连接图,找出复杂产品中的“连接关键件”和“识别关键件”,用于区分不同的零件连接集合;通过子装配体的稳定性检验及矫正、独立无冲突性检验及矫正,找出复杂产品中的有效子装配体;采用深度搜索策略生成每个子装配体的装配序列,得到复杂产品的装配树结构。通过某齿轮油泵模型的实例演示,证明了子装配体识别方法的有效性。

装配序列规划;识别关键件;子装配体识别

随着市场竞争的日益激烈和全球一体化时代的到来,国内外制造业的生存和发展都面临着严峻的挑战。据统计,现代产品制造过程中,装配费用占整个产品总制造费用的30%～50%,装配时间也占据整个产品总制造时间的40%左右[1]。因此,产品装配序列规划(assembly sequence planning,简称ASP)的研究已成为一个重要的课题。

对于零件数量众多的大型复杂产品,如果单纯采用优先约束法、割集拆卸法等典型的装配序列规划方法,不可避免面临“组合爆炸”问题。解决这个难点的有效途径之一,就是采用子装配技术将复杂产品的装配结构层次化,从而缩减每个层次中被处理的零件数量,提高装配规划效率。

由于子装配技术可有效组织和管理复杂产品的装配序列规划过程、提高装配效率,许多学者对子装配体的识别方法进行了研究。Dini首次提出子装配概念,并给出了子装配体提取方法,但该方法需要参与运算的矩阵数量较多;张勐等[2]根据零件连接类型,建立装配体的带权无向连接图模型,通过模型边权值的设定识别子装配体,但该方法权值的分配存在一定的困难;龚京忠等[3]采用局部约束有向图表达装配体中的连接与装配关系,通过建立装配邻接和阻碍矩阵,采用紧连接分析和有向图分析识别子装配体,但该方法过于复杂,不利于复杂产品的装配序列规划;曹德君等[4]从装配有向图中识别基础件,通过模糊数学理论建立几何和工艺优先约束因素相对于装配难度的隶属函数,以综合函数值作为权值得到赋权配合关联图,并通过设置难度系数和以基础件为核心对零件节点进行合并与组合得到简化配合关联图,在此基础上通过一定规则和基础件识别子装配体,但该方法中规则的获取和确定十分困难;王孝义等[5]在分析子装配层次划分与产品结构树形成关系的基础上,提出了一种基于结构树重构的产品多级子装配体识别方法,但产品结构树的存储空间过大;赵姗姗等[6]通过分析功能子装配体间的干涉关系和稳定性,提出了一种工艺子装配体识别算法,但该方法中合理的工艺子装配体定义是个难点;王永等[7-8]总结了不同的子装配体识别方法,指出子装配体应满足的三大约束条件:拓扑约束条件、几何约束条件和工艺约束条件。

鉴于此,利用产品零件无向连接图找出“连接关键件”和“识别关键件”,基于子装配体的稳定性检验及矫正、独立无干涉性检验及矫正,提出一种新的子装配体识别方法。该方法可将复杂产品分割为多个子装配体,而且各个子装配体之间相互独立,根据具体需要,在子装配体中找出下一级子装配体和上一级子装配体,从而得到产品的结构分层树装配模型,并采用深度搜索策略生成每个子装配体的装配序列,得到复杂产品的装配树结构。

1 装配连接图

一个产品通常由许多零部件以一定的装配连接而成,产品零件的连接关系可用一个无向连接图G=〈V(G),E(G)〉描述,如图1所示。其中:节点集V(G) ={v1,v2,…,vn}(n为产品零件数量)为非空有限集,顶点元素vi表示装配体的零件pi;边集E(G)={e1, e2,…,em}(m为产品连接数量)也为非空有限集,无向图的边元素ei表示该边两端顶点(零件)的连接关系。

图1 无向连接图Fig.1 The undirected connected graph

产品零件间通常存在紧固连接、一般接触连接和无连接3种连接关系。设产品P由n个零件组成,即P={p1,p2,…,pn},则紧固连接关系和一般接触连接关系的定义如下。

定义1 若零件pi和pj在某装配方向k∈(x, y,z,-x,-y,-z)上装配后形成不可自分离的整体,即必须借助一定外力才能使2个零件分开,则称零件pi与零件pj存在紧固连接关系(如螺纹、焊接等)。在无向连接图中,紧固连接关系用实线表示。

定义2 若零件pi和pj在所有装配方向{x,y, z,-x,-y,-z}上均为一般物理接触连接或无连接(但至少存在一个方向的一般物理接触),即2个零件的装配是不稳定的、易自分离的组合,则称零件pi与零件pj存在一般接触连接关系(如依靠、贴合等)。在无向连接图中,一般接触连接关系用虚线表示。

无连接关系的2个零件在无向连接图中对应顶点之间没有边线连接。

由于复杂产品的零件数量较多,零件间连接接触关系比较复杂。为了合理地划分子装配体,提出“连接关键件”和“识别关键件”概念。

定义3 若产品中某零件p的紧固连接数量NK≥max[3,(N-3)/lg(N+1)](N为产品的零件数量),则定义该零件p为连接关键件。

定义4 若产品中某零件p不是非关键件,且同时与大于等于2个连接关键件存在连接关系,则定义该零件p为识别关键件。

2 子装配技术

2.1 子装配体概念

当一个装配体是另一个装配体的零部件时,称其为子装配体。一个子装配体应满足如下约束要求:

1)稳定性要求:组成子装配体的零件之间的连接应稳定,即在子装配体移动过程中不会发生自分离。

2)独立无干涉性要求:同一级子装配体之间相互独立且不干涉装配;子装配体内部的零件或子装配体与不属于该子装配体的零件相互独立且不干涉装配。

此外,在产品装配过程中的零件依据相互的连接关系,按照特定的定位方式进行安装,因此,需要在装配过程中选择某个零件作为装配基础件。装配基础件在装配过程中固定不动,其他零件都以它为基础进行装配。在整个装配过程中基础件是起始装配零件,其他零件都依附于它,因此,基础件往往处于装配体的中心位置。每个子装配体内部都有且只有一个基础件。基础件一般为体积和质量较大、与其他零件的连接数量较多的零件,如箱体、基座等。

2.2 子装配体识别算法

在复杂产品装配规划中,通常将产品递归分解成各级子装配体,以便有效组织和管理产品装配。即在装配规划过程中,将一个复杂的产品划分为若干个子装配体;根据具体需要,子装配体又可划分为下一级子装配体和上一级子装配体,直到满足需求为止;在上层将子装配体作为独立的零件进行处理,在下层单独处理子装配体内的零件。这样,可有效缩减每个层次被处理的零件数量,减小装配规模,提高装配规划效率。子装配体划分合理与否,直接决定后续装配效率和装配质量。

利用产品零件无向连接图找出“连接关键件”和“识别关键件”,然后基于子装配体的稳定性和独立无干涉性提出新的子装配体识别方法。算法流程图如图2所示。算法步骤如下:

1)找出复杂产品的所有连接关键件,并记录到集合{C1,C2,…,Co},其中,o为连接关键件的总数量。这些连接关键件由于连接数量较多,除了用于找出识别关键件外,还可作为每个子装配体中的装配基准件。

2)基于连接关键件集合{C1,C2,…,Cm}找出产品中的识别关键件,并记录到集合{K1,K2,…,Km},其中,m为识别关键件的总数量。

图2 子装配体识别算法流程图Fig.2 The flow chart of subassembly identify

3)因为识别关键件Ki同时与多个连接关键件存在连接关系,所以识别关键件Ki的连接类型较复杂,也较易引发装配冲突。因此,暂时忽略这些识别关键件Ki的所有连接关系,复杂产品将散裂为若干零件连接子集或一些孤立零件,而且这些连接子集中的零件与其他零件存在装配干涉冲突的可能性很小。在这个过程中标记每个连接子集为S1,S2,…,Sh,其中,h为连接子集的数量。

4)检验零件连接子集Si的装配稳定性。若连接子集Si中某零件pi的连接类型均为一般接触连接,且与连接子集Si外的某零件pj存在连接关系,则该子集Si不符合子装配体稳定性要求,执行步骤5),进行稳定性矫正处理;否则,若连接子集Si中所有零件均满足装配稳定性要求,则该子集Si满足子装配体稳定性要求,执行步骤6),进行连接子集Si的独立无干涉性检验。

5)子集稳定性矫正。将与连接子集Si中某零件pi存在不稳定连接关系的零件pj并入该连接子集Si,然后执行步骤4),继续进行连接子集Si的稳定性检验。

6)检验零件连接子集的独立无干涉性。若子集Si装配完毕,连接子集Si外的某零件pj将无法装配,则该子集Si与零件pj存在装配冲突关系,执行步骤7),进行独立无干涉性处理;否则,若不存在其他零件pj与子集Si中的零件存在装配冲突关系,执行步骤8),进行连接子集合并处理。

7)子集独立无干涉性矫正。将与子集Si存在装配冲突的零件pj并入该连接子集Si,然后执行步骤4),进行连接子集稳定性检验。

8)连接子集都已经过稳定性检验矫正处理和独立无干涉性检验矫正处理,若2个连接子集Si和Sj存在相同的零件pi,则这2个连接子集应合并为一个较大的连接子集。所有连接子集Si都经过合并检验处理后,将每个连接子集Si视为一个子装配体Ai。

9)将子装配体视作特殊的零件,与孤立零件一起,利用子装配体识别方法递归寻找更高层次子装配体;或将子装配体视作一个新装配体,利用子装配体识别方法寻找低层次子装配体。最后,将每个子装配体视为特殊的零件,与孤立零件一起构成复杂产品的根装配体。

2.3 子装配体规划算法

子装配体识别可将复杂产品分解为一组子装配体,每个子装配体都是相互独立的装配体,而且零件数量相对较少。因此,复杂产品的装配序列可由各子装配体的装配序列合并得到。基于深度搜索策略,提出一种有效的子装配体的装配序列规划算法。算法流程图如图3所示。算法步骤如下:

图3 子装配体规划算法流程图Fig.3 The flow chart of subassembly planning algorithm

1)找出基准件B的紧固连接集合SB={b1,b2,…,bu},u为与基准件存在紧固连接关系的零件数量,并选择一个零件作为下一个待装配零件pw=bi。

2)找出与待装配零件pw存在连接关系,且未包含在Q中的零件集合W={w1,w2,…,wl},l为与该零件连接的零件数量。若待装配零件pw与Q中零件装配后,与集合W中所有零件均不存在装配冲突关系,则将零件pw加入到已装配序列Q中,并标记为前序装配零件,pf=pw,执行步骤3);否则,零件pw将干涉其他零件的装配,即零件pw不能作为待装配零件,执行步骤4)。

3)在集合W中选择一个零件作为下一个待装配零件pw=wj,并执行步骤2)。

4)若前序装配零件pf不等于基准件B,执行步骤5);否则,即pf=B,执行步骤6)。

5)将前序装配零件pf的连接集合Sf中的其他未装配零件fk作为新的下一个待装配零件pw=fk,并执行步骤2);若集合W中已无零件,则执行步骤7)。

6)将基准件的紧固连接集合SB中的其他未装配零件作为新的下一个待装配零件pw=bt,并执行步骤2);若集合SB中已无零件,则执行步骤8)。

7)将已装配序列Q中零件pf的前一个零件作为新的前序装配零件pf,并执行步骤4)。

8)所有零件都已遍历,算法结束,即子装配体装配序列规划结束,并输出子装配体的装配序列规划结果。

最后,将复杂产品的装配序列表示为树形结构,即并行装配树结构。其中:树的根节点表示复杂产品,树的分支节点表示子装配体或零件;父节点与子节点之间的无箭头连线表示子装配体及其组成零件之间的关系;兄弟节点之间的有箭头连线表示同一子装配体内零件的装配优先关系(箭尾的零件优先于箭头的零件装配),即表示子装配体的零件装配顺序。

3 实例分析

使用Visual C++2010集成开发工具开发了“基于识别关键件的子装配体识别系统”软件平台。同时,为了进一步证明子装配体识别算法的有效性,利用开发的软件平台对图4所示的某齿轮油泵模型进行了子装配体识别规划。图4中,零件1～16分别为泵体、从动轴齿轮、填料、填料压盖、锁紧螺母、主动轴齿轮、垫片、圆柱销、泵盖、垫圈、螺栓、钢珠、钢珠定位圈、弹簧、小垫片和螺栓。

由图4所示齿轮油泵零件的连接类型,可得到齿轮油泵模型的无向连接图如图5所示。

图5 齿轮油泵零件的无向连接图Fig.5 The undirected connected graph of oil pump parts

基于图5无向连接图,可得到齿轮油泵模型的连接关键件集合为{p1,p9},识别关键件集合为{p2, p6,p7,p8,p11}。基于识别关键件,得到零件连接集合子集S1={p4,p5,p6},S2={p10,p11},S3={p12, p13,p14,p15,p16},孤立零件为p2、p3、p7和p8。根据子装配体稳定性检验及矫正处理、冲突无干涉性检验及矫正处理,形成的子装配体为A1={p1,p2,p3,p4, p5,p6}和A2={p9,p12,p13,p14,p15,p16}。最后将子装配体A1和A2与孤立零件p7、p8、p10、p11组成新的产品模型,利用子装配体识别算法递归得到上一级子装配体A3={A1,A2,p7}和父级子装配体A4={A3, p8,p10,p11}。根据子装配体得到齿轮油泵的装配结构树模型如图6所示。

图6 齿轮油泵的装配结构树Fig.6 The tree structure of gear-oil-pump assembly

4 结束语

装配序列规划是产品制造周期中的重要环节,直接决定了产品的制造成本和质量。然而装配序列规划是一个典型的组合优化问题,在求解过程中很容易出现组合爆炸问题。通过将复杂的产品划分成合理的子装配体,可解决装配规划零件规模和搜索空间过大的问题。根据产品零件连接无向图找出连接关键件和识别关键件,然后再结合子装配体的稳定性和独立无干涉性约束要求,能够快速准确识别出复杂产品中的有效子装配体。同时,基于深度搜索策略,更有效地将子装配体识别方法与子装配体序列规划方法有机结合,从而高效地服务于复杂产品的装配序列规划。

[1] 常亮,刘华,古天龙,等.基于启发式DCPM-FGA的产品装配序列规划[J].计算机集成制造系统,2011,17(2): 239-247.

[2] 张勐,古天龙.基于带权无向连接图的子装配体识别方法研究[J].桂林电子科技大学学报,2008,28(1):19-22.

[3] 龚京忠,李国喜,臧宇飞,等.基于有向图子装配识别的装配序列规划[J].机械设计与制造,2008(9):201-203.

[4] 曹德君,田锡天,耿俊浩,等.在装配序列规划中子装配体识别方法研究[J].机械设计与制造,2009(10):126-128.

[5] 王孝义,汪惠芬.基于结构树重构的复杂产品多级子装配规划研究[J].机械科学与技术,2011,30(5):797-803.

[6] 赵姗姗,赵宏,高亮,等.基于功能结构树的工艺子装配体识别及其装配约束关系的分析[J].中国机械工程, 2012,23(13):1615-1619.

[7] 王永,刘继红.面向协同装配规划的装配单元规划方法[J].机械工程学报,2009,45(10):172-179.

[8] Wang Yong,Liu Jihong.Subassembly identification for assembly sequence planning[J].The International Journal of Advanced Manufacturing Technology,2013,68 (14):1-13.

编辑:翁史振

Subassembly identify method based on identify key part

Dong Shilong,Gu Tianlong,Xu Zhoubo
(School of Computer Science and Engineering,Guilin University of Electronic Technology,Guilin 541004,China)

In order to alleviate the combination explosion problem in the process of complex product assembly sequence planning,base on the connected undirected graph and the subassemblies constraints,a new subassembly identify algorithm is proposed.The“connection key part”and“identify key part”are found by the connected undirected graph to distinguish between the different part sets.All effective subassemblies of the complex product are found out by the stability and independence without conflict of the subassembly.Then the depth search strategy is used to generate the part assembly sequence of each subassembly,and get the assembly tree structure of the complex product.The demonstration of gear-oil-pump assembly proves that the new subassembly identify method is effective.

assembly sequence planning;identify key part;subassembly identify

TP391

A

1673-808X(2015)01-0147-05

2014-03-27

国家自然科学基金(61262030,61100025)

古天龙(1964-),男,山西芮城人,教授,博士,研究方向为形式化方法、符号计算。E-mail:cctlgu@guet.edu.cn

董士龙,古天龙,徐周波.基于识别关键件的子装配体识别方法[J].桂林电子科技大学学报,2015,35(1):147-151.