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

（哈爾濱理工大學(xué)，黑龍江 哈爾濱 150081）

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

1 基本模型構(gòu)建與分析

1.1 整數(shù)規(guī)劃模型構(gòu)建

將整數(shù)規(guī)劃模型分為幾個階段，根據(jù)約束條件分別引入變量。

第一階段考慮規(guī)劃問題：

第二階段考慮規(guī)劃問題：

1.2 建立過程

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

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

圖1 排列方式

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

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

經(jīng)過程序運算得到27個排列方案。

2 模擬退火算法的模型優(yōu)化與改進

2.1 模型優(yōu)化過程

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

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

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

圖2 1—9 排列方案

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

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

2.2 識別算法的提出

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

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

3 改進模擬退火算法

3.1 模型構(gòu)建

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

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

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

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

因此，需要改進啟發(fā)式算法，應(yīng)優(yōu)先保證排刀數(shù)降低，在此基礎(chǔ)上盡可能降低人工切刀的數(shù)量。

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

3.2 算法優(yōu)化

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

圖3 材料尺寸變化圖

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

4 結(jié)論

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