基于兩段排樣方式的矩形件優(yōu)化下料算法

扈少華，武書(shū)彥，潘立武

?

基于兩段排樣方式的矩形件優(yōu)化下料算法

扈少華，武書(shū)彥，潘立武

(河南牧業(yè)經(jīng)濟(jì)學(xué)院軟件學(xué)院，河南 鄭州 450011)

針對(duì)矩形件下料問(wèn)題，提出一種基于兩段排樣方式的優(yōu)化下料算法。首先構(gòu)造一種約束排樣算法，生成矩形件在板材上的兩段排樣方式。然后采用列生成算法依據(jù)矩形件剩余需求量迭代調(diào)用上述約束排樣算法生成一個(gè)虛擬下料方案，按照不產(chǎn)生多余矩形件原則選取虛擬下料方案中的部分排樣方式加入到實(shí)際下料方案中，更新矩形件剩余需求量；重復(fù)上述步驟直到矩形件剩余需求量為零。采用文獻(xiàn)中基準(zhǔn)例題將該算法與2種文獻(xiàn)算法進(jìn)行比較，數(shù)值實(shí)驗(yàn)結(jié)果表明該算法下料利用率比2種文獻(xiàn)算法分別高1.61%和0.78%。

下料問(wèn)題；兩段排樣方式；列生成算法；約束排樣；矩形件

在機(jī)械制造業(yè)的生產(chǎn)過(guò)程中經(jīng)常會(huì)遇到矩形件下料(rectangular items cutting stock，RCS)問(wèn)題:用長(zhǎng)為、寬為的板材切割出種不同規(guī)格的矩形件，其中第種矩形件的長(zhǎng)為l、寬為w、需求量為d，=1,2,···,；優(yōu)化目標(biāo)為板材使用張數(shù)最少。RCS問(wèn)題的解是一個(gè)下料方案，由多個(gè)不同的排樣方式組成，每個(gè)排樣方式對(duì)應(yīng)單張板材上矩形件的具體排列方式[1]。

針對(duì)RCS問(wèn)題，目前常見(jiàn)的求解方法有整數(shù)規(guī)劃、線(xiàn)性規(guī)劃和順序啟發(fā)式算法。

文獻(xiàn)[2]提出了基于兩階段排樣方式的整數(shù)規(guī)劃模型，研究了RCS問(wèn)題的線(xiàn)性松弛下界。文獻(xiàn)[3]提出了基于三階段排樣方式的整數(shù)規(guī)劃模型，該模型具有多項(xiàng)式個(gè)數(shù)的變量和約束條件；構(gòu)造了該模型的分支定價(jià)和集合覆蓋求解算法。文獻(xiàn)[4]通過(guò)擴(kuò)展一維下料問(wèn)題的數(shù)學(xué)模型構(gòu)造了RCS問(wèn)題基于兩階段和三階段排樣方式的整數(shù)規(guī)劃模型，其中決策變量對(duì)應(yīng)板材各階段的切割線(xiàn)位置。以上文獻(xiàn)方法只能求解規(guī)模較小的RCS問(wèn)題，對(duì)于中大規(guī)模的RCS問(wèn)題，耗費(fèi)的計(jì)算時(shí)間讓人無(wú)法忍容。

文獻(xiàn)[5-6]采用線(xiàn)性規(guī)劃方法對(duì)RCS問(wèn)題進(jìn)行了探討。研究表明，線(xiàn)性規(guī)劃方法的求解速度快于整數(shù)規(guī)劃方法。但線(xiàn)性規(guī)劃方法求得的下料方案解(各個(gè)排樣方式的頻數(shù))為小數(shù)，并非RCS問(wèn)題的實(shí)際可行解。文獻(xiàn)中通過(guò)對(duì)線(xiàn)性規(guī)劃解進(jìn)行向上取整操作得到RCS問(wèn)題的實(shí)際可行解。但向上取整會(huì)增加下料方案的板材使用張數(shù)，浪費(fèi)板材資源。

順序啟發(fā)式算法通過(guò)逐個(gè)生成排樣方式來(lái)構(gòu)造下料方案，每個(gè)排樣方式滿(mǎn)足部分矩形件需求量，當(dāng)所有矩形件需求量均得到滿(mǎn)足時(shí)，算法終止。文獻(xiàn)[7]提出了求解一維下料問(wèn)題的順序啟發(fā)式算法，該算法能在較短的時(shí)間內(nèi)得到近似最優(yōu)解。文獻(xiàn)[8]提出了1.5維下料問(wèn)題的迭代順序啟發(fā)式算法，其可通過(guò)改變參數(shù)得到不同的排樣方式。文獻(xiàn)[9]提出了RCS問(wèn)題基于價(jià)值修正策略的順序啟發(fā)式算法，并通過(guò)不斷修正矩形件的價(jià)值使排樣方式更趨于合理。文獻(xiàn)[10]提出了一種以排樣方式為導(dǎo)向的啟發(fā)式下料算法，迭代構(gòu)造多個(gè)排樣方式，每次選取排樣價(jià)值最大的一個(gè)排樣方式加入到下料方案中。文獻(xiàn)[11]構(gòu)造了3種啟發(fā)式排樣規(guī)則：首次適應(yīng)插入、最佳適應(yīng)插入和關(guān)鍵適應(yīng)插入，并提出了一種新穎的適應(yīng)度計(jì)算公式。

本文針對(duì)RCS問(wèn)題提出一種基于兩段排樣方式的優(yōu)化下料算法，該算法結(jié)合了線(xiàn)性規(guī)劃和順序啟發(fā)式算法思想。首先構(gòu)造兩段排樣方式的約束排樣算法，然后采用線(xiàn)性規(guī)劃法調(diào)用約束排樣算法生成多個(gè)虛擬下料方案，按照不產(chǎn)生多余矩形件原則選取各個(gè)虛擬下料方案中的部分排樣方式組合形成實(shí)際下料方案。數(shù)值實(shí)驗(yàn)結(jié)果表明本文算法能有效的節(jié)約板材資源。

1 兩段排樣方式及其數(shù)學(xué)模型

1.1 兩段排樣方式

用一條平行于板材邊的分割線(xiàn)將板材劃分為兩個(gè)段，同一段中排放方向相同的條帶，這種排樣方式稱(chēng)為兩段排樣方式[12]。兩段排樣方式有4種類(lèi)型(圖1)，即HXX型、HXY型、VXY型和VYY型。其中HXY型中的“H”表示兩個(gè)段是水平排放，“XY”表示第一個(gè)段為向段，第二個(gè)段為向段。

圖1 兩段排樣方式的類(lèi)型

圖2中，箭頭所示的分界線(xiàn)將板材分為水平排放的兩個(gè)段；圖2(a)左右兩個(gè)段中分別包含3條水平條帶；圖2(b)左邊段中包含3條水平條帶，右邊段中包含2條豎直條帶。

圖2 兩段排樣方式例圖

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

約束兩段排樣問(wèn)題：采用兩段排樣方式將長(zhǎng)為、寬為的板材切割出種不同規(guī)格的矩形件，約束每種矩形件允許切割的數(shù)量不大于其需求量，l、w、c、b分別為第種矩形件的長(zhǎng)、寬、價(jià)值、需求量，其中=1,2,···,；優(yōu)化目標(biāo)為使得板材切割出的矩形件總價(jià)值最大。令排樣方式中包含y個(gè)第種矩形件，即

其中，為自然數(shù)集合。

2 兩段排樣方式生成算法

令板材和矩形件的水平邊為長(zhǎng)，豎直邊為寬。假設(shè)板材和矩形件的尺寸均為整數(shù)，此假設(shè)不影響本文算法的通用性，因?yàn)楫?dāng)板材或矩形件尺寸不為整數(shù)時(shí)，可將板材和矩形件尺寸按比例尺放大到整數(shù)。本節(jié)著重研究HXY型兩段排樣方式的生成算法，同理易得其他3種類(lèi)型的兩段排樣方式的生成算法。

2.1 條帶的價(jià)值

對(duì)矩形件按照寬度非遞減順序編號(hào)，即1≤2≤····≤w。令(,)為水平條帶′w(長(zhǎng)：，寬：w)的價(jià)值，其中=1,2,···,，=0,1,···,；(,,)為水平條帶′w中包含矩形件的個(gè)數(shù)，則有

2.2 段的價(jià)值

記(,,)為向段′(長(zhǎng)：、寬：)中包含矩形件的個(gè)數(shù)，其中(,,0)=0。可通過(guò)動(dòng)態(tài)規(guī)劃遞推可得段的價(jià)值(,)，即

其中，(,0)=0；e表示段中排入水平條帶′w所獲得的價(jià)值增量。同理可確定向段′的價(jià)值。

2.3 排樣方式生成算法

步驟1. 根據(jù)2.1節(jié)內(nèi)容，生成與向段′主排樣相關(guān)的所有水平條帶′w(=0,1,···,；=1,2,···,)和與向段′主排樣相關(guān)的所有豎直條帶l′。

步驟2. 根據(jù)2.2節(jié)內(nèi)容，生成向段′的主排樣，記兩段排樣方式價(jià)值=F(,)。

步驟3. 從1到枚舉分割線(xiàn)位置。

步驟3.1. 確定向段′的主排樣。

步驟3.2. 生成與向段(–)′輔排樣相關(guān)的所有豎直條帶，確定向段(–)′的輔排樣。

步驟3.4. 生成與向段′輔排樣相關(guān)的所有水平條帶，確定向段′的輔排樣。

步驟4. 輸出最優(yōu)兩段排樣方式。

3 下料算法

RCS問(wèn)題的解即下料方案，其由多個(gè)不同的排樣方式組成，其中每個(gè)排樣方式的頻數(shù)(使用次數(shù))為非負(fù)整數(shù)，RCS問(wèn)題的整數(shù)規(guī)劃數(shù)學(xué)模型為

式(5)的線(xiàn)性松弛形式為

本文下料算法步驟如下[1]：

步驟1. 初始化實(shí)際下料方案為空，即不包含任何排樣方式。

步驟2. 初始化剩余下料問(wèn)題為原始下料問(wèn)題，即矩形件的剩余需求量為d。

步驟3. 采用基于列生成的線(xiàn)性規(guī)劃算法[15]迭代調(diào)用2.3節(jié)兩段排樣方式生成算法求解當(dāng)前剩余下料問(wèn)題的線(xiàn)性松弛式(6)，得到一個(gè)虛擬下料方案(由于每種排樣方式的頻數(shù)可能為小數(shù)，因此并不符合實(shí)際)。

步驟4. 按照一定規(guī)則選取當(dāng)前虛擬下料方案中的部分排樣方式加入到實(shí)際下料方案中，更新每種矩形件的剩余需求量；若當(dāng)前所有矩形件的剩余需求量均為0，則轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟3。

步驟5. 輸出實(shí)際下料方案。

步驟3~4反復(fù)求解剩余下料問(wèn)題的線(xiàn)性松弛式直到所有矩形件的需求量均得到滿(mǎn)足。步驟3采用列生成算法迭代調(diào)用第2節(jié)排樣方式生成算法得到虛擬下料方案中的各個(gè)排樣方式。

令max為當(dāng)前虛擬下料方案中排樣方式頻數(shù)的小數(shù)部分的最大值，有0≤max<1，令參數(shù)在區(qū)間[0,1]取值。記為虛擬下料方案中當(dāng)前正在考察的排樣方式，=[1,2,···,y]，其中y為中包含矩形件的數(shù)量，令為的頻數(shù)。步驟4按照以下規(guī)則選取虛擬下料方案中的排樣方式加入到實(shí)際下料方案中：

方案1.對(duì)虛擬下料方案中的排樣方式按照其頻數(shù)非遞增順序進(jìn)行排序。

方案2.按順序逐個(gè)考察排樣方式，如果≥max且對(duì)任意?{1,2,···,}有y≤d，則將加入到實(shí)際下料方案中。

分析可知，方案2每次至少選取了一個(gè)排樣方式加入到實(shí)際下料方案中，這是因?yàn)?i>y≤d對(duì)每個(gè)排樣方式均滿(mǎn)足且至少存在一個(gè)排樣方式其頻數(shù)大于等于max，這保證了下料算法的收斂性。另外可知取值越小，加入到實(shí)際下料方案中的排樣方式個(gè)數(shù)就越多。

4 數(shù)值實(shí)驗(yàn)計(jì)算

用C++語(yǔ)言編程實(shí)現(xiàn)本文下料算法，在英特爾奔騰雙核G4400 CPU，主頻3.3 GHz，內(nèi)存4 GB計(jì)算機(jī)上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)平臺(tái)為Microsoft Visual Studio 2012。采用文獻(xiàn)中基準(zhǔn)例題，將本文下料算法與文獻(xiàn)[5]和[6]算法進(jìn)行比較。

4.1 與文獻(xiàn)[5]算法的比較

用本文下料算法求解文獻(xiàn)[5]的6道例題(ID1-ID6)。考察=0.65、0.75、0.85、0.95的4種情形。實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果見(jiàn)表1，其中、分別為本文下料算法的下料利用率和計(jì)算時(shí)間。從表1可以看出，本文下料算法的計(jì)算時(shí)間隨著的增加而增加，下料利用率隨著的增加先增加后減少。這是因?yàn)樵酱螅看渭尤氲綄?shí)際下料方案的排樣方式越少，矩形件剩余需求量遞減的速度較慢，算法迭代次數(shù)較多；當(dāng)?shù)娜≈党^(guò)某一臨界值后，每次只能加入一個(gè)排樣方式到實(shí)際下料方案中，算法貪婪性變強(qiáng)，使得下料利用率變低。文獻(xiàn)[5]算法平均下料利用率為97.14%；本文下料算法在=0.85時(shí)平均下料利用率最高，比文獻(xiàn)[5]算法高1.61%。本文下料算法的計(jì)算時(shí)間不超過(guò)3 s，計(jì)算時(shí)間在實(shí)際應(yīng)用中比較合理。

表1 實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

4.2 與文獻(xiàn)[6]算法的比較

某電機(jī)廠(chǎng)，需要用長(zhǎng)為1 000 mm，寬為600 mm的板材切割出10種矩形件，矩形件長(zhǎng)寬尺寸在區(qū)間[70 mm,220 mm]分布，需求量在區(qū)間[4000,10000]分布，具體數(shù)據(jù)見(jiàn)文獻(xiàn)[6]中的表3。文獻(xiàn)[6]算法生成的下料方案使用2 285張板材，下料利用率為99.18%；本文算法(取值為0.85)生成下料方案，計(jì)算時(shí)間為2.67 s，下料方案使用2 267張板材，下料利用率為99.96%；本文算法下料利用率比文獻(xiàn)[6]算法高0.78%。另外本文算法板材下料利用率接近100%，說(shuō)明該算法在節(jié)省板材資源和提高板材利用率方面是有效的。本文算法在生成下料方案的過(guò)程中總共考察了109個(gè)排樣方式，平均每個(gè)排樣方式耗時(shí)0.024 s。圖3為本文算法生成的下料方案，共包含15個(gè)排樣方式，其中“圖3(a)方式1：706張”表示按照排樣方式1切割板材706張。

5 結(jié) 論

RCS問(wèn)題廣泛地存在于機(jī)械制造業(yè)的板料成形生產(chǎn)過(guò)程中，一個(gè)好的優(yōu)化下料算法可減少板材消耗，降低板材切割難度。本文設(shè)計(jì)了一種基于動(dòng)態(tài)規(guī)劃和列生成的順序啟發(fā)式下料算法。首先采用動(dòng)態(tài)規(guī)劃算法生成對(duì)矩形件數(shù)量有約束的兩段排樣方式，然后采用列生成算法迭代調(diào)用動(dòng)態(tài)規(guī)劃算法依次生成多個(gè)虛擬下料方案，按照不產(chǎn)生多余矩形件原則在各個(gè)虛擬下料方案中選取若干排樣方式構(gòu)成實(shí)際下料方案。數(shù)值實(shí)驗(yàn)結(jié)果表明，本文下料算法可有效地節(jié)省板材資源，且計(jì)算時(shí)間能滿(mǎn)足實(shí)際應(yīng)用需要。

[1] 胡鋼, 楊瑞, 潘立武. 基于價(jià)值修正的圓片下料順序啟發(fā)式算法[J]. 圖學(xué)學(xué)報(bào), 2016, 37(3): 337-341.

[2] LODI A, MARTELLO S, VIGO D. Models and bounds for two-dimensional level packing problems [J]. Journal of Combinatorial Optimization, 2004, 8(3): 363-379.

[3] PUCHINGER J, RAIDL G R. Models and algorithms for three-stage two-dimensional bin packing [J]. European Journal of Operational Research, 2007, 183(3): 1304-1327.

[4] SILVA E, ALVELOS F, DE CARVALHO J M V. 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.

[5] CUI Y. 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.

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

[7] HAESSLER R W. A heuristic programming solution to a nonlinear cutting stock problem [J]. Management Science, 1971, 17(12): B793-B802.

[8] SONG X, CHU C B, NIE Y Y, et al. An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem [J]. European Journal of Operational Research, 2006, 175(3): 1870-1889.

[9] 黃少麗, 楊劍, 侯桂玉,等. 解決二維下料問(wèn)題的順序啟發(fā)式算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2011, 47(13): 234-237.

[10] CHARAMBOUS C, FLESZAR K. A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts [J]. Computers & Operations Research, 2011, 38(10): 1443-1451.

[11] FLESZAR K. Three insertion heuristics and a justification improvement heuristic for two-dimensional bin packing with guillotine cuts [J]. Computers & Operations Research, 2013, 40(1): 463-474.

[12] 潘衛(wèi)平, 陳秋蓮, 崔耀東. 考慮切割刀數(shù)的最優(yōu)兩段排樣算法研究[J]. 廣西大學(xué)學(xué)報(bào): 自然科學(xué)版, 2014, 39(3): 687-692.

[13] KELLERER H, PFERSCHY U, PISINGER D. Knapsack problems [M]. Berlin: Springer, 2004: 56-79.

[14] CUI Y, HUANG B. A heuristic for constrained T-shape cutting patterns of circular items [J]. Engineering Optimization, 2011, 43(8): 867-877.

[15] 車(chē)念, 張軍, 潘立武. 沖裁條帶剪切下料問(wèn)題的一種求解算法[J]. 機(jī)械設(shè)計(jì)與制造, 2016(2): 37-40.

An Optimization Algorithm for Rectangular Items Cutting Stock Problem Based on Two-Segment Patterns

HU Shaohua, WU Shuyan, PAN Liwu

(Software College, Henan University of Animal Husbandry & Economy, Zhengzhou Henan 450011, China)

For on the rectangular items cutting stock problem, an optimization algorithm based on two-segment patterns is proposed. Firstly, a constrained packing algorithm is constructed to generate the two-segment patterns of rectangular items on the plate. Then, column generation algorithm is used to generate a virtual cutting plan according to the current remaining demand of rectangular items, several patterns are added into actual cutting plan according to the rule that no redundant rectangular item is generated, and the current remaining demand of rectangular items is updated. The above steps are repeated until the remaining demand of rectangular items is zero. Compared the proposed algorithm with two algorithms in the literature through benchmark instances, results of numerical experiments show that material utilization of the proposed algorithm is higher than two literature algorithms about 1.61% and 0.78%, respectively.

cutting stock problem; two-segment patterns; column generation algorithm; constrained packing; rectangular items

TP 391

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

A

2095-302X(2018)01-0091-06

2017-06-08；

2017-06-28

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

扈少華(1978–)，男，河南鄭州人，講師，碩士。主要研究方向?yàn)镃AD、智能制造。E-mail：hshhnmy@163.com