楊傳華,吳錦文,李殿國,楊海

(1.佳木斯大學(xué) 機械工程學(xué)院,黑龍江 佳木斯 154007;2.奇瑞汽車股份有限公司,安徽 蕪湖241009;3.東芝大連有限公司,遼寧大連 116600)

0 引言

隨著社會的發(fā)展、科技的進步,二維圖形排樣廣泛存在于許多工業(yè)中,如：機械廠中金屬板材的排樣,玻璃廠中玻璃的排樣,服裝廠中布料的排樣。長期以來,人們不斷地研究各種排樣算法,對于一維排樣和二維規(guī)則圖形排樣已經(jīng)有了比較成熟的排樣算法,而對于不規(guī)則的圖形[1],現(xiàn)在采用比較多是矩形包絡(luò)法、遺傳算法和模擬退火算法。本文先采用矩形包絡(luò)法對不規(guī)則圖形進行預(yù)處理,在此基礎(chǔ)上采用基于最低水平線的搜索算法和平移靠接算法[2]對預(yù)處理圖形進行排樣。

1 最小矩形包絡(luò)法、基于最低水平線的搜索算法

1.1 最小矩形包絡(luò)法[3]

最小矩形包絡(luò)法就是用矩形將不規(guī)則的圖形包絡(luò)在矩形內(nèi),并使包絡(luò)矩形的面積最小。如圖 1,2所示：

1.2 基于最低水平線的搜索算法[4]

分析 BL算法[5]和“下臺階算法”可以發(fā)現(xiàn)：前者經(jīng)常會出現(xiàn)排樣左側(cè)偏高的情況,而后者經(jīng)常會出現(xiàn)右側(cè)偏高現(xiàn)象。最低水平線算法解決了此問題,具體步驟如下：

Step 1：設(shè)置初始最高輪廓線為板材最下面的邊;

Step 2：每當(dāng)要排入一個零件 Pi時,就在最高輪廓線集中選取最低的一段水平線,如有數(shù)段,則選取最左邊的一段,測試該段線的寬度是否大于或等于待排零件的寬度：

(1)如果該段線的寬度大于或等于要排入零件的寬度,則將該零件在此位置排放,同時更新零件最高輪廓線;

(2)否則,查詢與最低水平線段相鄰的左、右兩段水平線,將最低水平線提升至相鄰且高度較低的一段平齊,同時更新零件最高輪廓線;

Step 3：重復(fù) Step 2過程,直至能排入該零件,并求出此時的最大高度;

Step 4：重復(fù) Step 2和 Step 3過程,直至所有零件排放完畢,最后所得的最大高度即為所需板材的高度。

基于最低水平線的搜索算法是在最低水平線算法排樣中出現(xiàn)了要排入的零件的寬度大于最高輪廓線集中最低的一段(或多段)水平線時,而不去更新零件的最高輪廓線,而是從未排樣的零件中挑選寬度小于最低水平線寬度的零件[6]。將此兩個零件交換順序,而后重新生成新的排列順序。

2 平移靠接算法原理[9-11]

平移靠接算法是將兩個不規(guī)則圖形在水平或豎直發(fā)方向上進行靠接,直至兩個圖形剛好相接(但不交叉,即無重疊區(qū)域)。以圖 3在水平方向平移靠接為例進行說明：

圖 3 平移靠接前

(1)首先掃描靠接區(qū)域和確定靠接輪廓線

通過掃描可以確定靠接區(qū)域為圖形 1的右側(cè)和圖形 2的左側(cè),從而可以判斷出圖形 1的靠接輪廓線為ABCDE,圖形 2的靠接輪廓線為 FGHIJK[7-8]。

(2)選取兩個圖形靠接輪廓線上的折點(即凸凹點)

對于圖形 1輪廓線上的折點有：A、B、C、D、E,圖形2輪廓線上的折點有 ：F、G、H、I、J、K。

(3)確定各個折點的水平靠接距離

先確定圖形 1上折點的水平靠接距離,過 A點向右作水平線與圖形 2的輪廓線相交(如圖 3所示),并標(biāo)記此線段的長度為 L1,用此方法可以求得過 B、C、D、E四點與圖形 2輪廓線相交的水平線的長度,分別標(biāo)記為 L3、L6、L8、L9。

同理可以確定圖形 2上折點的水平靠接距離,分別標(biāo)記為 L2、L4、L5、L7、L9。由于過 F點作水平線不與圖形1的輪廓線相交,所以不作記錄。各個水平靠接距離形成了數(shù)集 W={L1,L2,L3,L4,…,L9}。

(4)確定最終的水平靠接距離 Wmin

通過數(shù)值比較從 W數(shù)集中選出數(shù)值最小的 L值作為水平靠接距離 Wmin。(對于此例,L8的值最小,所以Wmin=L8)。

(5)進行水平靠接

以 L8為水平靠接距離進行水平靠接,靠接后的圖形如圖 4所示。

圖 4 平移靠接后

3 基于 PRO/E平臺的排樣實例及說明

3.1 參與排樣的鈑金件的原始數(shù)據(jù)

參與排樣的鈑金件共有 8個,用 PRO/E軟件繪出后如下圖所示(單位為：mm),其中鈑金件外的紅線框為鈑金件的最小包絡(luò)矩形。

3.2 用 PRO/E軟件中的排樣系統(tǒng)的排樣結(jié)果

將這8個鈑金件放在寬 100mm,足夠長的鈑金件上排樣,排樣的順序為零件 1、零件 7、零件 2、零件 6、零件4、零件 3、零件 8、零件 5。如果用的長度越小,則排樣的效果就越好。PRO/E軟件中的排樣系統(tǒng)的排樣結(jié)果如圖 5所示,此時,鈑金件所用的板材長度是 49mm。

3.3 用本論文的排樣算法的排樣結(jié)果

用上述同樣的排樣方式和排樣順序,鈑金件所用的長度是 40mm。對上述的 8個鈑金件進行排樣,排樣結(jié)果如圖 6所示,此排樣算法的排樣過程說明：①從板材的最左下端排鈑金件 1;②排鈑金件 7并進行向左水平靠接;③排鈑金件 2;④排鈑金件 6并進行向左水平靠接;⑤排鈑金件 4發(fā)現(xiàn)鈑金件 6的右側(cè)寬度不夠,此時運用基于最低水平線的搜索算法從未排樣的鈑金件中搜索到能在此處排樣的鈑金件 8,交換鈑金件 4和鈑金件 8的排樣順序,(即未排鈑金件的排樣順序為：鈑金件 3、鈑金件 4、鈑金件 5),此時更新最低水平線為鈑金件 6最小包絡(luò)矩形的上端線段;⑥在更新后的最低水平線上排鈑金件 3并進行向下靠接,此時更新最低水平線為鈑金件 7最小包絡(luò)矩形的上端線段;⑦在更新后的最低水平線上排鈑金件 4并進行向左水平靠接;⑧排鈑金件 5并進行向下靠接。經(jīng)過此算法所得排樣圖如圖 7所示。

4 結(jié)束語

[1]黃紅兵,蔣望東.二維不規(guī)則零件排樣問題的研究[J].廣西科學(xué)院學(xué)報,2004,20(4)：225-227.

[2]Song Yanan,Ye Jiawei,Wei Liangliang,etal.The Analysis,New Development and of Packing(Nesting),Symposium on the Development of Ship-building＆Ship-repairing Industry 2003,Guangzhou China,2003(3)：21-22.

[3]曹新明,蔣瑞斌.不規(guī)則零件最小包絡(luò)矩形的求解研究[J].科技通報,2007,1(23)：102-105.

[4]朱冠華.矩形件排樣中基于最低水平線的改進算法[J].茂名學(xué)院報,2006,1(16)：28-32.

[5]Jokobs S.On genetic algorithms for the packing of polygons.European Journal of Operational Reseaech,1996,88：165-181.

[6]AdamowiczM,Albano A.A solution of the rectangular cutting-stock problem[J].IEEE Transactions on Systems,Man,and Cybernetics,1976,SMC-6(4)：302-310.

[7]覃中平,張煥國.確定凸多邊形平移時最初碰撞部位的最優(yōu)算法[J].計算機學(xué)報,1992,15(3)：171-177.

[8]汪嘉業(yè).平面上簡單多邊形平移時確定碰撞部位的最優(yōu)算法[J].計算機學(xué)報,1992,15(8)：582-588.

[9]Cheng S K,Rao K P.Large-Scale nesting of irregu lar patterns using compact neighborhood algorithm.Journal of Materials Processing Technology,2000,(103)：135-140.

[10]宋亞男,葉家瑋,鄧飛其,等.不規(guī)則圖形排樣系統(tǒng)中靠接算法比較研究[J].計算機工程,2004,19(30)：8-10.

[11]宋亞男,葉家瑋,鄧飛其,等.排樣系統(tǒng)中基于位圖的三種靠接算法比較[J].武漢科技大學(xué)學(xué)報,2004,1(27)：54-57.