貪心策略在電站鍋爐管材套料優化的應用研究

曲默豐， 辛 煒， 宋華強

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

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

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

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

1 數學模型

目標函數為：

(1)

約束條件為：

(2)

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

2 求解方法

2.1 貪心策略

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

2.2 算法流程

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

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

圖1 原材料管材切割

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

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

算法流程見圖2。

圖2 算法流程

3 計算結果及分析

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

3.1 與相關公開套料數據的對比

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

表1 目標管材信息

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

表2 算法1計算結果

表3 算法2計算結果

表4 算法3計算結果

表5 算法4計算結果

3.2 與S公司實際套料數據對比

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

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

表7 S公司目標管材信息

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

表8 S公司實際套料結果

表8(續)

表9 算法4計算結果

表9(續)

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

4 結語

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