董士龍,古天龍,徐周波

(桂林電子科技大學(xué)計算機科學(xué)與工程學(xué)院,廣西桂林 541004)

基于識別關(guān)鍵件的子裝配體識別方法

董士龍,古天龍,徐周波

(桂林電子科技大學(xué)計算機科學(xué)與工程學(xué)院,廣西桂林 541004)

為避免在復(fù)雜產(chǎn)品裝配序列規(guī)劃過程中出現(xiàn)過度的組合爆炸,同時基于產(chǎn)品無向連接圖和子裝配體約束要求,提出一種新的子裝配體識別方法。通過產(chǎn)品零件的無向連接圖,找出復(fù)雜產(chǎn)品中的“連接關(guān)鍵件”和“識別關(guān)鍵件”,用于區(qū)分不同的零件連接集合;通過子裝配體的穩(wěn)定性檢驗及矯正、獨立無沖突性檢驗及矯正,找出復(fù)雜產(chǎn)品中的有效子裝配體;采用深度搜索策略生成每個子裝配體的裝配序列,得到復(fù)雜產(chǎn)品的裝配樹結(jié)構(gòu)。通過某齒輪油泵模型的實例演示,證明了子裝配體識別方法的有效性。

裝配序列規(guī)劃;識別關(guān)鍵件;子裝配體識別

隨著市場競爭的日益激烈和全球一體化時代的到來,國內(nèi)外制造業(yè)的生存和發(fā)展都面臨著嚴峻的挑戰(zhàn)。據(jù)統(tǒng)計,現(xiàn)代產(chǎn)品制造過程中,裝配費用占整個產(chǎn)品總制造費用的30%～50%,裝配時間也占據(jù)整個產(chǎn)品總制造時間的40%左右[1]。因此,產(chǎn)品裝配序列規(guī)劃(assembly sequence planning,簡稱ASP)的研究已成為一個重要的課題。

對于零件數(shù)量眾多的大型復(fù)雜產(chǎn)品,如果單純采用優(yōu)先約束法、割集拆卸法等典型的裝配序列規(guī)劃方法,不可避免面臨“組合爆炸”問題。解決這個難點的有效途徑之一,就是采用子裝配技術(shù)將復(fù)雜產(chǎn)品的裝配結(jié)構(gòu)層次化,從而縮減每個層次中被處理的零件數(shù)量,提高裝配規(guī)劃效率。

由于子裝配技術(shù)可有效組織和管理復(fù)雜產(chǎn)品的裝配序列規(guī)劃過程、提高裝配效率,許多學(xué)者對子裝配體的識別方法進行了研究。Dini首次提出子裝配概念,并給出了子裝配體提取方法,但該方法需要參與運算的矩陣數(shù)量較多;張勐等[2]根據(jù)零件連接類型,建立裝配體的帶權(quán)無向連接圖模型,通過模型邊權(quán)值的設(shè)定識別子裝配體,但該方法權(quán)值的分配存在一定的困難;龔京忠等[3]采用局部約束有向圖表達裝配體中的連接與裝配關(guān)系,通過建立裝配鄰接和阻礙矩陣,采用緊連接分析和有向圖分析識別子裝配體,但該方法過于復(fù)雜,不利于復(fù)雜產(chǎn)品的裝配序列規(guī)劃;曹德君等[4]從裝配有向圖中識別基礎(chǔ)件,通過模糊數(shù)學(xué)理論建立幾何和工藝優(yōu)先約束因素相對于裝配難度的隸屬函數(shù),以綜合函數(shù)值作為權(quán)值得到賦權(quán)配合關(guān)聯(lián)圖,并通過設(shè)置難度系數(shù)和以基礎(chǔ)件為核心對零件節(jié)點進行合并與組合得到簡化配合關(guān)聯(lián)圖,在此基礎(chǔ)上通過一定規(guī)則和基礎(chǔ)件識別子裝配體,但該方法中規(guī)則的獲取和確定十分困難;王孝義等[5]在分析子裝配層次劃分與產(chǎn)品結(jié)構(gòu)樹形成關(guān)系的基礎(chǔ)上,提出了一種基于結(jié)構(gòu)樹重構(gòu)的產(chǎn)品多級子裝配體識別方法,但產(chǎn)品結(jié)構(gòu)樹的存儲空間過大;趙姍姍等[6]通過分析功能子裝配體間的干涉關(guān)系和穩(wěn)定性,提出了一種工藝子裝配體識別算法,但該方法中合理的工藝子裝配體定義是個難點;王永等[7-8]總結(jié)了不同的子裝配體識別方法,指出子裝配體應(yīng)滿足的三大約束條件:拓撲約束條件、幾何約束條件和工藝約束條件。

鑒于此,利用產(chǎn)品零件無向連接圖找出“連接關(guān)鍵件”和“識別關(guān)鍵件”,基于子裝配體的穩(wěn)定性檢驗及矯正、獨立無干涉性檢驗及矯正,提出一種新的子裝配體識別方法。該方法可將復(fù)雜產(chǎn)品分割為多個子裝配體,而且各個子裝配體之間相互獨立,根據(jù)具體需要,在子裝配體中找出下一級子裝配體和上一級子裝配體,從而得到產(chǎn)品的結(jié)構(gòu)分層樹裝配模型,并采用深度搜索策略生成每個子裝配體的裝配序列,得到復(fù)雜產(chǎn)品的裝配樹結(jié)構(gòu)。

1 裝配連接圖

一個產(chǎn)品通常由許多零部件以一定的裝配連接而成,產(chǎn)品零件的連接關(guān)系可用一個無向連接圖G=〈V(G),E(G)〉描述,如圖1所示。其中:節(jié)點集V(G) ={v1,v2,…,vn}(n為產(chǎn)品零件數(shù)量)為非空有限集,頂點元素vi表示裝配體的零件pi;邊集E(G)={e1, e2,…,em}(m為產(chǎn)品連接數(shù)量)也為非空有限集,無向圖的邊元素ei表示該邊兩端頂點(零件)的連接關(guān)系。

圖1 無向連接圖Fig.1 The undirected connected graph

產(chǎn)品零件間通常存在緊固連接、一般接觸連接和無連接3種連接關(guān)系。設(shè)產(chǎn)品P由n個零件組成,即P={p1,p2,…,pn},則緊固連接關(guān)系和一般接觸連接關(guān)系的定義如下。

定義1 若零件pi和pj在某裝配方向k∈(x, y,z,-x,-y,-z)上裝配后形成不可自分離的整體,即必須借助一定外力才能使2個零件分開,則稱零件pi與零件pj存在緊固連接關(guān)系(如螺紋、焊接等)。在無向連接圖中,緊固連接關(guān)系用實線表示。

定義2 若零件pi和pj在所有裝配方向{x,y, z,-x,-y,-z}上均為一般物理接觸連接或無連接(但至少存在一個方向的一般物理接觸),即2個零件的裝配是不穩(wěn)定的、易自分離的組合,則稱零件pi與零件pj存在一般接觸連接關(guān)系(如依靠、貼合等)。在無向連接圖中,一般接觸連接關(guān)系用虛線表示。

無連接關(guān)系的2個零件在無向連接圖中對應(yīng)頂點之間沒有邊線連接。

由于復(fù)雜產(chǎn)品的零件數(shù)量較多,零件間連接接觸關(guān)系比較復(fù)雜。為了合理地劃分子裝配體,提出“連接關(guān)鍵件”和“識別關(guān)鍵件”概念。

定義3 若產(chǎn)品中某零件p的緊固連接數(shù)量NK≥max[3,(N-3)/lg(N+1)](N為產(chǎn)品的零件數(shù)量),則定義該零件p為連接關(guān)鍵件。

定義4 若產(chǎn)品中某零件p不是非關(guān)鍵件,且同時與大于等于2個連接關(guān)鍵件存在連接關(guān)系,則定義該零件p為識別關(guān)鍵件。

2 子裝配技術(shù)

2.1 子裝配體概念

當(dāng)一個裝配體是另一個裝配體的零部件時,稱其為子裝配體。一個子裝配體應(yīng)滿足如下約束要求:

1)穩(wěn)定性要求:組成子裝配體的零件之間的連接應(yīng)穩(wěn)定,即在子裝配體移動過程中不會發(fā)生自分離。

2)獨立無干涉性要求:同一級子裝配體之間相互獨立且不干涉裝配;子裝配體內(nèi)部的零件或子裝配體與不屬于該子裝配體的零件相互獨立且不干涉裝配。

此外,在產(chǎn)品裝配過程中的零件依據(jù)相互的連接關(guān)系,按照特定的定位方式進行安裝,因此,需要在裝配過程中選擇某個零件作為裝配基礎(chǔ)件。裝配基礎(chǔ)件在裝配過程中固定不動,其他零件都以它為基礎(chǔ)進行裝配。在整個裝配過程中基礎(chǔ)件是起始裝配零件,其他零件都依附于它,因此,基礎(chǔ)件往往處于裝配體的中心位置。每個子裝配體內(nèi)部都有且只有一個基礎(chǔ)件?；A(chǔ)件一般為體積和質(zhì)量較大、與其他零件的連接數(shù)量較多的零件,如箱體、基座等。

2.2 子裝配體識別算法

在復(fù)雜產(chǎn)品裝配規(guī)劃中,通常將產(chǎn)品遞歸分解成各級子裝配體,以便有效組織和管理產(chǎn)品裝配。即在裝配規(guī)劃過程中,將一個復(fù)雜的產(chǎn)品劃分為若干個子裝配體;根據(jù)具體需要,子裝配體又可劃分為下一級子裝配體和上一級子裝配體,直到滿足需求為止;在上層將子裝配體作為獨立的零件進行處理,在下層單獨處理子裝配體內(nèi)的零件。這樣,可有效縮減每個層次被處理的零件數(shù)量,減小裝配規(guī)模,提高裝配規(guī)劃效率。子裝配體劃分合理與否,直接決定后續(xù)裝配效率和裝配質(zhì)量。

利用產(chǎn)品零件無向連接圖找出“連接關(guān)鍵件”和“識別關(guān)鍵件”,然后基于子裝配體的穩(wěn)定性和獨立無干涉性提出新的子裝配體識別方法。算法流程圖如圖2所示。算法步驟如下:

1)找出復(fù)雜產(chǎn)品的所有連接關(guān)鍵件,并記錄到集合{C1,C2,…,Co},其中,o為連接關(guān)鍵件的總數(shù)量。這些連接關(guān)鍵件由于連接數(shù)量較多,除了用于找出識別關(guān)鍵件外,還可作為每個子裝配體中的裝配基準件。

2)基于連接關(guān)鍵件集合{C1,C2,…,Cm}找出產(chǎn)品中的識別關(guān)鍵件,并記錄到集合{K1,K2,…,Km},其中,m為識別關(guān)鍵件的總數(shù)量。

圖2 子裝配體識別算法流程圖Fig.2 The flow chart of subassembly identify

3)因為識別關(guān)鍵件Ki同時與多個連接關(guān)鍵件存在連接關(guān)系,所以識別關(guān)鍵件Ki的連接類型較復(fù)雜,也較易引發(fā)裝配沖突。因此,暫時忽略這些識別關(guān)鍵件Ki的所有連接關(guān)系,復(fù)雜產(chǎn)品將散裂為若干零件連接子集或一些孤立零件,而且這些連接子集中的零件與其他零件存在裝配干涉沖突的可能性很小。在這個過程中標記每個連接子集為S1,S2,…,Sh,其中,h為連接子集的數(shù)量。

4)檢驗零件連接子集Si的裝配穩(wěn)定性。若連接子集Si中某零件pi的連接類型均為一般接觸連接,且與連接子集Si外的某零件pj存在連接關(guān)系,則該子集Si不符合子裝配體穩(wěn)定性要求,執(zhí)行步驟5),進行穩(wěn)定性矯正處理;否則,若連接子集Si中所有零件均滿足裝配穩(wěn)定性要求,則該子集Si滿足子裝配體穩(wěn)定性要求,執(zhí)行步驟6),進行連接子集Si的獨立無干涉性檢驗。

5)子集穩(wěn)定性矯正。將與連接子集Si中某零件pi存在不穩(wěn)定連接關(guān)系的零件pj并入該連接子集Si,然后執(zhí)行步驟4),繼續(xù)進行連接子集Si的穩(wěn)定性檢驗。

6)檢驗零件連接子集的獨立無干涉性。若子集Si裝配完畢,連接子集Si外的某零件pj將無法裝配,則該子集Si與零件pj存在裝配沖突關(guān)系,執(zhí)行步驟7),進行獨立無干涉性處理;否則,若不存在其他零件pj與子集Si中的零件存在裝配沖突關(guān)系,執(zhí)行步驟8),進行連接子集合并處理。

7)子集獨立無干涉性矯正。將與子集Si存在裝配沖突的零件pj并入該連接子集Si,然后執(zhí)行步驟4),進行連接子集穩(wěn)定性檢驗。

8)連接子集都已經(jīng)過穩(wěn)定性檢驗矯正處理和獨立無干涉性檢驗矯正處理,若2個連接子集Si和Sj存在相同的零件pi,則這2個連接子集應(yīng)合并為一個較大的連接子集。所有連接子集Si都經(jīng)過合并檢驗處理后,將每個連接子集Si視為一個子裝配體Ai。

9)將子裝配體視作特殊的零件,與孤立零件一起,利用子裝配體識別方法遞歸尋找更高層次子裝配體;或?qū)⒆友b配體視作一個新裝配體,利用子裝配體識別方法尋找低層次子裝配體。最后,將每個子裝配體視為特殊的零件,與孤立零件一起構(gòu)成復(fù)雜產(chǎn)品的根裝配體。

2.3 子裝配體規(guī)劃算法

子裝配體識別可將復(fù)雜產(chǎn)品分解為一組子裝配體,每個子裝配體都是相互獨立的裝配體,而且零件數(shù)量相對較少。因此,復(fù)雜產(chǎn)品的裝配序列可由各子裝配體的裝配序列合并得到?；谏疃人阉鞑呗?提出一種有效的子裝配體的裝配序列規(guī)劃算法。算法流程圖如圖3所示。算法步驟如下:

圖3 子裝配體規(guī)劃算法流程圖Fig.3 The flow chart of subassembly planning algorithm

1)找出基準件B的緊固連接集合SB={b1,b2,…,bu},u為與基準件存在緊固連接關(guān)系的零件數(shù)量,并選擇一個零件作為下一個待裝配零件pw=bi。

2)找出與待裝配零件pw存在連接關(guān)系,且未包含在Q中的零件集合W={w1,w2,…,wl},l為與該零件連接的零件數(shù)量。若待裝配零件pw與Q中零件裝配后,與集合W中所有零件均不存在裝配沖突關(guān)系,則將零件pw加入到已裝配序列Q中,并標記為前序裝配零件,pf=pw,執(zhí)行步驟3);否則,零件pw將干涉其他零件的裝配,即零件pw不能作為待裝配零件,執(zhí)行步驟4)。

3)在集合W中選擇一個零件作為下一個待裝配零件pw=wj,并執(zhí)行步驟2)。

4)若前序裝配零件pf不等于基準件B,執(zhí)行步驟5);否則,即pf=B,執(zhí)行步驟6)。

5)將前序裝配零件pf的連接集合Sf中的其他未裝配零件fk作為新的下一個待裝配零件pw=fk,并執(zhí)行步驟2);若集合W中已無零件,則執(zhí)行步驟7)。

6)將基準件的緊固連接集合SB中的其他未裝配零件作為新的下一個待裝配零件pw=bt,并執(zhí)行步驟2);若集合SB中已無零件,則執(zhí)行步驟8)。

7)將已裝配序列Q中零件pf的前一個零件作為新的前序裝配零件pf,并執(zhí)行步驟4)。

8)所有零件都已遍歷,算法結(jié)束,即子裝配體裝配序列規(guī)劃結(jié)束,并輸出子裝配體的裝配序列規(guī)劃結(jié)果。

最后,將復(fù)雜產(chǎn)品的裝配序列表示為樹形結(jié)構(gòu),即并行裝配樹結(jié)構(gòu)。其中:樹的根節(jié)點表示復(fù)雜產(chǎn)品,樹的分支節(jié)點表示子裝配體或零件;父節(jié)點與子節(jié)點之間的無箭頭連線表示子裝配體及其組成零件之間的關(guān)系;兄弟節(jié)點之間的有箭頭連線表示同一子裝配體內(nèi)零件的裝配優(yōu)先關(guān)系(箭尾的零件優(yōu)先于箭頭的零件裝配),即表示子裝配體的零件裝配順序。

3 實例分析

使用Visual C++2010集成開發(fā)工具開發(fā)了“基于識別關(guān)鍵件的子裝配體識別系統(tǒng)”軟件平臺。同時,為了進一步證明子裝配體識別算法的有效性,利用開發(fā)的軟件平臺對圖4所示的某齒輪油泵模型進行了子裝配體識別規(guī)劃。圖4中,零件1～16分別為泵體、從動軸齒輪、填料、填料壓蓋、鎖緊螺母、主動軸齒輪、墊片、圓柱銷、泵蓋、墊圈、螺栓、鋼珠、鋼珠定位圈、彈簧、小墊片和螺栓。

由圖4所示齒輪油泵零件的連接類型,可得到齒輪油泵模型的無向連接圖如圖5所示。

圖5 齒輪油泵零件的無向連接圖Fig.5 The undirected connected graph of oil pump parts

基于圖5無向連接圖,可得到齒輪油泵模型的連接關(guān)鍵件集合為{p1,p9},識別關(guān)鍵件集合為{p2, p6,p7,p8,p11}。基于識別關(guān)鍵件,得到零件連接集合子集S1={p4,p5,p6},S2={p10,p11},S3={p12, p13,p14,p15,p16},孤立零件為p2、p3、p7和p8。根據(jù)子裝配體穩(wěn)定性檢驗及矯正處理、沖突無干涉性檢驗及矯正處理,形成的子裝配體為A1={p1,p2,p3,p4, p5,p6}和A2={p9,p12,p13,p14,p15,p16}。最后將子裝配體A1和A2與孤立零件p7、p8、p10、p11組成新的產(chǎn)品模型,利用子裝配體識別算法遞歸得到上一級子裝配體A3={A1,A2,p7}和父級子裝配體A4={A3, p8,p10,p11}。根據(jù)子裝配體得到齒輪油泵的裝配結(jié)構(gòu)樹模型如圖6所示。

圖6 齒輪油泵的裝配結(jié)構(gòu)樹Fig.6 The tree structure of gear-oil-pump assembly

4 結(jié)束語

裝配序列規(guī)劃是產(chǎn)品制造周期中的重要環(huán)節(jié),直接決定了產(chǎn)品的制造成本和質(zhì)量。然而裝配序列規(guī)劃是一個典型的組合優(yōu)化問題,在求解過程中很容易出現(xiàn)組合爆炸問題。通過將復(fù)雜的產(chǎn)品劃分成合理的子裝配體,可解決裝配規(guī)劃零件規(guī)模和搜索空間過大的問題。根據(jù)產(chǎn)品零件連接無向圖找出連接關(guān)鍵件和識別關(guān)鍵件,然后再結(jié)合子裝配體的穩(wěn)定性和獨立無干涉性約束要求,能夠快速準確識別出復(fù)雜產(chǎn)品中的有效子裝配體。同時,基于深度搜索策略,更有效地將子裝配體識別方法與子裝配體序列規(guī)劃方法有機結(jié)合,從而高效地服務(wù)于復(fù)雜產(chǎn)品的裝配序列規(guī)劃。

[1] 常亮,劉華,古天龍,等.基于啟發(fā)式DCPM-FGA的產(chǎn)品裝配序列規(guī)劃[J].計算機集成制造系統(tǒng),2011,17(2): 239-247.

[2] 張勐,古天龍.基于帶權(quán)無向連接圖的子裝配體識別方法研究[J].桂林電子科技大學(xué)學(xué)報,2008,28(1):19-22.

[3] 龔京忠,李國喜,臧宇飛,等.基于有向圖子裝配識別的裝配序列規(guī)劃[J].機械設(shè)計與制造,2008(9):201-203.

[4] 曹德君,田錫天,耿俊浩,等.在裝配序列規(guī)劃中子裝配體識別方法研究[J].機械設(shè)計與制造,2009(10):126-128.

[5] 王孝義,汪惠芬.基于結(jié)構(gòu)樹重構(gòu)的復(fù)雜產(chǎn)品多級子裝配規(guī)劃研究[J].機械科學(xué)與技術(shù),2011,30(5):797-803.

[6] 趙姍姍,趙宏,高亮,等.基于功能結(jié)構(gòu)樹的工藝子裝配體識別及其裝配約束關(guān)系的分析[J].中國機械工程, 2012,23(13):1615-1619.

[7] 王永,劉繼紅.面向協(xié)同裝配規(guī)劃的裝配單元規(guī)劃方法[J].機械工程學(xué)報,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

國家自然科學(xué)基金(61262030,61100025)

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

董士龍,古天龍,徐周波.基于識別關(guān)鍵件的子裝配體識別方法[J].桂林電子科技大學(xué)學(xué)報,2015,35(1):147-151.