貪心策略在電站鍋爐管材套料優(yōu)化的應(yīng)用研究

曲默豐， 辛 煒， 宋華強

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

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

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

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

1 數(shù)學模型

目標函數(shù)為：

(1)

約束條件為：

(2)

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

2 求解方法

2.1 貪心策略

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

2.2 算法流程

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

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

圖1 原材料管材切割

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

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

算法流程見圖2。

圖2 算法流程

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

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

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

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

表1 目標管材信息

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

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

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

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

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

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

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

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

表7 S公司目標管材信息

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

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

表8(續(xù))

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

表9(續(xù))

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

4 結(jié)語

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