姜永亮， 周　俊

(海南師范大學(xué)校園網(wǎng)絡(luò)中心，海南 ?？?571158)

基于最優(yōu)子段的矩形優(yōu)化排樣

姜永亮， 周俊

(海南師范大學(xué)校園網(wǎng)絡(luò)中心，海南 ?？?571158)

為有效解決企業(yè)實(shí)際生產(chǎn)中的矩形優(yōu)化排樣問題，對(duì)矩形優(yōu)化排樣算法進(jìn)行研究，給出基于最優(yōu)子段的矩形優(yōu)化排樣算法，有效解決了企業(yè)實(shí)際生產(chǎn)中的長(zhǎng)板矩形優(yōu)化排樣問題。首先基于動(dòng)態(tài)規(guī)劃算法求出所有小于剪床刀刃長(zhǎng)度的最優(yōu)子段的最佳排樣方式，然后以所求的最優(yōu)子段作為可用子段在長(zhǎng)板上進(jìn)行優(yōu)化排樣，并將矩形優(yōu)化排樣問題轉(zhuǎn)化為完全背包問題。最后基于分支定界技術(shù)的整數(shù)規(guī)劃算法對(duì)其進(jìn)行求解。企業(yè)應(yīng)用實(shí)例表明該算法在解決長(zhǎng)板矩形優(yōu)化問題方面優(yōu)于其他算法。

矩形優(yōu)化排樣；最優(yōu)子段；動(dòng)態(tài)規(guī)劃算法；分支定界技術(shù)

所謂的矩形優(yōu)化排樣問題就是指將需要的多規(guī)格、多類型零件排放在給定尺寸的板材上，使板材的利用率最大，該問題是屬于NP完備問題[1-2]。在機(jī)械制造、家具、玻璃加工等企業(yè)經(jīng)常遇到排樣問題：如在規(guī)格為 L×W的板材上進(jìn)行剪切排樣，要求剪切出的矩形毛坯的種類最多為m種，每種毛坯在板材上出現(xiàn)的次數(shù)不限，排樣的目標(biāo)是使板材中所含毛坯的總價(jià)值最大，該類排樣稱為無約束排樣[3]。對(duì)于此類問題，國(guó)內(nèi)外學(xué)者均進(jìn)行了相關(guān)研究并取得了一定的成果。文獻(xiàn)[4]提出了生成矩形毛坯最優(yōu)T形排樣方式的遞歸算法；文獻(xiàn)[5]提出基于勻質(zhì)條帶的矩形件最優(yōu)三塊布局算法；文獻(xiàn)[6]提出基于最優(yōu)兩段式排樣算法等。對(duì)于剪床刀刃不大于板材的最大長(zhǎng)度的排樣問題，上述算法可以進(jìn)行有效解決，當(dāng)遇到剪床刀刃長(zhǎng)度小于板材長(zhǎng)度的長(zhǎng)板排樣問題時(shí)，上述算法無法解決。對(duì)于長(zhǎng)板矩形優(yōu)化排樣問題文獻(xiàn)[7]提出長(zhǎng)板單一尺寸矩形毛坯定長(zhǎng)分割優(yōu)化排樣算法；文獻(xiàn)[8]提出基于兩階段的分段單一矩形優(yōu)化排樣算法，上述算法僅僅有效解決了單一矩形的長(zhǎng)板優(yōu)化排樣問題。對(duì)于多規(guī)格矩形套排的長(zhǎng)板矩形優(yōu)化排樣問題，目前企業(yè)常用的算法是基于文獻(xiàn)[9]提出的兩階段或三階段矩形優(yōu)化排樣算法，該算法雖然切割工藝簡(jiǎn)單，但是在很多情況下原材料利用率不高。在資源日益短缺的今天，節(jié)約生產(chǎn)成本也是企業(yè)提高經(jīng)濟(jì)效益的有效方式?？紤]到企業(yè)實(shí)際生產(chǎn)中切割工藝及原材料利用率對(duì)企業(yè)經(jīng)濟(jì)效益2個(gè)因素的影響，這里提出基于最優(yōu)子段的矩形優(yōu)化排樣算法，并將其應(yīng)用于系統(tǒng)開發(fā)，有效解決了企業(yè)實(shí)際生產(chǎn)中的長(zhǎng)板矩形優(yōu)化排樣問題。

1　相關(guān)概念

(1) 條帶。若干個(gè)矩形零件連續(xù)地按照水平或豎直方向排放在一起構(gòu)成一個(gè)條帶，如圖1所示，其中圖1(a)、(b)為X向條帶，圖1(c)、(d)為Y向條帶。

圖1　排樣中的條帶

(2) 同質(zhì)條帶。對(duì)于給定尺寸的條帶(x×y，其中，x為條帶長(zhǎng)度，y為寬度)，若條帶中只含一種矩形零件，該條帶稱為同質(zhì)條帶如圖 2(a)所示，若條帶中含多種矩形零件，則稱為一般條帶如圖2(b)所示。

圖2　最優(yōu)條帶與一般條帶

(3) 子段。假定實(shí)際生產(chǎn)中所用板材規(guī)格為L(zhǎng)×W，在排樣過程中將板材分成若干個(gè)子段，要求各子段長(zhǎng)度均小于剪床刀刃長(zhǎng)度LB，圖3為板材分成5個(gè)子段。

圖3　板材分成5個(gè)子段

(4) 最優(yōu)子段。假定在排樣中按照某種排樣方式對(duì)各子段進(jìn)行優(yōu)化排樣，得到最優(yōu)排樣方式下價(jià)值為V的子段有S1, S2,…,Sn，且在長(zhǎng)度方面，則稱子段S1是價(jià)值為V的最優(yōu)子段。

(5) 兩塊式排樣。對(duì)于沿長(zhǎng)度方向剪切的子段沿豎直方向?qū)⑵浞殖勺笥覂蓧K，如圖4所示，可在塊內(nèi)使用同質(zhì)條帶進(jìn)行排樣。對(duì)于塊S1使用X向條帶，對(duì)于塊S2可以使用X向條帶也可以使用Y向條帶，若塊S2使用X向條帶則該子段的排樣方式稱為FXX排樣方式，如圖4(a)所示，若塊S2使用Y向條帶則該子段的排樣方式稱為 FXY排樣方式，如圖4(b)所示。鑒于上述假定，最優(yōu)子段其最優(yōu)排樣方式可以使用求解。

圖4　兩塊式排樣

2　基于最優(yōu)子段的矩形優(yōu)化排樣算法

2.1問題描述

假定某一排樣任務(wù)中，所用板材長(zhǎng)度為L(zhǎng)，寬度為W，剪床刀刃長(zhǎng)度為L(zhǎng)B，待排矩形零件的規(guī)格為：，矩形的價(jià)值為c1, c2,… ,cm(這里取矩形零件的面積為其價(jià)值)。受剪床刀刃長(zhǎng)度的限制，企業(yè)在實(shí)際的生產(chǎn)下料過程中必須先將板材剪切成若干個(gè)子段，然后在各子段上進(jìn)行優(yōu)化下料。優(yōu)化排樣的求解正好與優(yōu)化下料過程的求解相反。優(yōu)化排樣的求解過程為：首先求出各子段的最優(yōu)排樣方式，然后使用各子段在長(zhǎng)板上進(jìn)行優(yōu)化布局?？紤]到實(shí)際生產(chǎn)中切割工藝對(duì)生產(chǎn)效率的影響問題，需對(duì)各子段采用基于同質(zhì)條帶的兩塊式排樣方式。鑒于兩塊式排樣是以同質(zhì)條帶為單位進(jìn)行排樣的，在對(duì)子段進(jìn)行兩塊式排樣之前需求出各同質(zhì)條帶的價(jià)值。這樣基于最優(yōu)子段的矩形優(yōu)化排樣需要求解如下3個(gè)問題：①同質(zhì)條帶求解；②最優(yōu)子段排樣方式求解；③板材最優(yōu)分段求解。

2.2同質(zhì)條帶求解

規(guī)格為x×wi的X向條帶其價(jià)值可用式(1)求解：

規(guī)格為wi×y 的Y向條帶其價(jià)值可用式(2)求解：

2.3最優(yōu)子段排樣方式求解

規(guī)格為x×W的子段，基于同質(zhì)條帶的兩塊式排樣方式的最優(yōu)價(jià)值可用式(3)求解：

式(3)中的VXX為兩塊均使用X向條帶進(jìn)行排樣的最優(yōu)價(jià)值，VXY為一塊使用X向條帶且另一塊使用Y向條帶進(jìn)行排樣的最優(yōu)價(jià)值。對(duì)于長(zhǎng)度為x寬度為k的塊，如果基于X向條帶進(jìn)行排樣其價(jià)值可用式(4)求解：

如果基于 Y向條帶進(jìn)行排樣其價(jià)值可用式(5)求解：

式(4)、(5)中的 Z均代表的是非負(fù)整數(shù)集合，int()為取整函數(shù)?；谝陨厦枋觯瑢?duì)于式(3)中的VXX可用式(6)求解：

VXY可用式(7)求解：

完成式(6)、(7)求解之后，根據(jù)式(3)即可求出規(guī)格為x×W的子段，基于同質(zhì)條帶的兩塊式排樣方式的最優(yōu)價(jià)值Vx。根據(jù)式(8)：

求出所有不大于剪床刀刃長(zhǎng)度子段的最優(yōu)排樣價(jià)值V1, V2,…,VL及最優(yōu)排樣方式。在 V1, V2,…,VLBB中若有，則長(zhǎng)度為k的子段價(jià)值稱為Vk的最優(yōu)子段，按上述規(guī)則求出所有小于等于剪床刀刃長(zhǎng)度最優(yōu)子段的價(jià)值、長(zhǎng)度及最優(yōu)排樣方案，即完成了最優(yōu)子段最優(yōu)排樣方式的求解。式(4)、(5)從數(shù)學(xué)模型上分析均屬于背包問題，考慮到動(dòng)態(tài)規(guī)劃算法具有存儲(chǔ)記憶功能，這里使用動(dòng)態(tài)規(guī)劃算法對(duì)其進(jìn)行求解。

2.4板材最優(yōu)分段求解

其中，N1,N2,… ,Nn1為最優(yōu)子段在板材上出現(xiàn)的次數(shù)。對(duì)于式(9)使用基于分支定界的整數(shù)規(guī)劃算法對(duì)其進(jìn)行求解，求出板材的最優(yōu)分段，進(jìn)而求出長(zhǎng)板矩形優(yōu)化樣的最終排樣結(jié)果。

3　應(yīng)用實(shí)例

為驗(yàn)證算法的有效性，這里基于 C#語言開發(fā)一矩形優(yōu)化排樣系統(tǒng)，系統(tǒng)對(duì)AutoCAD進(jìn)行了二次開發(fā)，所有排樣結(jié)果以CAD格式輸出。配置CPU主頻2.10，1 G內(nèi)存即可運(yùn)行本系統(tǒng)。

實(shí)例 1. 國(guó)內(nèi)某拖車生產(chǎn)企業(yè)使用本系統(tǒng)對(duì)長(zhǎng)板進(jìn)行優(yōu)化矩形下料。零件信息見表1，板材規(guī)格為6000 mm ×1810 mm，企業(yè)現(xiàn)有剪床刀刃長(zhǎng)度為2 010 mm。將上述信息輸入本系統(tǒng)進(jìn)行優(yōu)化排樣得到板材利用率為99.68%，使用兩階段算法和三階段算法[9]得到板材利用率分別為82.95%和91.27%，3種算法的原材料利用率如表2所示，本文算法原材料利用率比兩階段算法提高了 16.73%，比三階段算法提高了8.41%，使用本文算法可將板材分成4個(gè)最優(yōu)子段，其中長(zhǎng)度為1 824的子板重復(fù)使用了3次，如圖5(a)所示，長(zhǎng)度為526的子板使用1次，其最優(yōu)排樣方式如圖5(b)所示，整張板材的最優(yōu)排樣方式如圖6所示，從排樣圖可看出使用本文算法在切割工藝上與三階段算法切割工藝基本相當(dāng)。企業(yè)實(shí)際生產(chǎn)應(yīng)用表明，在解決長(zhǎng)板矩形優(yōu)化排樣問題方面本文算法明顯優(yōu)于兩階段算法和三階段算法。

表1　矩形零件信息

表2　板材利用率

實(shí)例 2. 取歐洲切割與裝箱特別興趣組織官方網(wǎng)站http://www.fe.up.pt/esicup/上的RecPub_G4.zip 中50組零件(每組包括30類零件)，作為待排零件，使用規(guī)格為2105 mm×1655 mm的板材，排樣過程中不受剪床刀刃長(zhǎng)度限制。使用本文算法和文獻(xiàn)[4]T型算法、文獻(xiàn)[5]三塊式算法、文獻(xiàn)[9]兩階段算法、文獻(xiàn)[10]三階段算法分別進(jìn)行優(yōu)化排樣。各種算法的板材平均利用率如表3所示，在原材料利用率達(dá)到98%以上的情況下，本文算法在原材料利用率上比其他算法仍然有所提高。

圖5　最優(yōu)子段排樣方式

圖6　最優(yōu)排樣方式

表3　板材平均利用率

4　結(jié)　論

基于最優(yōu)子段的矩形優(yōu)化排樣問題的求解主要集中在：同質(zhì)條帶求解、最優(yōu)子段排樣方式求解和長(zhǎng)板分段方式求解。對(duì)算法中3個(gè)步驟的時(shí)間復(fù)雜性分析可知，算法中同質(zhì)條帶求解時(shí)間復(fù)雜度為O(1)；最優(yōu)子段排樣方式求解的時(shí)間復(fù)雜度為O(m×LB×W)；長(zhǎng)板最優(yōu)分段方式求解的時(shí)間復(fù)雜度為O(LB×L)。在時(shí)間復(fù)雜度方面本文算法與三塊式排樣算法基本相當(dāng)，即系統(tǒng)計(jì)算速度與三塊式算法基本相當(dāng)，在計(jì)算時(shí)間方面本文算法能夠滿足企業(yè)實(shí)際需求。企業(yè)的實(shí)際應(yīng)用證明，基于最優(yōu)子段的矩形優(yōu)化排樣算法，在切割工藝相對(duì)簡(jiǎn)單的前提下，在優(yōu)化能力方面明顯優(yōu)于兩階段算法和三階段算法。文獻(xiàn)實(shí)例驗(yàn)證表明，在沒有剪床刀刃長(zhǎng)度限制條件下本文算法在優(yōu)化能力方面要優(yōu)于 T型算法、三塊式算法、兩階段、三階段等算法。

[1] Gilmore P C, Gomory R E. Multistage cutting stock problem of two and more dimentions [J]. Operations Research, 1965, 13(1): 94-120.

[2] 黃文奇, 劉景發(fā). 基于歐氏距離的矩形Packing問題的確定性啟發(fā)式求解算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2006, 29(5): 734-739.

[3] 崔耀東, 黃健民, 張顯全. 矩形毛料無約束二維剪切排樣的遞歸算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2006, 18(7): 948-951.

[4] 崔耀東. 生成矩形毛坯最優(yōu)T形排樣方式的遞歸算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2006, 18(1): 125- 127.

[5] 潘衛(wèi)平, 陳秋蓮, 崔耀東, 等. 基于勻質(zhì)條帶的矩形件最優(yōu)三塊布局算法[J]. 圖學(xué)學(xué)報(bào), 2015, 36(1): 7-11.

[6] 崔耀東, 季君, 曾窕俊. 生成矩形毛坯最優(yōu)兩段排樣方式的遞歸算法[J]. 南京航空航天大學(xué)學(xué)報(bào), 2006, 38(1): 111-114.

[7] 崔耀東. 長(zhǎng)板單一尺寸矩形毛坯定長(zhǎng)分割優(yōu)化排樣[J].計(jì)算機(jī)工程, 2004, 30(7): 178-180.

[8] 姜永亮, 楊志強(qiáng), 張誠一. 基于兩階段的分段單一矩形優(yōu)化排樣[J]. 計(jì)算機(jī)應(yīng)用, 2011, 31(6): 1689-1691.

[9] Hifi M. Exact algorithms for large scale unconstrained two and three staged cutting problems [J]. Computational Optimization and Applications, 2001, 18(1): 63-88.

[10] Silva E, Alvelosa F, Valério de Carvalho J M. An integer programming model for two-and three-stage two-dimensional cutting stock problems [J]. European Journal of Operational Research, 2010, 205(3): 699-708.

Rectangular Optimal Layout Based on Best Sub Segments

Jiang Yongliang,Zhou Jun

(Campus Network Center, Hainan Normal University, Haikou Hainan 571158, China)

To effectively solve the long board rectangular optimal layout problems which is often encountered in the actual production of enterprises, rectangular optimal layout algorithms were studied and a rectangular optimal layout algorithm based on the best sub segments was proposed, which effectively solve long board rectangular optimal layout problems in actual production. Firstly based on dynamic programming algorithm all sub optimal layout modes were solved which is less than the shear blade length. Secondly with the best sub segments as layout parts, these segments were optimized on the long board and the rectangular optimal layout problems were converted to knapsack problems completely. Finally the integer programm ing algorithm based on branch and bound technique was used to solve the long board rectangular optimal layout problems. Enterprise’s practical application showed that the algorithm in solving the long board rectangular optimization problems is better than other algorithms.

rectangular optimal layout; best sub segment; dynamic programming algorithm; branch and bound technique

TP 391.7

10.11996/JG.j.2095-302X.2016020280

A

2095-302X(2016)02-0280-05

2015-07-29；定稿日期：2015-11-01

國(guó)家自然科學(xué)基金項(xiàng)目(71361008)；海南省重點(diǎn)科技基金項(xiàng)目(ZDXM 20130080)；海南省自然科學(xué)基金項(xiàng)目(612136)

姜永亮(1980–)，男，河南漯河人，副教授，碩士。主要研究方向?yàn)橛?jì)算機(jī)排樣技術(shù)。E-mail：yongliangjiang@126.com

周俊(1974–)，男，海南?？谌耍呒?jí)工程師，學(xué)士。主要研究方向?yàn)橛?jì)算機(jī)排樣技術(shù)。E-mail：zhjun@hainnu.edu.cn