基于動態(tài)擇優(yōu)組合的板材切割下料算法

鞠云鵬 ,常德功

(青島科技大學a.自動化與電子工程學院;b.機電工程學院,山東 青島 266061)

隨著板式家具的批量生產,采取何種優(yōu)化的板 材下料方法以提高板材利用率、降低產品的定制成本,成為企業(yè)競爭的關鍵所在[1-4]。計算機輔助排樣方法能夠提高排板精度,將低人工費用,減少誤操作,提高板材切割效率[5]。將一批不同尺寸規(guī)格的板件排列在大的板材上并達到高的板材利用率是一個復雜問題,并且不確定能否在多項式時間內找到答案[6]。應用常規(guī)方法來解決這類多項式不確定性問題,所用時間達不到現(xiàn)實要求。對于生產規(guī)模較小的企業(yè),可以使用早期板材切割下料的一些方法[7-11]。但隨著板式家具的批量定制,很多企業(yè)的產量已達不到市場需求,同時板材切割利用率低的問題也開始暴露。針對低效率、低利用率問題,一些新的算法被先后提出。最下最左算法[12]首先被提出,之后在此基礎上出現(xiàn)了下臺階算法[13],后來又出現(xiàn)了最低水平線算法[14-15]以及近似算法[16]。以上幾種方法相對于傳統(tǒng)排樣方法具有明顯優(yōu)勢,但不能對所有矩形件進行全局搜索,因此,其具有一定局限性。隨著GA、SA、TS、AA、ANN 等智能算法的發(fā)展,出現(xiàn)了智能算法與常規(guī)算法相結合的優(yōu)化算法。文獻[17]將蟻群算法與啟發(fā)式算法相結合,來優(yōu)化板材切割下料。文獻[18]依據(jù)模擬退火局部搜索能力強、收斂速度慢和遺傳算法全局搜索能力強、收斂過早的特點,將二者進行有效結合。通過智能算法尋優(yōu),對于不確定性排板問題可以更大范圍的搜索有效解。對于數(shù)量較大、尺寸差異、規(guī)格不一的板件排樣,遺傳算法能夠在更大的范圍空間內進行尋優(yōu),但搜索有效解的時間會變長[19]。相對于最低水平線算法,最低水平線搜索算法在一定范圍內進行了尋優(yōu),但需對換兩個矩形件的位置,造成后面排板過程中小件缺失。本研究在最低水平線搜索算法基礎上,首先,將待排板件按面積大小進行排列。其次,在最低水平線排放矩形件時,按照矩形件的長度或寬度所占據(jù)最低水平線的比例來選取。若組合占據(jù)的比例較大,則優(yōu)先選取矩形件組合進行排放,并且組合中矩形件不能與其它待排矩形件交換順序。通過對矩形板件進行排樣,此優(yōu)化組合算法能夠有效提高板材的利用率。

1 數(shù)學模型

整塊矩形大板的長、寬分別為L、W,為減少切割過程所產生的余料,應盡量使所排放板件之間的空隙減到最小。設待排板件的規(guī)格數(shù)為k,第i 種板件的個數(shù)為ni,寬、長分別為wi,li。大板數(shù)量充足,則待切割小板件的數(shù)量可表示為

板件排放過程中可按長邊進行排放,也可按短邊進行排放,這需根據(jù)板件有無紋理加工要求進行。第一塊板件應首先放置在大板的左下角,并且后面板件要排放均勻。設大板左下角為基準點,第i 塊板件左上角的坐標表示為(x1i,y1i),其右下角的坐標表示為(x2i,y2i)。根據(jù)板件按長邊或短邊的排放形式,其對角線上兩點的坐標可表示為

ri＝0、1,當板件按長邊進行排放時,ri取0。當板件按短邊進行排放時,ri取1。建立板件左上角坐標與右下角坐標的關系:

為提高板材的利用率,板材上板件間的距離應盡量小,但板件排放時不能重疊、不能壓邊。取任意兩個板件Rt、Rs,為滿足排放要求,需滿足坐標關系。根據(jù)式(3)可得

板件在排放時,除滿足板件間不能重疊、壓邊外,還應保證板件不能排到大板邊界之外,即板件右下角橫坐標小于板件長度,板件左上角縱坐標小于板件寬度。根據(jù)以上約束可得

式(5)中u 為單位階躍函數(shù)。為使板材利用率最高,應滿足式(6)目標函數(shù)。

一般Sj為定值,代表一批板材中大板的面積;Sm為一次生產中所用最后一塊大板的面積。

2 優(yōu)化組合算法分析

本工作以啟發(fā)式定位算法為基礎,并對數(shù)據(jù)庫中待排件逐一進行面積計算,然后按面積大小進行排序。采用動態(tài)擇優(yōu)組合算法對其進行排放。假設最低水平線長度為l,板件的排放順序如下。

1)選擇待切大板的底邊作為最低水平輪廓線,使其成為集合元素。

2)從待排矩形件中搜索矩形件或矩形件組合,搜索原則按照矩形件或矩形件組合占據(jù)最低水平線的比例來確定。若存在多個組合,則按照面積大小優(yōu)先選取面積較大的組合。

3)在所建立的集合中查找最低水平線,并比較組合件底邊長度與l:①如果組合件底邊長度較短,則組合件可放置在該水平線。如果組合件底邊長度大于l,但寬度小于l,且板件沒有紋理切割要求,那么此組合件經旋轉后可放置在該水平線。如果該組合件的長度不等于其寬度,并且長、寬均小于l,且板件沒有紋理切割要求,則將該組合件按長邊放置在該水平線。②否則在待排放的矩形件序列中,將其它組合件的長、寬與l進行比較,當搜索到合適的組合件時,不互換當前不能排放的矩形件與所搜索到的組合件的位置,而是只將搜索到的組合件放置在當前最低水平線。如果組合件的長、寬均大于l,則最低水平線需調整至一定高度,此高度應與該水平線相鄰的其它最低輪廓線的高度保持一致,同時最低輪廓線集合也需進行更新。

4)重復執(zhí)行程序第2)、3)步,一塊大板被切割完成后,需用另一塊大板,此時再從程序第(1)步開始執(zhí)行。本工作將此算法稱為動態(tài)擇優(yōu)組合算法。

3 比較分析

3.1 下料數(shù)據(jù)

為更好的驗證優(yōu)化組合算法對排板的有效性,本文以工廠實際提供的下料板件數(shù)據(jù)為實驗數(shù)據(jù)。板材采用常用的2440×1220×18 規(guī)格,單位為mm。下料板件的尺度及紋理要求如表1所示。

表1 板件明細Table 1 Details of the board

3.2 排板算法比較與分析

3.2.1 最下最左算法

圖1為最下最左算法排版。對板件{＋1,＋2,＋3,＋4}進行順序排放,數(shù)字前的“＋”表示板件不能旋轉。根據(jù)最下最左規(guī)則,排放完板件1、2、3后,板件1、2與板件3之間產生了大的空隙(圖1(a))。再繼續(xù)對板件4進行排放,板件4排放完成之后,仍然沒有彌補前面留下的空隙(圖1(b))。4個板件較為理想的排放形式如圖1(c)所示,其板件的排放較為緊湊。

圖1 最下最左算法排板Fig.1 Bottom left algorithm layout

3.2.2 下臺階算法

對板件{＋1,＋2,＋3,＋4}進行順序排放,此節(jié)中的板件區(qū)別于圖1中的板件,數(shù)字前的“＋”表示板件不能旋轉。將最下最左算法的排板與下臺階算法的排板進行比較,見圖2。對前3個板件的排放,二者均沒有明顯優(yōu)勢(圖2(a))。對第4個板件進行排放時,出現(xiàn)了差距,最下最左算法沒有將板件放置在最低輪廓線上,造成整體排放高度較高,而下臺階算法整體排板較為均勻,板件排列緊湊。

圖2 BL算法與下臺階算法排板對照Fig.2 Comparisons between BL algorithm and lower step algorithm

3.2.3 最低水平線算法

最近水平線算法見圖3。對板件{＋1,－2,＋3,＋4}進行順序排放,此節(jié)中的板件區(qū)別于前面的板件,數(shù)字前的“＋”表示板件不能旋轉,“－”表示板件旋轉90°后排放。圖3中(a)～(f)是根據(jù)最低水平線法對4個板件的排放過程。

圖3 最低水平線算法排板Fig.3 Lowest horizontal line algorithm layout

分別采用最低水平線法和下臺階算法對6個板件的排板效果進行比較見圖4。對前5個板件的排放,二者均沒有明顯優(yōu)勢(圖4(a))。對第6個板件進行排放時,二者出現(xiàn)了差距。最低水平線法將板件6安置在了最低輪廓線處,下臺階算法將板件6安置在了比最低輪廓線高的板件4之上,造成下臺階算法的整體排板高度較高,排板不均勻,而圖4(b)的排板效果較為理想。

圖4 最低水平線法與下臺階算法排板對照Fig.4 Comparisons between the lowest horizontal line method and the lower step algorithm

3.2.4 最低水平線搜索算法

對圖3中4個板件進行排放,采用最低水平線法對板件3排放時,由于板件3長度大于當前最低水平線,因此,板件3不能放在最低水平線gd,此時需更新最低水平線,新的最低水平線變更為ab,然后對待排板件進行排放。根據(jù)最低水平線搜索算法規(guī)則,當板件3不能排放在gd時,可從待排件中選出適合排放的板件4,這樣就避免了最低水平線以上部分排放空間的浪費。將最低水平線搜索算法與最低水平線法進行比較見圖5,圖5(b)較圖3(f)的整體排板更低、更均勻。

圖5 基于最低水平線搜索算法排板(對照圖3)Fig.5 Layout based on the lowest horizontal search algorithm(comparative Fig.3)

3.2.5 動態(tài)擇優(yōu)組合算法

對板件{－1,＋2,－3,＋4,－5,＋6,－7}進行順序排放,此節(jié)中的板件區(qū)別于前面的板件,數(shù)字前的“＋”表示板件不能旋轉,“－”表示板件旋轉90°后排放。根據(jù)最低水平線搜索算法規(guī)則對7個板件進行排放見圖6,當?shù)?個板件進行排放時,出現(xiàn)了板件4長度大于當前最低水平線的情況,為此采用搜索算法,選擇了合適的板件7,并將合適板件與不合適板件的位置進行了交換。再對板件5、6、4進行排放,造成圖6(c)的整體排板高度較高,板件2、3、4、6間留有大的空隙。區(qū)別于最低水平線搜索算法,根據(jù)動態(tài)擇優(yōu)組合算法規(guī)則對7個板件進行排放見圖7,在找到合適的板件7之后,將其安置在當前最低水平線處。然后再對板件4、5、6進行排放,效果如圖7(b),通過圖得知,其排板均勻、整體高度低,較圖6(c),其利用率更高。

圖6 基于最低水平線搜索算法排板(對照圖7)Fig.6 Layout based on the lowest horizontal search algorithm(comparative Fig.7)

圖7 動態(tài)擇優(yōu)組合算法排板Fig.7 Dynamic optimum combination algorithm layout

為驗證動態(tài)擇優(yōu)組合算法的排板效果,選用表1中實際切割板件作為優(yōu)化組合排列對象。同時,采用最低水平線搜索算法對實際切割板件進行排列(圖8),與動態(tài)擇優(yōu)組合算法(圖9)形成對照。表2為板材利用率表。

表2 板材利用率Table 2 Utilization rate of raw materials

圖8 基于最低水平線搜索算法排板(對照圖9)Fig.8 Layout based on the lowest horizontal search algorithm(comparative Fig.9)

圖9 基于動態(tài)擇優(yōu)組合的矩形件排板Fig.9 Rectangular parts layout based on dynamic optimal combination

分別采用以上兩種方法對表1中不同規(guī)格的板件進行排板,通過圖8、圖9得知,采用動態(tài)擇優(yōu)組合算法比最低水平線搜索算法少用1張大板,采用優(yōu)化組合方法能夠明顯提高板材的利用率。表2統(tǒng)計了優(yōu)化組合方法下6張大板各自的利用率。

4 結 語

對于板材切割下料問題,最下最左算法、下臺階算法、最低水平線算法、最低水平線搜索算法具有一定的優(yōu)勢,但以上算法的適用范圍較窄,為此采用基于動態(tài)擇優(yōu)組合的板材切割下料算法。通過實驗板件所用大板的張數(shù)可以證明基于動態(tài)擇優(yōu)組合的板材切割下料算法更能提高板材的利用率。