基于人工干預(yù)的鈑金零件排樣算法

謝友寶，呂永海，張 睿，徐麗笑

(南昌航空大學(xué)航空制造工程學(xué)院，南昌 330063)

基于人工干預(yù)的鈑金零件排樣算法

謝友寶，呂永海，張 睿，徐麗笑

(南昌航空大學(xué)航空制造工程學(xué)院，南昌 330063)

針對飛機鈑金零件排樣中存在大量的凹形零件，這些零件尺寸差異較大，將人工干預(yù)排樣與改進(jìn)的最低水平線搜索算法相結(jié)合，對凹形零件內(nèi)部再加以利用，提出一種可滿足實際生產(chǎn)需要的排樣算法。該算法利用最小包絡(luò)矩形把不規(guī)則零件轉(zhuǎn)化成矩形零件，并由人工選擇凹形零件的凹形區(qū)域，利用傳統(tǒng)的最低水平線搜索算法改進(jìn)后的算法進(jìn)行排樣，若遇到凹形零件則在其中插入尺寸相對較小的零件，直到零件排至板材末端。自動排樣完畢進(jìn)入人工干預(yù)階段，在一些空白區(qū)域再次排入零件，從而得到利用率較高的排料圖。實驗結(jié)果表明，將該算法應(yīng)用到鈑金零件排樣系統(tǒng)中，無論是在系統(tǒng)運行時間上還是在排樣利用率方面都能得到滿意的效果。

凹形零件;人工干預(yù);最低水平線搜索算法;最小包絡(luò)矩形

0 引言

鈑金零件大量地應(yīng)用于機械制造、航空航天等許多行業(yè)中。零件排樣結(jié)果的好壞對這些行業(yè)生產(chǎn)的合理性與經(jīng)濟性等指標(biāo)皆具有重要影響。因此開發(fā)出一套高效、高利用率的排樣方案是機械制造領(lǐng)域的一項重要課題，排樣技術(shù)的研究具有非常重要的實際意義。

所謂板材排樣是指將板材分割成各種形狀的毛坯零件，其中的鈑金零件包括規(guī)則零件和不規(guī)則零件。在我國許多企業(yè)的機械制造生產(chǎn)中，鈑金零件排樣很多是依靠人工經(jīng)驗試湊排樣，經(jīng)過多次反復(fù)后找出一個主觀認(rèn)為較好的排樣方案［1］。隨著計算機技術(shù)的不斷發(fā)展，CAD/CAM已在越來越多的領(lǐng)域發(fā)揮作用，可以形象而逼真地完成自動優(yōu)化排樣過程。目前，規(guī)則零件的排料，其中比較典型的有校核碰撞法［2］、分支定界法［3］、人工智能算法等，從而使得規(guī)則零件的自動排樣問題得到很好地解決。但是在一般情況下，大部分的待加工的鈑金零件都是不規(guī)則零件。尤其是在飛機鈑金零件的下料中，零件形狀極不規(guī)則，很多零件內(nèi)部還存在很大的凹形未利用區(qū)域，使得零件的排料算法運算異常復(fù)雜，生產(chǎn)效率大大降低。因此，國內(nèi)外一些學(xué)者進(jìn)行了大量的研究，其中運用最多的還是最小包絡(luò)矩形法即先將不規(guī)則零件轉(zhuǎn)化為矩形件(對零件進(jìn)行圖形聚合處理［4］求組合后的包絡(luò)矩形)，再按規(guī)則零件排樣算法進(jìn)行排樣。但是，該種排樣方法在包絡(luò)矩形內(nèi)部的局部利用率大大降低，即使可以對部分零件進(jìn)行圖形聚合，但是該方法對很多零件而言具有很大的局限性。所以本文對不規(guī)則零件內(nèi)部存在大的空余塊進(jìn)行再利用，對最最低水平線搜索算法進(jìn)行了改進(jìn)，并結(jié)合ObjectARX二次開發(fā)技術(shù)中圖形數(shù)據(jù)庫碰撞技術(shù)以及圖塊插入技術(shù)。采用人工干預(yù)排樣，解決包絡(luò)矩形局部利用率低的問題，開發(fā)出軟件用時少，排樣利用率高的算法。實驗證明該算法是針對形狀各異、大小不一的零件排樣的有效算法。

1 排樣問題描述

在鈑金零件的排樣中，假設(shè)參與排樣的第i個零件為 Pi，則在板材 B 上參與排樣的零件 P1，P2，P3，…Pi，…Pn必須滿足以下約束條件［5］:

(1)Pi，Pj互不干涉，i，j=1，2，…，n 且 i≠ j。

(2)零件 Pi必須完全在板材 B 內(nèi)，i=1，2，…，n。

(3)零件的排樣必須滿足一定的工藝要求，比如零件間距，板材邊距等參數(shù)。

假設(shè)Si為零件i的實際面積，板材的長和寬分別為L，W，zi為零件i在板材上的插入因子，值為1或0。則原材料利用率R的目標(biāo)函數(shù)為:

若 Di(xi，yi，αi，si，ei)為零件 i在板材中的具體位置，(xi，yi)為零件經(jīng)旋轉(zhuǎn)αi的內(nèi)部各個點的坐標(biāo)，(si，ei)為代表零件的工藝參數(shù)(本文只考慮零件間的間距和板材的邊距)，則零件排樣約束條件的數(shù)學(xué)表達(dá)式如下:

零件排樣的目標(biāo)為:在(2)、(3)、(4)三個約束條件下，使得板材利用率R達(dá)到(1)式的結(jié)果。

2 算法的求解過程

2.1 零件預(yù)處理

本文所涉及的算法基于最小包絡(luò)矩形法，凹形區(qū)域采用人工選取，對于零件形狀的描述只需解析零件包絡(luò)矩形的特征。任何一個復(fù)雜的不規(guī)則零件都可以得到其最小包絡(luò)矩形，方法是將零件在其AutoCAD圖形中繞零件上面的任何一點以1°為單位進(jìn)行旋轉(zhuǎn)90°從而遍歷所有可能的包絡(luò)矩形，并依次計算其包絡(luò)矩形面積從而得到其最小的。在本文中若最小包絡(luò)矩形長度小于寬度，則將零件再旋轉(zhuǎn)90°。獲得最小包絡(luò)矩形后采用SQL Server2000保存其信息(如長度、寬度、面積、零件類型等)。通過零件預(yù)覽，若零件內(nèi)部空余塊很大可再加以利用，則將該零件標(biāo)志為凹形零件，選取其最大的空白區(qū)域如圖1所示，通過直接點擊鼠標(biāo)獲取該面域。圖中包含有該零件的包絡(luò)矩形，其中虛線區(qū)域為所選的零件凹形區(qū)域。

圖1 選取凹形區(qū)域

2.2 算法的實現(xiàn)

(1)零件的排序

零件的排序很大程度上影響和決定著排料圖最終布局的合理性，根據(jù)每個零件對排料圖最終布局的影響程度，我們對零件賦予不同的優(yōu)先權(quán)。在排料實踐中形成了很多對賦予待排零件優(yōu)先權(quán)的規(guī)則，其中比較理想并且應(yīng)用最多的有如下幾種［6］:①按零件最小包絡(luò)矩形面積遞減順序;②按零件最小包絡(luò)矩形長度遞減順序;③按零件最小包絡(luò)矩形寬度遞減順序。但以上三個規(guī)則都有其局限性，都忽略了其他兩個因素對排料的影響。在本文中，考慮長條零件對排樣結(jié)果影響較大，在考慮零件的面積時兼顧零件的長度，為了使長條零件獲得排樣優(yōu)先權(quán)，定義如下條件作為判斷標(biāo)準(zhǔn):

其中l(wèi)，w分別為零件最小包絡(luò)矩形的長度和寬度，l≥w(零件預(yù)處理中將包絡(luò)矩形長度小于寬度的情況進(jìn)行了轉(zhuǎn)換)。t作為條件中的判斷指數(shù)，在應(yīng)用中可根據(jù)需要自定。所以本文中優(yōu)先按(5)式計算結(jié)果大小遞減順序排放長條零件，而后其他零件根據(jù)零件面積順序排樣。排樣算法的定序同時也要兼顧定位的方式，與定位規(guī)則以及其他約束條件相匹配，才能使算法運行可靠。

(2)改進(jìn)的最低水平線搜索算法

最低水平線法是一種不斷更新水平線集的排放算法［7］，是目前算法中應(yīng)用廣泛的一種零件定位規(guī)則，而最低水平線搜索算法則是在它的基礎(chǔ)上增加了一個搜索策略，其基本思想就是優(yōu)先選擇最低的水平線進(jìn)行插入零件，若水平線長度小于當(dāng)前零件的長度則優(yōu)先搜索后面未排樣的合適的零件，將該合適的零件與當(dāng)前前待排零件進(jìn)行置換，直到未找到合適零件再將水平線提升，并依次繼續(xù)以上過程。

本文所涉及算法在傳統(tǒng)的最低水平線搜索算法增加了以下幾個策略:在排樣過程中若板材已排放凹形零件后，則在后續(xù)每次排放零件時都優(yōu)先搜索凹形零件并判斷凹形零件中是否能排放該零件，把凹形區(qū)域作為新一板材進(jìn)行排樣，并在其中應(yīng)用具有旋轉(zhuǎn)策略的最低水平線算法，若在所有凹形零件中都無法插入待排零件，則將該零件轉(zhuǎn)入到板材中進(jìn)行排樣;在搜索過程中考慮盡量將大零件優(yōu)先排放，減小大零件對后續(xù)排樣的影響，所以增加零件旋轉(zhuǎn)策略即在水平線長度小于零件最小包絡(luò)矩形長度時，則考慮包絡(luò)矩形的寬度是否小于水平線長度，若滿足則對零件進(jìn)行旋轉(zhuǎn)排樣，否則再搜索下一零件;將搜索的可插入零件先排入板材中，隨后將其從零件列表中刪除，而不與當(dāng)前待排零件進(jìn)行置換。

在排樣過程中，將未排零件集、凹形零件集、水平線集分別使用動態(tài)鏈表表示。零件集鏈表中零件順序按照以上零件的排序規(guī)則，每排入一個零件則將其結(jié)點刪除，當(dāng)零件鏈表為空時零件排樣結(jié)束;在凹形零件集中凹形區(qū)域順序按照對應(yīng)零件插入順序，每遇到排入凹形零件則將鏈表末尾增加一結(jié)點;而在板材水平線集鏈表中水平線順序按照從左到右的順序，每插入一零件則將鏈表更新。排樣的具體實現(xiàn)過程如下:

2.3 算例分析

將該算法應(yīng)用于飛機鈑金零件下料軟件系統(tǒng)中，該系統(tǒng)采用AutoCAD二次開發(fā)工具中的ObjectARX開發(fā)技術(shù)，與VC++相結(jié)合在AutoCAD中生成排料圖。自動排樣過程采用ObjectARX插入塊技術(shù)，生成排料圖。本文算例排料圖如圖2所示。從排樣結(jié)果可以看出，部分零件的形狀極不規(guī)則但其內(nèi)部空白區(qū)域得到了較合理的利用，其利用率為67%。

圖2 自動排樣的排樣效果

3 人工干預(yù)

盡管在以上改進(jìn)最低水平線搜索算法的應(yīng)用下，不規(guī)則零件的排樣得到了改善，但是從圖中可以看出有部分區(qū)域仍然可以得到利用。在ObjectARX二次開發(fā)技術(shù)中，圖形輪廓的判交相對算法較復(fù)雜，若由系統(tǒng)遍歷所有可排樣位置，計算量大，系統(tǒng)運行慢，但是在人工干預(yù)中由用戶指定零件的排樣區(qū)域，系統(tǒng)自動調(diào)整其排樣位置，可使得排樣的利用率在保證工作效率的情況下得到進(jìn)一步的提高。圖3所示為經(jīng)人工干預(yù)后的排料圖，其利用率達(dá)到了71%。

圖3 人工干預(yù)后的排樣效果

4 結(jié)束語

本文以最低水平線搜索算法為基礎(chǔ)，結(jié)合不規(guī)則零件凹形區(qū)域的再次利用策略，提出改進(jìn)的最低水平線搜索算法，將凹形區(qū)域的搜索融入其中。并且在自動排樣完畢后采用人工干預(yù)，利用ObjectARX的零件判交技術(shù)，使得不規(guī)則零件得到更合理的排樣。實驗結(jié)果表明，本文所提出的算法在排樣利用率以及排樣效率方面都比較優(yōu)秀，能解決零件之間尺寸相對大的排樣問題，對飛機鈑金零件的下料具有很重要的實際意義。

［1］郭乃成，王定強.計算機輔助沖裁排樣優(yōu)化［J］.鍛壓技術(shù)，1988，8(1):25-29.

［2］黃健.集CAD/CAM/CNC于一體的板材下料系統(tǒng)［J］.機械工業(yè)自動化，1997，19(3):20-22.

［3］Cihan H.Dagli.Knowledge-based Systems for Cutting Stock Problems.European Journal of Operation Research，1990，44(1/2):160-166.

［4］賈桂紅.基于VC++/Object ARX的二維排料與NC自動編程系統(tǒng)設(shè)計［J］. 煤礦機械，2008，29(7):95-96.

［5］鄭文清，陳建華.滿足工藝品剪切要求的二維不規(guī)則排料算法［J］. 計算機技術(shù)與發(fā)展，2008，18(11):26-31.

［6］劉崇倫.計算機輔助二維排料與數(shù)控自動編程系統(tǒng)的實現(xiàn)［D］.華北電力大學(xué)，2005.

［7］王竹婷，劉林.改進(jìn)的最低水平線搜索算法求解矩形排樣問題［J］. 工程設(shè)計學(xué)報，2009，16(2):98-103.

Sheet Metal Parts Layout Algorithm based on Manual Intervention

XIE You-bao，LV Yong-hai，ZHANG Rui，XU Li-xiao
(Nanchang HangKong University，School of Aeronautical Manufacturing Engineering，Nanchang 330063，China)

Aiming at the existence of numerous concave parts which have large distance of dimensional gap between each of them in aircraft sheet metal parts layout，a layout algorithm is proposed which make use of the pack space of the concave parts secondarily while integrating Human-Computer Interaction with Improved Lowest Horizontal Search Algorithm to meet needs of actual production.Transforming irregular part into rectangular part with minimum envelop rectangle and picking the pack space of concave parts artificially，this algorithm take advantage of the improved conventional lowest horizontal search algorithm to insert parts on plate until the end of the plate is occupied while the concave part is inserted by the part with smaller dimension if that is lie.The stage of manual intervention proceeds to insert some parts in pack space when automatic layout stage is completed so as to get the layout graph with high layout utilization.The experimental results show that the improved algorithm could give satisfied results whether shorten the time of system running or improve the layout utilization when it is applied by the sheet metal parts layout system.

concave parts;manual intervention;the lowest horizontal search algorithm;minimum envelop rectangle

TP391.73

A

1001-2265(2011)02-0086-03

2010-08-16

謝友寶(1968—)，男，江西安福人，南昌航空大學(xué)航空制造工程學(xué)院教授，主要研究方向為機電一體化設(shè)備研制、數(shù)控技術(shù)、CAD/CAM技術(shù)、計算機軟硬件系統(tǒng)開發(fā)等，(E-mail)xyb68@tom.com。

(編輯 趙蓉)