基于啟發(fā)式包絡(luò)算法鋼板排料方法研究

李飛

在鋼結(jié)構(gòu)生產(chǎn)中,鋼板排料工作的主要任務(wù)是將一系列形狀各異的規(guī)則或不規(guī)則的二維零件在矩形鋼版上按最優(yōu)方式進行排布,降低料耗。常見的排料要求有兩種:一種是固定數(shù)量、固定規(guī)格的鋼板,要求切割出盡可能多的零件;另一種是鋼板數(shù)量不限定,板規(guī)為常見規(guī)格,而需求的零件數(shù)量是固定的,要求消耗的鋼板最少。

對于訂單式的鋼結(jié)構(gòu)項目生產(chǎn)來說,后一種排料要求更加符合實際情況,即利用若干規(guī)格和數(shù)量的鋼板,為指定尺寸、指定數(shù)量和指定紋理的零件下料,在滿足配套和切割便利的前提下,使板材的利用率最高,同時又使鋼板原料的需求最少。

1排料方法分析

在鋼結(jié)構(gòu)實際生產(chǎn)中矩形零件占一部分,還有一部分零件是不規(guī)則零件,其中對鋼板料耗影響最大的就是不規(guī)則零件,不同的組合次序、旋轉(zhuǎn)角度都可能導(dǎo)致不同的排料結(jié)果。鋼板排料的數(shù)學(xué)理論除了常用的遺傳算法外,啟發(fā)式包絡(luò)算法也是一種較為簡易的方法。

1.1 啟發(fā)式排料原理

啟發(fā)式方法是根據(jù)板件的輪廓特征先求取最小包絡(luò)矩形,再求出聚合矩形。通過對零件外輪廓多邊形進行操作,分別求得與多邊形平行或重合的最小矩形,找出其中的最小者即為零件最小包絡(luò)矩形;將原零件復(fù)制一個并旋轉(zhuǎn)180°;將復(fù)制件沿原零件的四周依次移動到若干個位置,再分別與原零件進行組合,每次組合均求一次最小包絡(luò)矩形,面積最小的矩形即為零件聚合體的最小包絡(luò)矩形。如果聚合后的聚合矩形的面積小于兩個零件的最小包絡(luò)矩形面積之和,則聚合成功;反之則自動放棄聚合。

1.2 啟發(fā)式排料流程

啟發(fā)式排料先要對待排料板件進行簡化預(yù)處理,將不規(guī)則的二維圖形簡化為二維矩形,即用板件的最小包絡(luò)矩形代替板件進行排料。

單個或多個不規(guī)則零件的組合找出其最小包絡(luò)矩形,然后化為矩形件的排料問題。

(1)單個零件的矩形替代。

采用窮舉法求取板件的最小矩形包絡(luò)。只有當(dāng)零件的包絡(luò)矩形與零件的外輪廓多邊形中的一條邊平行或重合時,此包絡(luò)矩形才有可能是最小包絡(luò)矩形。

求解包絡(luò)矩形的過程是:零件外輪廓的頂點連線形成封閉圖形(凸多邊形),然后以凸多邊形的每一邊假設(shè)與所求矩形中的一邊重合,根據(jù)頂點位置即可得出此時的包絡(luò)矩形,其中面積最小者為最佳包絡(luò)矩形。

(2)多個零件的矩形替代。

當(dāng)單個零件經(jīng)矩形替代后,若矩形面積較零件面積大的較多,即又較多的面積冗余。為了提高材料利用率,可將兩個合適的零件聚合在一起,再按單個零件的矩形替代方法求出其最小矩形包絡(luò)。一般情況下,兩個同類零件相對180°轉(zhuǎn)角聚合是較為理想的。

(3)冗余域最小原則。

單(多)個零件的矩形替代與零件邊界間的空白部分成為冗余域。

為了提高材料的利用率,進行矩形替代預(yù)處理時,要將適當(dāng)?shù)男×慵匦翁娲畛涞饺哂嘤蛑小?/p>

(4)排料優(yōu)化算法的描述。

假設(shè)母板編號為Bm,每塊矩形件編號為An。首先將矩形件按面積大小排序,面積大的在前,面積小的在后,母板的面積為S(Bm),將排序后的矩形件排到母板上,對某一個矩形件An,它總是被排到第1個能排下它的母板Bm上,也就是說,矩形件An被排到已排入的矩形件面積不超過S(Bm)-S(An)。

S(Bm)-C(Bk)-S(An)=min{S(Bm)-C(Bk)-S(An)|S(Bm)-C(Bm)≥S(An)}(k=1,2,3,…,m)

其中,C(Bk)為第k塊母板上排入的矩形件的總面積。

2注意問題

2.1 繪制排料圖的注意事項

為簡化排料圖的繪制,排料前應(yīng)先將零件分類,一般可分為以下三類。

(1)零件長邊大于鋼板短邊的一類。此類零件在鋼板上只有一種排法,對材料利用率影響較大,應(yīng)注意利用余料安排其他尺寸較小零件。

(2)零件兩邊均小于鋼板短邊一類。此類零件排料組合情況多樣,應(yīng)注意不同零件的搭配。

(3)零件尺寸較小,或某邊長與鋼板某邊長成倍比關(guān)系的一類。此類零件單一下料利用率高。

繪制排料圖時,應(yīng)先考慮第1類零件,其次搭配好第2類零件,最后將第3類零件作為余料的填充料。數(shù)量較大的第3類零件還應(yīng)繪制單一排料圖。

2.2 簡化模型的方法

在下料問題的模型中,每種零件對應(yīng)一個約束條件,當(dāng)一批下料任務(wù)中零件品種較多時,不盡會使排料工作復(fù)雜化,而且模型也相應(yīng)復(fù)雜,會使計算量急劇增加。此時可采用以下方法處理。

(1)對尺寸不大且數(shù)量較少的零件,在排料和建模時可暫不考慮,它們通?？稍谧罱K方案的余料中安排,或在取整修整階段一起解決。

(2)對數(shù)量相同或相近,且某邊長也相同或相近的兩種或多種零件,可組合成一“新零件”進行排料和建模。

(3)若經(jīng)上述處理后零件品種仍過多時,可將各零件適當(dāng)分組。對各組零件分別排料和建模,可將一個大的問題化為幾個較小的問題來求解。這不僅可大大減少運算量,還可簡化排料工作。

3結(jié)語

啟發(fā)式包絡(luò)算法對于數(shù)量不是很多、輪廓較為規(guī)則的零件效果較為明顯,但是對于輪廓不規(guī)則(尤其是凹多邊形)、數(shù)量較多的零件排料效果不是非常理想。遺傳式排料方法是對不規(guī)則零件排料的有益補充,但是對于零件較多的時候,排料同樣非常耗時,并且對計算機硬件要求較高。對一個鈑金CAD/CAM系統(tǒng)而言,如何將這兩種排料算法有效的結(jié)合起來,并盡可能在優(yōu)化排料方案基礎(chǔ)上提高排料過程自動化程度,這是鈑金CAD需要研究的新領(lǐng)域。

參考文獻

[1] 黃宜軍,施德恒,許啟富.鈑金CAD中一個較優(yōu)的排料算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2000,5(5):380～383.

[2] 張英杰.二維不規(guī)則零件自動排料的優(yōu)化算法[J].機械設(shè)計與研究,2009,10(5):79～81.