鞠云鵬 ,常德功

(青島科技大學(xué)a.自動(dòng)化與電子工程學(xué)院;b.機(jī)電工程學(xué)院,山東 青島 266061)

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

1 數(shù)學(xué)模型

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

板件排放過(guò)程中可按長(zhǎng)邊進(jìn)行排放,也可按短邊進(jìn)行排放,這需根據(jù)板件有無(wú)紋理加工要求進(jìn)行。第一塊板件應(yīng)首先放置在大板的左下角,并且后面板件要排放均勻。設(shè)大板左下角為基準(zhǔn)點(diǎn),第i 塊板件左上角的坐標(biāo)表示為(x1i,y1i),其右下角的坐標(biāo)表示為(x2i,y2i)。根據(jù)板件按長(zhǎng)邊或短邊的排放形式,其對(duì)角線(xiàn)上兩點(diǎn)的坐標(biāo)可表示為

ri＝0、1,當(dāng)板件按長(zhǎng)邊進(jìn)行排放時(shí),ri取0。當(dāng)板件按短邊進(jìn)行排放時(shí),ri取1。建立板件左上角坐標(biāo)與右下角坐標(biāo)的關(guān)系:

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

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

式(5)中u 為單位階躍函數(shù)。為使板材利用率最高,應(yīng)滿(mǎn)足式(6)目標(biāo)函數(shù)。

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

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

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

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

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

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

4)重復(fù)執(zhí)行程序第2)、3)步,一塊大板被切割完成后,需用另一塊大板,此時(shí)再?gòu)某绦虻?1)步開(kāi)始執(zhí)行。本工作將此算法稱(chēng)為動(dòng)態(tài)擇優(yōu)組合算法。

3 比較分析

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

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

表1 板件明細(xì)Table 1 Details of the board

3.2 排板算法比較與分析

3.2.1 最下最左算法

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

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

3.2.2 下臺(tái)階算法

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

圖2 BL算法與下臺(tái)階算法排板對(duì)照Fig.2 Comparisons between BL algorithm and lower step algorithm

3.2.3 最低水平線(xiàn)算法

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

圖3 最低水平線(xiàn)算法排板Fig.3 Lowest horizontal line algorithm layout

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

圖4 最低水平線(xiàn)法與下臺(tái)階算法排板對(duì)照Fig.4 Comparisons between the lowest horizontal line method and the lower step algorithm

3.2.4 最低水平線(xiàn)搜索算法

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

圖5 基于最低水平線(xiàn)搜索算法排板(對(duì)照?qǐng)D3)Fig.5 Layout based on the lowest horizontal search algorithm(comparative Fig.3)

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

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

圖6 基于最低水平線(xiàn)搜索算法排板(對(duì)照?qǐng)D7)Fig.6 Layout based on the lowest horizontal search algorithm(comparative Fig.7)

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

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

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

圖8 基于最低水平線(xiàn)搜索算法排板(對(duì)照?qǐng)D9)Fig.8 Layout based on the lowest horizontal search algorithm(comparative Fig.9)

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

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

4 結(jié) 語(yǔ)

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