基于最優化約束和模擬退火算法的鋼板切割問題研究

李永圣，馬景濤，甘惠材，白博雄

（哈爾濱理工大學，黑龍江 哈爾濱 150081）

在鋼材廠切割鋼板時，先將原材料鋼卷放在開卷機上，被送至剪切平臺上進行剪切。剪切臺上依次有剪切頭和圓盤剪[1]。剪切頭只能一刀切，如需額外橫向切割，只能將材料移至小機器進行切割。生產板料時在切割后直接下料，卷料則需通過卷取機壓臂成卷后再入庫。原料在切割成品時若有剩余，符合余料標準的回收入庫下次使用。對于鋼材廠而言，如何提升成材率就是需要考慮的關鍵因素。本質等同于在固定的立體空間中盡量塞入多的大小不一的箱子，即把某種離散對象按照某種已經確定的約束條件進行安排，當得知符合這種約束條件的特定安排存在時，求解此種特定安排在某個優化準則下的最大解或最小解的離散組合最優化問題。

1 基本模型構建與分析

1.1 整數規劃模型構建

將整數規劃模型分為幾個階段，根據約束條件分別引入變量。

第一階段考慮規劃問題：

第二階段考慮規劃問題：

1.2 建立過程

程序變量為不同大小的產品，矩陣中存儲著產品的長度y、寬度x，需要加工的產品只有卷材，共5 種，分別是訂單1、訂單2、訂單3、訂單4、訂單5，這5個訂單的Z分別為36、29、42、32、18。在數據庫中任意選擇一個產品，之后繼續任意選擇一個產品編號為j，使j產品緊緊挨著產品i放置。由于卷料都特別長，為了避免成材率過低，也減輕程序運算的負擔，規定主程序選擇的原材料長度都大大長于1—5 號產品，也就是只選擇長度在10 萬以上的原材料，即只有1、6、8 和9 這4 種原材料被程序選擇。將產品逐個編號，范圍為1—157。

程序從矩陣中隨機抽出一個產品，放置在矩陣右上角。假設該產品編號為i。程序在數據庫中任意選擇一個產品，將其安放在原材料左上角，之后繼續任意選擇一個產品編號為j，使j產品緊緊挨著產品i放置，此時原材料被用去的寬度為xi+xj，當小于xi時，就繼續添加產品直至產品的總寬度大于等于xi。為了避免重復添加，已經被添加的產品會在存儲矩陣中被刪除。排列方式如圖1所示。

圖1 排列方式

假設某一行排列了b個產品（由于排刀上限，b＜6），無法再增加新的產品了，那么在切割完本行產品之后需要重新排刀與進行一刀切，即切頭剪。切頭剪的位置選取的是這b個產品當中最長的那個，即最大的那個，假設為yp。此時，切刀的位置就是y－yp。之后在新的一行重復產品的選擇流程，直到矩陣中存儲的產品都選擇到。

在剪切過程中原材料因為被剪切而不斷變短。如果剩余原材料短于整個存儲矩陣中最短的產品，即沒有合適的產品能與之匹配，則更換材料。程序在運行過程中必須隨時保存中間結果，即統計產品面積，以及選擇出符合題目要求的余料，然后根據面積比值計算成材率，作為優化的參考指標。

經過程序運算得到27個排列方案。

2 模擬退火算法的模型優化與改進

2.1 模型優化過程

模擬退火算法來源于金屬材料退火過程的模擬，將金屬加熱到較高溫度的過程中，金屬內部粒子隨溫度升高從有序變為無序狀，同時粒子內能升高，再讓其緩慢冷卻，此時粒子逐漸從無序趨于有序，每個溫度都達到平衡態，最后在常溫時達到基態，此時內能為最小[2]。首先從27個排列方式中隨機選擇一種排列方式作為最優排列[3-4]，用最優排列對原材料進行普通Kriging 插值預測，計算初始解的均方根誤差。計算公式如下所示：

式（1）中：A為均方根誤差；n為可行排列方案數；Si為原材料面積；Ci為產品的面積。

而后對最優排列作隨機的變動從而得到一組新的排列，即是在余集中隨機選擇一個材料尺寸替換初始排列中的一個材料尺寸從而產生新的一種排列方案，對新排列方案繼續進行普通Kriging 插值預測，計算A1與Δ=A1－A0。如果Δ小于等于0，則接受新排列為此時的最優解排列方案；但如果Δ大于0，則按照Metropolis 準則以概率P來選擇新的排列方案，否則保留原排列方案。1—9 排列方案如圖2所示。

圖2 1—9 排列方案

Metropolis 準則：設從當前排列方案生成新的排列方案，如果新排列方案的排刀數小于原排列方案的排刀數（即A1＜A0），則將新的排列方案作為當前方案；否則，以概率P來選擇新的排列方案。概率P的計算公式為：

此方案的最終成材率為71.03%。

2.2 識別算法的提出

卷料與板料長度相差過大，不宜混合生產。因此本文抽取了程序運算的部分中間結果，也就統計出了產品面積并選擇出了符合題目要求的余料，然后根據面積比值計算成材率，發現啟發式算法前期的搜索模式太過粗陋，因此根據數據演化的定量規律做了調整[5-6]。

盡量減少人工排刀數可以通過盡量擴大n來解決，減小再切割數則要求同一行的產品盡量是同一訂單號的產品。盡量減少再切割數需要優先把相同的元素并排放置。

3 改進模擬退火算法

3.1 模型構建

改進以后的模擬退火算法使用隨機的選擇概率P，用來選擇比目前差一些的排列方案，依靠一定的概率跳出局部最優排列方案這一陷阱，從而得到全局最優排列方案。設之前某個排列方案為x（n），算法通過排刀數這一指標，排列方案變為x（n+1），對應地，方案的排刀數由E（n）變為E（n+1），定義由x（n）變為x（n+1）的選擇概率P為：

通過上述公式可以說明，當排刀數減小時，排列方案的變化會被選擇（此時的概率P為1），當排刀數增加時，意味著此排列方案的變化偏離了全局最優排列方案，但是算法在此時不會放棄該排列方案的變化，而是對此變化進行一定的概率選擇：在區間[0，1]中隨機選擇一個數，當隨機選擇的數小于P時，說明這種排列方案的變化是被算法接受的，否則拒絕排列方案的變化，進入下一步循環流程。選擇概率P的取值不是固定不變的，而是動態變化的，它的大小是由排刀數的變化量決定。

改進后的模擬退火算法流程：①假設B是初始解，設定Bi=B，設定開始退火溫度為T，令i=0；②設T=Ti，用參數T及Bi引入Metorpolis 抽樣算法中計算，返回狀態Ai作為本算法的當前解；③空冷階段中，令T=Ti+1，式中Ti+1

選擇合適的排刀數對本算法影響較大，排刀數越低，搜索性則越強，得到最優解的概率就越大，但程序運算時間會變得很長。本算法選取排刀數經過反復試驗獲得。本算法中循環鏈的鏈長表示為任何一個排列方案，或者為遍歷次數，稱循環數。如果想盡可能減少人工切刀的數量，解決方法就是優先把相同尺寸的材料并排放置。但這本質上和降低排刀數是部分矛盾的，優先排布相同尺寸材料降低了橫向組合產品的自由度，導致降低排刀數的目標受到了阻礙。

因此，需要改進啟發式算法，應優先保證排刀數降低，在此基礎上盡可能降低人工切刀的數量。

最終切割方案板料的總排刀次數為128 次，再次切割的次數為307 次，卷料的總排刀次數51 次，再切割次數為64 次，板材的成材率為68.34%，卷材的成材率為71.03%。

3.2 算法優化

為了降低運算量，不能每添加一個產品就進行一次浮動放縮，應采取填縫的措施。添加完一行的產品后，以最長的產品為基準，與剩下的短的產品做比較，延長短的產品使其在允許的尺寸浮動范圍內到達到最長產品的長度，如果短產品不能達到最長產品的長度，即把短產品延長到最大允許的浮動尺寸。采用這種思路，分別計算了板料和卷料的結果。材料尺寸變化圖如圖3所示。

圖3 材料尺寸變化圖

在每次材料運算的過程中添加一個判斷條件，檢查訂單數是不是這7 種中的一個。之后分別計算板料和卷料，并針對部分訂單輸出了浮動比。最終結果的卷材成材率為75.04%，板料的成材率為76.74%。

4 結論

本文圍繞鋼板切割刀都是實際的生產問題，先用受約束的整數算法來求出所有可行的解決方式，再通過程序中間結果，即統計產品面積，選擇出符合題目要求的預料，然后根據面積比值計算成材率，作為優化的參考指標。并加入識別算法，來確保不生產過量，最后通過優化退火算法得到最終的板材切割方案。