曲默豐， 辛 煒， 宋華強(qiáng)

(上海鍋爐廠有限公司， 上海 200245)

一維套料問(wèn)題普遍存在于電站鍋爐受熱面制造過(guò)程中，即將一種或多種規(guī)格的一維原材料管材通過(guò)切割的方式重新組成一種或多種規(guī)格的目標(biāo)材料管材[1]。一維套料問(wèn)題屬于NP-hard問(wèn)題，其目標(biāo)一般為原材料的利用率最大化，目前可以通過(guò)精確或啟發(fā)式算法進(jìn)行求解[2]。當(dāng)原材料種類單一且數(shù)量較少時(shí)，采用線性規(guī)劃法、分支定界法等[3]可以得到準(zhǔn)確解；而當(dāng)原材料種類和數(shù)量較多時(shí)，切割的組合數(shù)量將會(huì)呈現(xiàn)爆炸式增加，使得求解變得非常困難，因此通常采用啟發(fā)式算法獲得近似最優(yōu)解。近年來(lái)，啟發(fā)式算法由于具有效率高、精度高的優(yōu)點(diǎn)受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。賈志欣等[4]運(yùn)用遺傳算法優(yōu)化下料問(wèn)題，其主體思路為視目標(biāo)材料的一種順序?yàn)橐粋€(gè)方案，將不同種方案進(jìn)行組合優(yōu)化運(yùn)算(簡(jiǎn)稱算法1)；王小東等[5]利用多級(jí)序列線性優(yōu)化的方法求解下料問(wèn)題，屬于改進(jìn)的啟發(fā)式算法(簡(jiǎn)稱算法2)；祝勝蘭[6]對(duì)單一規(guī)格與多規(guī)格下料問(wèn)題分別進(jìn)行研究，最終采用先匯總切割然后按照約束條件搜索最優(yōu)途徑的方法(簡(jiǎn)稱算法3)。

相比于精確求解，上述算法雖然在運(yùn)算速度與原材料利用率等方面有了較大提升，但是仍然存在一定的改善空間。目前，大多數(shù)算法針對(duì)多規(guī)格一維套料問(wèn)題的求解一般僅考慮原材料長(zhǎng)度大于目標(biāo)材料的情況，而未對(duì)部分原材料長(zhǎng)度小于目標(biāo)材料的情況進(jìn)行討論。在電站鍋爐水冷壁、過(guò)熱器及再熱器的制造過(guò)程中，上述的第二種套料情況十分普遍，針對(duì)同時(shí)適用于兩種套料方式且高效省料的算法展開研究具有十分重要的科研價(jià)值和工程意義。為此，筆者綜合考慮貪心策略與實(shí)際工程經(jīng)驗(yàn)，提出了適用于電站鍋

爐管材套料的新求解方法(簡(jiǎn)稱算法4)。

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

目標(biāo)函數(shù)為：

(1)

約束條件為：

(2)

式中：F為消耗原材料總長(zhǎng)度的最小值；Xin為與Dn相對(duì)應(yīng)的第i種排列組合數(shù)量；Pim為與dm相對(duì)應(yīng)的第i種排列組合數(shù)量；Yi為第i種排列組合重復(fù)次數(shù)。

2 求解方法

2.1 貪心策略

貪心策略屬于啟發(fā)式算法范疇，在一維多規(guī)格管材套料問(wèn)題中，貪心策略首先將消耗原材料總長(zhǎng)度最小這一全局目標(biāo)拆解為多個(gè)子目標(biāo)，然后按照某種順序和策略依次對(duì)各個(gè)子目標(biāo)進(jìn)行優(yōu)化，從而獲得局部最優(yōu)解，最后將局部最優(yōu)解串聯(lián)起來(lái)并認(rèn)為得到全局最優(yōu)解。貪心策略雖然不能準(zhǔn)確地計(jì)算得出全局最優(yōu)解，但是其最終結(jié)果仍然是全局最優(yōu)解的較佳近似值之一[7]。

2.2 算法流程

采用貪心策略求解多規(guī)格一維套料問(wèn)題分為以下步驟：

(1)將原材料管材[Ln,Dn]和目標(biāo)管材[lm,dm]分別按照管材長(zhǎng)度從大到小的順序排列。

圖1 原材料管材切割

(3)設(shè)置偏差最大值界限(可參考原材料管材總長(zhǎng)與目標(biāo)管材總長(zhǎng)之間的偏差，根據(jù)實(shí)際情況適當(dāng)調(diào)整)，并取最小偏差所對(duì)應(yīng)的組合作為局部最優(yōu)解。

(4)匯總所有局部最優(yōu)解并得到最終計(jì)算結(jié)果。

算法流程見圖2。

圖2 算法流程

3 計(jì)算結(jié)果及分析

該算例均在主頻為1.6 GHz、內(nèi)存為8 GB的計(jì)算機(jī)上運(yùn)行。

3.1 與相關(guān)公開套料數(shù)據(jù)的對(duì)比

采用文獻(xiàn)[5]中的經(jīng)典一維管材切割套料算例進(jìn)行計(jì)算并與其他學(xué)者采用不同算法計(jì)算得到的結(jié)果進(jìn)行對(duì)比。該算例可簡(jiǎn)述為：原材料管材長(zhǎng)度為3 m，數(shù)量若干，目標(biāo)管材長(zhǎng)度與數(shù)量見表1。

表1 目標(biāo)管材信息

算法1～4的計(jì)算結(jié)果[4-6]分別見表2～5。對(duì)比表2～5可以看出：4種算法均消耗了8根原材料管材，但是算法4計(jì)算得到的前7根原材料管材的余料長(zhǎng)度均為0，利用率最高，第8根原材料管材的余料長(zhǎng)度為2.4 m，長(zhǎng)于其他3種算法結(jié)果，更有利于后續(xù)套料使用，結(jié)合算法4運(yùn)行時(shí)間較短，僅為0.25 s，可知算法4較佳。

表2 算法1計(jì)算結(jié)果

表3 算法2計(jì)算結(jié)果

表4 算法3計(jì)算結(jié)果

表5 算法4計(jì)算結(jié)果

3.2 與S公司實(shí)際套料數(shù)據(jù)對(duì)比

S公司是全國(guó)領(lǐng)先的電站鍋爐生產(chǎn)制造公司，在鍋爐制造領(lǐng)域擁有雄厚的技術(shù)實(shí)力和豐富的生產(chǎn)經(jīng)驗(yàn)。筆者運(yùn)用算法4對(duì)該公司某容量П形鍋爐后煙井包覆管套料進(jìn)行計(jì)算，并與該公司實(shí)際套料數(shù)據(jù)進(jìn)行對(duì)比，原材料管材與目標(biāo)管材信息分別見表6與表7。

表6 S公司原材料管材信息

表7 S公司目標(biāo)管材信息

S公司實(shí)際套料結(jié)果與算法4計(jì)算結(jié)果分別見表8與表9。

表8 S公司實(shí)際套料結(jié)果

表8(續(xù))

表9 算法4計(jì)算結(jié)果

表9(續(xù))

由表8與表9對(duì)比可以看出：采用算法4套料產(chǎn)生的單根管余料普遍較少，并且第32種切割方式得到的管材余料較長(zhǎng)(長(zhǎng)度為3.15 m)，方便后續(xù)套料再次使用。此外，假設(shè)長(zhǎng)度大于1 m的原材料管材可作為后續(xù)套料使用，則S公司實(shí)際結(jié)果中滿足該條件的有6.723 m原材料管材1根，算法4計(jì)算結(jié)果中滿足該條件的有3.150 m和6.000 m原材料管材各1根，其中6.000 m原材料管材為未進(jìn)行任何切割操作的整根管，綜合考慮余料長(zhǎng)度與余料屬性，算法4在提高原材料管材利用率方面略勝一籌。結(jié)合算法4計(jì)算時(shí)間僅為1.36 s可知，其在工程實(shí)際的多規(guī)格一維管材套料計(jì)算中表現(xiàn)良好。

4 結(jié)語(yǔ)

筆者采用貪心策略與實(shí)際工程經(jīng)驗(yàn)相結(jié)合的方式，對(duì)電站鍋爐管材套料問(wèn)題提出了一種新的求解方法，該算法能夠明顯提高原材料的利用率且運(yùn)算速度較快，具有原理簡(jiǎn)單、結(jié)構(gòu)簡(jiǎn)潔、易于實(shí)現(xiàn)等特點(diǎn)。綜合考慮求解質(zhì)量、速度以及編程的難易程度，該算法是求解工程應(yīng)用問(wèn)題的實(shí)用方法。