姜永亮， 周　俊

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

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

姜永亮， 周俊

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

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

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

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

1　相關概念

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

圖1　排樣中的條帶

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

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

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

圖3　板材分成5個子段

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

(5) 兩塊式排樣。對于沿長度方向剪切的子段沿豎直方向將其分成左右兩塊，如圖4所示，可在塊內使用同質條帶進行排樣。對于塊S1使用X向條帶，對于塊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問題描述

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

2.2同質條帶求解

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

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

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

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

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

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

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

VXY可用式(7)求解：

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

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

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

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

3　應用實例

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

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

表1　矩形零件信息

表2　板材利用率

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

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

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

表3　板材平均利用率

4　結　論

基于最優(yōu)子段的矩形優(yōu)化排樣問題的求解主要集中在：同質條帶求解、最優(yōu)子段排樣方式求解和長板分段方式求解。對算法中3個步驟的時間復雜性分析可知，算法中同質條帶求解時間復雜度為O(1)；最優(yōu)子段排樣方式求解的時間復雜度為O(m×LB×W)；長板最優(yōu)分段方式求解的時間復雜度為O(LB×L)。在時間復雜度方面本文算法與三塊式排樣算法基本相當，即系統(tǒng)計算速度與三塊式算法基本相當，在計算時間方面本文算法能夠滿足企業(yè)實際需求。企業(yè)的實際應用證明，基于最優(yōu)子段的矩形優(yōu)化排樣算法，在切割工藝相對簡單的前提下，在優(yōu)化能力方面明顯優(yōu)于兩階段算法和三階段算法。文獻實例驗證表明，在沒有剪床刀刃長度限制條件下本文算法在優(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]. 計算機學報, 2006, 29(5): 734-739.

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

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

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

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

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

[8] 姜永亮, 楊志強, 張誠一. 基于兩階段的分段單一矩形優(yōu)化排樣[J]. 計算機應用, 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

國家自然科學基金項目(71361008)；海南省重點科技基金項目(ZDXM 20130080)；海南省自然科學基金項目(612136)

姜永亮(1980–)，男，河南漯河人，副教授，碩士。主要研究方向為計算機排樣技術。E-mail：yongliangjiang@126.com

周俊(1974–)，男，海南?？谌耍呒壒こ處?，學士。主要研究方向為計算機排樣技術。E-mail：zhjun@hainnu.edu.cn