曾兆敏， 王繼紅， 管衛(wèi)利

(1. 四川信息職業(yè)技術(shù)學(xué)院，四川 廣元 628017；2. 鄭州科技學(xué)院電氣工程學(xué)院，河南 鄭州 450064；3. 南寧學(xué)院信息工程學(xué)院，廣西 南寧 530200)

二維板材切割下料問題的一種確定性算法

曾兆敏1， 王繼紅2， 管衛(wèi)利3

(1. 四川信息職業(yè)技術(shù)學(xué)院，四川 廣元 628017；2. 鄭州科技學(xué)院電氣工程學(xué)院，河南 鄭州 450064；3. 南寧學(xué)院信息工程學(xué)院，廣西 南寧 530200)

研究二維板材切割下料問題，即使用最少板材切割出一定數(shù)量的若干種矩形件。提出一種結(jié)合背包算法和線性規(guī)劃算法的確定性求解算法。首先構(gòu)造生成均勻條帶四塊排樣方式的背包算法；然后采用線性規(guī)劃算法迭代調(diào)用上述背包算法，每次均根據(jù)生產(chǎn)成本最小原則改善目標(biāo)函數(shù)并修正各種矩形件的當(dāng)前價值，按照當(dāng)前價值生成新的排樣方式；最后選擇最優(yōu)的一組排樣方式組成排樣方案。采用基準(zhǔn)測題，將該算法與著名的T型下料算法進(jìn)行比較，實驗結(jié)果表明，該算法比T型下料算法更能節(jié)省板材，計算時間能夠滿足實際應(yīng)用需要。

二維切割；矩形件下料；背包算法；線性規(guī)劃算法

板材二維切割下料(two dimensional cutting stock，TCS)問題是指用板材切割出一定數(shù)量的若干種矩形件，在每種矩形件的需求量得到滿足的條件下使得所切割的板材張數(shù)最少。TCS問題是屬于NP難的組合優(yōu)化問題，在機(jī)械制造業(yè)領(lǐng)域有廣泛的應(yīng)用[1-3]。TCS問題的解稱為排樣方案，由一組排樣方式組成，并且指出按照每種排樣方式所切割的板材張數(shù)。排樣方式是指單張板材上矩形件的排列方式。

目前文獻(xiàn)中對排樣方式生成算法研究較多，Hifi等[4]運(yùn)用束搜索原理提出了兩階段排樣方式的生成算法。Cui和Huang[5]提出了T型、兩段[6]排樣方式的啟發(fā)式生成算法。Cui[7]及潘衛(wèi)平等[8]分別提出了三階段排樣方式、勻質(zhì)條帶三塊排樣方式的背包算法。以上算法，只能解決單張板材上的矩形件無約束排樣問題，無法解決下料問題。陳學(xué)松等[9]采用遺傳模擬退火算法對下料問題進(jìn)行了求解，但該算法生成的排樣方案板材切割工藝復(fù)雜，且材料利用率較低。崔耀東[10]及Cui[11]提出了T型排樣方式的遞歸算法，并將該算法和線性規(guī)劃相結(jié)合構(gòu)造了下料算法，使下料問題得到了較好地解決。本文提出一種新的均勻條帶四塊(four block uniform strips, FBUS)排樣方式，首先構(gòu)造生成該種排樣方式的背包算法；然后采用線性規(guī)劃算法迭代調(diào)用該背包算法求解排樣方案。實驗結(jié)果表明，本文算法能夠有效地解決板材TCS問題。

1 基本概念

1.1 問題定義

TCS問題[1]：用規(guī)格為L(長)×W(寬)的板材切割出一定數(shù)量的m種矩形件，其中第i種矩形件的規(guī)格為 li×wi，個數(shù)為 bi；優(yōu)化目標(biāo)是用盡量少的板材切割出所需的全部矩形件。

板材二維無約束排樣(two dimensional unconstrained packing, TUP)問題：將規(guī)格為L×W的板材切割成m種矩形件，其中第i種矩形件的規(guī)格為 li×wi，價值為 vi，對每種矩形件的個數(shù)無約束；優(yōu)化目標(biāo)是使得板材切割的矩形件總價值V最大。數(shù)學(xué)模型為

其中，pi為排樣方式P中第i種矩形件的個數(shù)。

TCS問題的解(排樣方案)由一組排樣方式組成，每種排樣方式由相應(yīng)的TUP排樣算法生成。經(jīng)常采用線性規(guī)劃(linear programm ing, LP)求解TCS問題。LP的求解步驟為：

步驟 1. 構(gòu)造一個初始可行解。

步驟 2. 確定第 i種矩形件的當(dāng)前價值，i= 1,2,…,m。

步驟 3. 采用相應(yīng)的TUP算法求解模型(1)，得到一個新的排樣方式P。

步驟 4. 用排樣方式 P置換當(dāng)前排樣方案中的一個排樣方式，當(dāng)且僅當(dāng) P能改善當(dāng)前排樣方案，轉(zhuǎn)步驟2；否則轉(zhuǎn)步驟5。

步驟 5. 輸出排樣方案。

1.2 FBUS排樣方式相關(guān)概念

1.2.1 條帶

一個或多個矩形件排成一行(列)所占據(jù)的板材條稱作條帶[11]。有普通條帶、同質(zhì)條帶、均勻條帶3種類型，如圖1所示，條帶中的數(shù)字表示矩形件編號。普通條帶可以切割成多種矩形件、同質(zhì)條帶只允許切割成一種矩形件、均勻條帶可以切割成多種寬度相同的矩形件。文獻(xiàn)中針對普通條帶和同質(zhì)條帶研究較多，而均勻條帶尚未見相關(guān)研究。由分析可知：①均勻條帶可直接切割成矩形件而無需后續(xù)修剪，因此其切割工藝比普通條帶簡單。②均勻條帶可排放多種矩形件，板材利用率高于同質(zhì)條帶。因此均勻條帶能較好地平衡切割工藝與材料利用率。本文采用均勻條帶。

圖1 條帶

1.2.2 FBUS排樣方式

FBUS排樣方式首先用一條父分界線將板材分成兩個子板，然后用兩條與父分界線垂直的子分界線將子板分成A、B、C、D 4個塊，各塊中只排放長度和方向均相同的均勻條帶；當(dāng)子板是左右排列時稱之為X向FBUS排樣方式，當(dāng)子板是上下排列時稱之為Y向FBUS排樣方式(圖2)。

圖2 FBUS排樣方式的2種類型

2 算法原理

2.1 排樣方式生成算法

2.1.1 生成條帶

令vi為第 i種矩形件的價值，s(j,x)為條帶x(長)×wj(寬)的價值，ei為條帶中第i種矩形件的數(shù)量，則有如下公式

2.1.2 生成塊

塊由條帶組成，且同一塊由長度和方向均相同的條帶組成。將水平條帶組成的塊稱為X向塊，將豎直條帶組成的塊稱為Y向塊。對于X向塊，條帶的長度等于塊的長度；對于 Y向塊，條帶的長度等于塊的寬度(塊的水平邊為長，豎直邊為寬)。對于塊x(長)×y(寬)，記f( x, y)為塊的價值，x≤L，y≤W。對X向塊，設(shè)其由 zX(j, x)個水平條帶 x×wj組成，fX(x, y)為塊價值；對Y向塊，設(shè)其由 zY(j, y)個豎直條帶y×lj組成，fY(x, y)為塊價值。則有如下數(shù)學(xué)模型

模型(3)、(4)均是無約束背包問題，具體解法可參閱文獻(xiàn)[12]。

2.1.3 生成FBUS排樣方式

設(shè)最優(yōu)X向、最優(yōu)Y向FBUS排樣方式的價值分別為VX、VY，最終的FBUS排樣方式價值為V。則有如下公式

式(6)中 x為父分界線的橫坐標(biāo)，y1，y2為兩條子分界線的縱坐標(biāo)。

式(7)中y為父分界線的縱坐標(biāo)，x1，x2為兩條子分界線的橫坐標(biāo)。

2.2 排樣方案生成算法

采用LP求解排樣方案[11]，其線性松弛模型為

其中，z為排樣方案總共使用的板材面積；C= [c1, c2,···,cm]，其中ci=L×W(i=1,2,...,m)； X= [x, x,···,x ]T，其中x為第i種排樣方式使用的數(shù)

1 2 mi量；A為排樣方案矩陣(m階方陣)，其元素aij表示第j種排樣方式中包含第i種矩形件的個數(shù)；B= [b, b ,...,b]T，其中b為第i種矩形件的需求量。

1 2 mi本文排樣方案生成算法有以下7個步驟(圖3)：

步驟 1. 輸入板材尺寸數(shù)據(jù) L、W，毛坯尺寸和需求量數(shù)據(jù) li、 wi、bi。

步驟 2. 令每張板材只排放一個第i種矩形件，得到初始可行排樣方案，易知該排樣方案使用張板材，此時A為單位矩陣。

步驟3. 確定矩形件價值向量 V=C A-1= [v1, v2,···,vm]。

步驟 4. 按照各矩形件當(dāng)前價值，調(diào)用排樣方式生成算法，生成一個新的排樣方式 P= [p1,p2,···,pm]，pi表示該排樣方式包含第i種矩形件的個數(shù)。

步驟 5. 計算引進(jìn) P是否能夠減少當(dāng)前排樣方案所用板材總面積z。

步驟 6. 用P替換原有排樣方案中的第k個排樣方式，其中k滿足生成一個新的排樣方案，記錄此時的排樣方案矩陣A。

步驟7. 輸出最終排樣方案。

圖3 排樣方案生成算法的流程圖

3 實例驗證

在VS2012平臺上進(jìn)行本文算法實驗編程。所用計算機(jī)為 AMD Athlon(tm) 64 X2 Dual Core Processor 4800+2.51 GHz，2.87 GB內(nèi)存。由于本文算法是確定的，故只要算法執(zhí)行完畢，實驗條件對算法求得的解無影響。

3.1 本文算法與文獻(xiàn)[7]算法比較

采用文獻(xiàn)[7]的 15道隨機(jī)測題，板材尺寸L、 W∈[2000,3000]，矩形件種數(shù) m∈ [50,200]，尺寸li、wi∈[50,200]。文獻(xiàn)[7]算法(TKP算法)生成三階段排樣方式，本文算法生成四塊排樣方式。令VTS、VFB分別為三階段排樣方式和四塊排樣方式價值，tTS、tFB分別為TKP算法和本文算法生成排樣方式所耗費的計算時間。表 1為測題的數(shù)值實驗結(jié)果。從表1可以看出，15道測題中本文算法排樣價值有9道測題高于TKP算法，有4道測題等于TKP算法，有2道測題低于TKP算法。本文算法平均排樣價值為4 391 592，TKP算法平均排樣價值為4 389 562，本文算法平均排樣價值高于TKP算法。對于15道測題本文算法平均計算時間與TKP算法近似，計算時間能夠滿足實際應(yīng)用需要。

表1 15道測題的實驗結(jié)果

3.2 本文算法與文獻(xiàn)[11]算法比較

采用文獻(xiàn)[11]的 6道測題(P1～P6)，板材尺寸L、 W∈[1500,2500]，矩形件種數(shù) m∈ [2,18]，尺寸li、wi∈ [150,600]，需求量 bi∈ [1000,20000]，i= 1,2,· ··, m 。實驗結(jié)果如表2所示，其中UT、UF、uT、uF分別為T型下料算法和本文下料算法排樣方案耗費的板材張數(shù)和板材利用率。本文算法求解6道測題總共耗時0.71 s，平均每道測題耗時0.12 s，計算時間在實際應(yīng)用中合理。從表2可以看出6道測題，T型下料算法平均耗費板材4 520張，利用率為97.14%；本文下料算法平均耗費板材4 492張，利用率為97.67%。本文下料算法比T型下料算法節(jié)省28張板材，提高材料利用率0.53%。另外注意到T型下料算法采用的是普通條帶，本文下料算法采用的是均勻條帶，由于均勻條帶可直接切割成矩形件而無需后續(xù)修剪，故在切割工藝方面，本文下料算法優(yōu)于T型下料算法。

圖4為本文下料算法生成的測題3排樣方案，此排樣方案由 12種排樣方式組成，其中“圖 4(a)方式1(303張)”表示按照排樣方式1使用板材303張。12種排樣方式總共使用板材7 153張，板材利用率為97.38%。

表2 6道測題的實驗結(jié)果

圖4 測題3的排樣方案

4 結(jié) 束 語

材料利用率和切割工藝復(fù)雜度是板材TCS問題需要考慮的 2個主要因素。本文提出了新型的FBUS排樣方式，其將板材分為4個塊，每個塊中只排放方向相同的均勻條帶，切割工藝比較簡單，板材利用率較高。構(gòu)造了生成該種排樣方式的背包算法，并和線性規(guī)劃算法相結(jié)合設(shè)計了基于FBUS排樣方式的下料算法。算法時間復(fù)雜度較低，易于實現(xiàn)相應(yīng)下料軟件，能夠有效地解決矩形件需求量較大的TCS問題。

[1] W?scher G, Hau?ner H, Schumann H. An improved typology of cutting and packing problems [J]. European Journal of Operational Research, 2007, 183(3): 1109-1130.

[2] 鄧應(yīng)波, 祝勝蘭, 饒運(yùn)清. 一種針對絕緣紙板排樣的混合算法[J]. 機(jī)械設(shè)計與制造, 2013, (3): 23-25.

[3] Andrade R, Birgin E G, Morabito R. Two-stage two-dimensional guillotine cutting stock problems w ith usable leftover [J]. International Transactions in Operational Research, 2016, 23(1/2): 121-145.

[4] Hifi M, Negre S, Ouafi R, et al. A parallel algorithm for constrained two-staged two-dimensional cutting problems [J]. Computers & Industrial Engineering, 2012, 62(1): 177-189.

[5] Cui Y D, Huang B X. Heuristic for constrained T-shape cutting patterns of rectangular pieces [J]. Computers & Operations Research, 2012, 39(12): 3031-3039.

[6] Cui Y D. Heuristic for two-dimensional homogeneous two-segment cutting patterns [J]. Engineering Optim ization, 2013, 45(1): 89-105.

[7] Cui Y D. A new dynam ic programm ing procedure for three-staged cutting patterns [J]. Journal of Global Optim ization, 2013, 55(2): 349-357.

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

[9] 陳學(xué)松, 曹 炬, 方仍存. 遺傳模擬退火算法在矩形優(yōu)化排樣系統(tǒng)中的應(yīng)用[J]. 鍛壓技術(shù), 2004, 29(1): 27-29.

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

[11] Cui Y D. Generating optimal T-shape cutting patterns for rectangular blanks [J]. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2004, 218(8): 857-866.

[12] Kellerer H, Pferschy U, Pisinger D. Knapsack problems [M]. Berlin: Springer Berlin Heidelberg, 2004: 211-234.

A Determ inistic Algorithm for Solving the Problem of Two-Dimensional Sheet Cutting Stock

Zeng Zhaom in1, Wang Jihong2, Guan Weili3

(1. Sichuan Institute of Information Technology, Guangyuan Sichuan 628017, China; 2. School of Electrical Engineering, Zhengzhou University of Science＆Technology, Zhengzhou Henan 450064, China; 3. Information Engineering College, Nanning University, Nanning Guangxi 530200, China)

This paper discusses the two dimensional sheet cutting stock problem, that is, use the least number of sheets to cut out a certain number of rectangular pieces. A determ inistic algorithm is proposed which based on the combination of knapsack algorithm and linear programm ing algorithm. First, a knapsack algorithm is constructed to generates the four blocks uniform strip pattern, then the linear programm ing algorithm is used to generate the cutting plans which iteratively calls the above knapsack algorithm to improve the objective function based on the principle of m inimum production cost and changes the current value of punched items to generate a new pattern according to the current value. Lastly, a set of optimal cutting patterns is selected to form the cutting scheme. The algorithm was compared w ith the famous T-shape algorithm using some benchmark problem tests. The results show that the algorithm can save more sheets than the T-shape one, and the calculation time is reasonable in practical application.

two-dimensional cutting; rectangle cutting stock; knapsack algorithm; linear programm ing algorithm

TP 399

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

A

2095-302X(2016)04-0471-05

2015-12-19；定稿日期：2016-02-03

四川省教育廳科研項目(GZY1 5C4 5)；廣西科學(xué)研究與技術(shù)開發(fā)計劃項目(1 2 1 1 8 0 1 7-1 0A)

曾兆敏(1974?)，女，四川西昌人，本科，副教授。主要研究方向為并行計算、計算機(jī)硬件。E-mail：zengzmsc@163.com

管衛(wèi)利(1977?)，男，廣西桂林人，碩士，副教授。主要研究方向為優(yōu)化算法、人工智能。E-mail：1430571958@qq.com