基于價(jià)值修正的圓片下料順序啟發(fā)式算法

胡 鋼， 楊 瑞， 潘立武

(1. 四川信息職業(yè)技術(shù)學(xué)院信息工程系，四川 廣元 628017；2. 鄭州科技學(xué)院電氣工程學(xué)院，河南 鄭州 450064；3. 河南牧業(yè)經(jīng)濟(jì)學(xué)院自動化與控制系，河南 鄭州 450011)

基于價(jià)值修正的圓片下料順序啟發(fā)式算法

胡 鋼1， 楊 瑞2， 潘立武3

(1. 四川信息職業(yè)技術(shù)學(xué)院信息工程系，四川 廣元 628017；2. 鄭州科技學(xué)院電氣工程學(xué)院，河南 鄭州 450064；3. 河南牧業(yè)經(jīng)濟(jì)學(xué)院自動化與控制系，河南 鄭州 450011)

討論圓片剪沖下料方案的設(shè)計(jì)問題。下料方案由一組排樣方式組成。首先構(gòu)造一種生成圓片條帶最優(yōu)四塊排樣方式的背包算法，然后采用基于價(jià)值修正的順序啟發(fā)式算法迭代調(diào)用上述背包算法，每次都根據(jù)生產(chǎn)成本最小的原則改善目標(biāo)函數(shù)并修正各種圓片的當(dāng)前價(jià)值，按照當(dāng)前價(jià)值生成一個(gè)新的排樣方式，最后選擇最優(yōu)的一組排樣方式組成下料方案。采用文獻(xiàn)中的基準(zhǔn)測題將文中下料算法與文獻(xiàn)中T型下料算法和啟發(fā)式下料算法分別進(jìn)行比較。實(shí)驗(yàn)計(jì)算結(jié)果表明，該算法的材料利用率比T型下料算法和啟發(fā)式下料算法分別高0.83%和3.63%，且計(jì)算時(shí)間在實(shí)際應(yīng)用中合理。

圓片；剪沖下料；四塊排樣方式；背包算法；啟發(fā)式算法

圓片剪沖下料問題是指采用剪切和沖壓工藝將庫存板材切割出一定數(shù)量的若干種圓片毛坯，滿足每種毛坯的需求量，使得所使用的板材張數(shù)最少。該問題是具有很高計(jì)算復(fù)雜度的NP難度問題，在機(jī)械、家具、船舶等制造行業(yè)中有著廣泛的存在[1]。目前國內(nèi)外對矩形下料問題研究較多[2-6]，然而對圓片下料問題研究卻比較少，Cui[7]提出了基于 T型排樣方式的線性規(guī)劃下料算法，由于線性規(guī)劃算法求得的解不一定是整數(shù)，最終解需要向上取整，因此解的質(zhì)量并不高。侯桂玉等[8]提出了基于直切排樣方式的啟發(fā)式下料算法，克服了線性規(guī)劃算法最終解需要向上取整的缺點(diǎn)，但由于直切排樣方式板材利用率比較低下，因此導(dǎo)致最終的排樣方案材料利用率并不理想。陳菲等[9]提出了材料利用率較高的三塊排樣方式生成算法，但是只能解決單張板材上的無約束排樣問題，無法解決下料問題。

本文提出基于四塊排樣方式的順序價(jià)值修正啟發(fā)式下料算法，用以解決圓片剪沖下料問題，即：①構(gòu)造一種背包算法生成圓片最優(yōu)四塊排樣方式；②采用基于價(jià)值修正的順序啟發(fā)式算法迭代調(diào)用上述背包算法求解下料方案。用該算法求解文獻(xiàn)中的例題，更能節(jié)省板材消耗。

1 數(shù)學(xué)模型和相關(guān)概念

1.1 問題描述及其數(shù)學(xué)模型

討論的圓片剪沖下料(circle cutting stock，CCS)問題可描述如下：已知板材尺寸L×W；有m種圓片，第i種圓片的直徑為di，需求量為bi( i= 1,2,···,m )。確定排樣方案，用盡量少的板材排出所需的全部圓片。排樣方案包含多個(gè)不同的排樣方式。排樣方式是指單張板材上圓片的排列方式[8]。

令J為排樣方案包含的排樣方式個(gè)數(shù)，pj= {a1j,a2j, ···,amj}為第j( j= 1,2,···,J )個(gè)排樣方式中所含圓片情況，其中aij為排樣方式中含第 i種圓片的數(shù)量。令Z為排樣方案使用板材的張數(shù)；xj為排樣方案包含第j個(gè)排樣方式的個(gè)數(shù)；N為非負(fù)整數(shù)集合。則CCS問題的數(shù)學(xué)模型為：

其含義是在滿足 2個(gè)約束條件下最小化板材使用張數(shù)。約束條件為：①每種圓片的需求量得到滿足；②每種排樣方式使用的數(shù)量為非負(fù)整數(shù)。

與 CCS問題緊密相關(guān)的是圓片排樣(circle cutting packing，CCP)問題，其數(shù)學(xué)模型為：

其中，V為排樣方式的價(jià)值，yi為排樣方式中包含的第i種圓片的個(gè)數(shù)，vi為第i種圓片的價(jià)值。

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

1.2.1 條帶

如圖1所示，條帶中可排放一排圓片或多排圓片，其中w為工藝余量。假設(shè)w=0，此假設(shè)不影響算法的通用性，因?yàn)楫?dāng) w≠ 0時(shí)，可令(d+w)為圓片直徑。為了滿足沖壓工藝約束，條帶中最多允許排放的圓片排數(shù)不超過3[7]。故按照條帶所包含圓片的排數(shù)可把條帶分為3類，定義第i種圓片的 第k類 條 帶 其 寬 度 為[10]： t(i-1)×3+ k=，其中， i= 1,···,m ,k= 1,2,3。 m種圓片共有3m種寬度的條帶。令 T = [t1,t2,··,t3m]為條帶寬度向量。

圖1 兩種圓片條帶

1.2.2 四塊排樣方式

四塊排樣方式的詳細(xì)定義參見文獻(xiàn)[11]。圖2為一圓片四塊排樣方式例圖，按順序使用 3條剪切線(圖中箭頭所示)將板材劃分為4個(gè)塊。左上角塊中包含2、10號水平條帶；左下角塊中包含2、3、8號豎直條帶；右上角塊中包含5號水平條帶；右下角塊中包含2、4號豎直條帶。分析四塊排樣方式的幾何性質(zhì)可知，四塊排樣方式是 T型和直切排樣方式的超集，故四塊排樣方式的板材利用率不會低于T型和直切排樣方式。

圖2 四塊排樣方式例圖

2 算法原理

2.1 排樣方式生成算法

2.1.1 計(jì)算條帶的價(jià)值

令n(j,x)為條帶x×tj(長為x，寬為tj)中所含圓片的個(gè)數(shù)， u(j,x)為條帶的價(jià)值，其中x≤L，j= 1,···,3 m ，則有[10]：

求解式(3)，算法時(shí)間復(fù)雜度為 O(m L)。

2.1.2 計(jì)算塊的價(jià)值

對于塊x×y，不妨設(shè)塊中條帶的長度方向與塊的x邊方向相同。記 F(x,y)為塊的價(jià)值，x≤L，y≤W。令 g(j,x)為塊中包含條帶x×tj的個(gè)數(shù)，則有：

式(4)是無界背包問題，具體算法可參見文獻(xiàn)[12]，時(shí)間復(fù)雜度為 O(m LW )。

2.1.3 計(jì)算四塊方式的價(jià)值

設(shè)四塊方式的3條剪切線位置分別為 x,y1,y2，其中 x,y1,y2均為整數(shù)。V為四塊方式價(jià)值，則有：

求解式(5)算法時(shí)間復(fù)雜度為 O(L W )。

2.1.4 算法步驟

步驟1. 根據(jù)式(3)生成所有可能的條帶。

步驟2. 根據(jù)式(4)生成所有可能的塊。

步驟3. 根據(jù)式(5)確定最優(yōu)四塊排樣方式。

2.2 排樣方案生成算法

傳統(tǒng)的啟發(fā)式下料算法生成排樣方案可簡單描述如下[8]：

(1) 初始化各種圓片的剩余需求量為圓片的需求量。

(2) 使用剩余圓片生成當(dāng)前排樣方式，在盡量少產(chǎn)生多余圓片的前提下，使得該種排樣方式盡量重復(fù)利用，記錄該排樣方式以及方式使用次數(shù)。

(3) 修改圓片的剩余量，判斷有無剩余圓片，若有則轉(zhuǎn)(2)，否則結(jié)束循環(huán)。

該算法存在貪婪性：好的排樣方式(板材利用率較高)在前面出現(xiàn)，而后面的排樣方式板材利用率偏低。出現(xiàn)這種情況的原因是：排樣方案中各種排樣方式順序產(chǎn)生，先生成的排樣方式優(yōu)先使用容易結(jié)合生成好的排樣方式的圓片(面積較小的圓片)；而不易結(jié)合生成板材利用率高的排樣方式的圓片(面積較大的圓片)被用來生成后面的排樣方式。該貪婪性使算法容易陷入局部最優(yōu)，而非全局最優(yōu)。為了克服該貪婪性，本文算法迭代構(gòu)造多個(gè)排樣方案，從中選擇板材使用張數(shù)最小的作為最終解；在生成每個(gè)排樣方式后均按照式(6)修正圓片的價(jià)值[13-17]。

表1列出了本文算法需要用到的變量符號。

表1 變量符號

具體步驟如下：

步驟1. 令 G=1，PNum=∞。初始化圓片價(jià)值，若 di≥ 0.5W，則令vi= λsi；否則令vi=si。

步驟2. 按如下步驟產(chǎn)生排樣方案：

(1) 令 j= 1，P=Φ，ri=bi(i∈I)。

(2) 調(diào)用2.1節(jié)排樣方式生成算法生成一個(gè)排樣方式P。

(3) 令 f =m in{ri/ yi|yi＞ 0,i ∈ I }，將P添加到排樣方案中。令 ri= ri- fyi,i∈ I ，修改圓片的剩余量。

(4) 按照式(6)修正圓片的當(dāng)前價(jià)值；如果存在ri＞ 0(i ∈I )，則令 j=j+ 1并轉(zhuǎn)(2)。

步驟 3. 如果排樣方案使用的板材張數(shù)小于PNum，則保存排樣方案，并記PNum為排樣方案使用的板材張數(shù)。

步驟4. 令 G=G+1，如果 G＞Gmax，輸出排樣方案，否則轉(zhuǎn)步驟2。

2.3 下料算法時(shí)間復(fù)雜度

本文算法總共構(gòu)造了Gmax個(gè)排樣方案；每個(gè)排樣方案考察了個(gè)排樣方式。由于四塊排樣方式生成算法時(shí)間復(fù)雜度為 O(m LW )，因此該算法總的時(shí)間復(fù)雜度為 O(mLWMGmax)。

3 數(shù)值實(shí)驗(yàn)

用C#語言在主頻為2.7 GHz、內(nèi)存為2 GB的計(jì)算機(jī)上進(jìn)行實(shí)驗(yàn)。參數(shù) α= 0.75，β=1.03，Gmax= 200。采用文獻(xiàn)中的測題，將本文算法和文獻(xiàn)中的下料算法進(jìn)行比較。

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

采用文獻(xiàn)[7]的20道測題，板材長為2 000，寬為1 000，剪沖工藝余量為8，每條條帶最多允許排放3排圓片，圓片直徑在區(qū)間[100, 500]均勻分布，圓片需求量在區(qū)間[500, 3000]均勻分布。具體數(shù)據(jù)及文獻(xiàn)[7]算法下料利用率統(tǒng)計(jì)結(jié)果，參見排樣網(wǎng)站 http://www.gxnu.edu.cn/Personal/ydcui/ English/Problems/COR2005-32-01.DTXT。

20道測題，本文算法平均下料利用率為72.56%，文獻(xiàn)[7]算法平均下料利用率為71.73%，可見本文算法平均下料利用率比文獻(xiàn)[7]算法高0.83%。求解20道測題文中算法總共耗時(shí)12.69 s，平均每道測題耗時(shí) 0.63 s；文獻(xiàn)[7]算法總共耗時(shí)12.92 s，平均每道測題耗時(shí)0.65 s，本文算法和文獻(xiàn)[7]算法計(jì)算時(shí)間近似，能滿足實(shí)際應(yīng)用需要。

圖 3為本文算法求得的測題 18的排樣方案圖，包含10個(gè)排樣方式，其中圖3(a)表示按照排樣方式1切割59張板材；排樣方案總共使用716張板材，板材利用率為73.06%；文獻(xiàn)[7]算法排樣方案總共使用724張板材，板材利用率為72.26%。

圖3 測題18的排樣方案

3.2 與文獻(xiàn)[8]下料算法比較

采用文獻(xiàn)[8]的15道隨機(jī)測題來檢驗(yàn)本文算法。測題具體數(shù)據(jù)見文獻(xiàn)[8]第4節(jié)。對于15道測題，本文算法求得的排樣方案板材平均利用率為72.85%，文獻(xiàn)[8]算法求得的排樣方案板材平均利用率為69.22%。圖4為本文算法求得的測題1的排樣方案圖，共使用板材 77張，板材利用率為77.79%；文獻(xiàn)[8]算法求得的測題1的排樣方案共使用板材84張，板材利用率為71.27%，可見本文算法能夠顯著的提高材料利用率。

圖4 測題1的排樣方案

3.3 一個(gè)生產(chǎn)實(shí)例的求解

某電機(jī)制造廠用規(guī)格為3000 mm×1500 mm的硅鋼板材，切割出8種尺寸不同的圓片，表2所示為圓片具體規(guī)格和需求量，剪沖工藝余量為6 mm。采用傳統(tǒng)啟發(fā)式算法下料利用率為69.62%，采用本文價(jià)值修正的順序啟發(fā)式算法下料利用率為 74.16%，明顯的提升下料利用率，減少余料浪費(fèi)。

表2 圓片直徑和需求量

4 結(jié) 論

實(shí)現(xiàn)了基于四塊排樣方式的圓形片剪沖下料算法，在生成排樣方案的過程中通過不斷修正各圓片價(jià)值，使得排樣方式更加趨于合理。實(shí)驗(yàn)結(jié)果表明，本文算法材料利用率比文獻(xiàn)[7]和[8]算法分別高0.83%和3.63%。將本文的四塊排樣方式生成算法和整數(shù)規(guī)劃相結(jié)合，設(shè)計(jì)剪沖下料問題的精確算法可以作為以后研究的方向。

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

[3] Dusberger F, Raidl G R. Solving the 3-staged 2-di mensional cutting stock problem by dynam ic programming and variable neighborhood search [J]. Electronic Notes in Discrete Mathematics, 2015, 47: 133-140.

[4] Kim K, Kim B I, Cho H. Multiple-choice knapsack-based heuristic algorithm for the two-stage two-dimensional cutting stock problem in the paper industry [J]. International Journal of Production Research, 2014, 52(19): 5675-5689.

[5] Gómez J C, Terashima-Marín H. Building general hyper-heuristics for multi-objective cutting stock problems [J]. Computacióny Sistemas, 2012, 16(3): 321-334.

[6] A ryanezhad M B, Hashem i N F, Makui A, et al. A simple approach to the two-dimensional guillotine cutting stock problem [J]. Journal of Industrial Engineering International, 2012, 8(1): 1-10.

[7] Cui Y D. Generating optimal T-shape cutting patterns for circular blanks [J]. Computers & Operations Research, 2005, 32(1): 143-152.

[8] 侯桂玉, 崔耀東, 黃少麗, 等. 一種求解圓形件下料問題的啟發(fā)式算法[J]. 計(jì)算機(jī)工程, 2010, 36(13): 227-229.

[9] 陳 菲, 劉 勇, 劉 睿, 等. 基于3塊方式的圓形片剪沖排樣算法[J]. 計(jì)算機(jī)工程, 2009, 35(14): 195-196.

[10] Cui Y D, Gu T L, Hu W. A cutting-and-inventory control problem in the manufacturing industry of stainless steel wares [J]. Omega, 2009, 37(4): 864-875.

[11] 易向陽, 仝青山, 潘衛(wèi)平. 矩形件二維下料問題的一種求解方法[J]. 鍛壓技術(shù), 2015, 40(6): 150-154.

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

[13] Cui Y D, Cui Y P, Zhao Z G. Pattern-set generation algor ithm for the one-dimensional cutting stock problem with setup cost [J]. European Journal of Operational Research, 2015, 243(2): 540-546.

[14] Cui Y D, Yang L, Zhao Z G, et al. Sequential grouping heuristic for the two-dimensional cutting stock problem with pattern reduction [J]. International Journal of Production Econom ics, 2013, 144(2): 432-439.

[15] Cui Y P, Cui Y D, Tang T B. Sequential heuristic for the two-dimensional bin-packing problem [J]. European Journal of Operational Research, 2015, 240(1): 43-53.

[16] Cui Y P, Tang T B. Parallelized sequential value correction procedure for the one-dimensional cutting stock problem with multiple stock lengths [J]. Engineering Optim ization, 2014, 46(10): 1352-1368.

[17] 姚 怡, 賴朝安. 一種帶剪切約束的啟發(fā)式二維裝箱算法[J]. 圖學(xué)學(xué)報(bào), 2015, 36(6): 879-886.

Sequential Value Correction Heuristic Algorithm for the Circle Cutting Stock Problem

Hu Gang1, Yang Rui2, Pan Liwu3

(1. Information Engineering Department, Sichuan Institute of Information Technology, Guangyuan Sichuan 628017, China; 2. School of Electrical Engineering, Zhengzhou University of Science＆Technology, Zhengzhou Henan 450064, China; 3. Department of Automation and Control, Henan University of Animal Husbandry & Economy, Zhengzhou Henan 450011, China )

This paper discusses the problem of generating optimal cutting plan for circles. The cutting plan consists of several cutting patterns. First a knapsack algorithm that generating four-block cutting patterns of circle strips was constructed; then the sequential value correction heuristic algorithm was used to generate the cutting plan, it iteratively calls the above knapsack algorithm procedure improves the objective function based on the principle of m inimum production cost and correct the current value of circles, generates a new pattern according to the current value; in the end a set of optimal cutting patterns was choose to form the cutting plan. The cutting stock algorithm was tested with the benchmark problems of literatures, and compared with the T-shape algorithm and heuristic algorithm. The results of numerical experiments show that, the material utilization rate of the algorithm is higher 0.83% and 3.63% than the above two algorithms.

wafer; cutting stock; four block patterns; knapsack problem; heuristic algorithm

TP 391

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

A

2095-302X(2016)03-0337-05

2015-11-03；定稿日期：2015-11-25

河南省科技廳科技攻關(guān)項(xiàng)目(152102210320)；河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(15B52000)

胡 鋼(1982–)，男，四川瀘州，講師，本科。主要研究方向?yàn)閮?yōu)化計(jì)算、軟件開發(fā)、實(shí)驗(yàn)室管理。E-mail：rtfdgl@163.com

潘立武(1971–)，男，河南杞縣人，副教授，博士。主要研究方向?yàn)橹悄苡?jì)算、CAD、軟件開發(fā)。E-mail：hge5963@163.com