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

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

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

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

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

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

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

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

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

1.2 建立過程

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

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

圖1 排列方式

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

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

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

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

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

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

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

而后對(duì)最優(yōu)排列作隨機(jī)的變動(dòng)從而得到一組新的排列，即是在余集中隨機(jī)選擇一個(gè)材料尺寸替換初始排列中的一個(gè)材料尺寸從而產(chǎn)生新的一種排列方案，對(duì)新排列方案繼續(xù)進(jìn)行普通Kriging 插值預(yù)測(cè)，計(jì)算A1與Δ=A1－A0。如果Δ小于等于0，則接受新排列為此時(shí)的最優(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的計(jì)算公式為：

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

2.2 識(shí)別算法的提出

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

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

3 改進(jìn)模擬退火算法

3.1 模型構(gòu)建

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

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

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

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

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

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

3.2 算法優(yōu)化

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

圖3 材料尺寸變化圖

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

4 結(jié)論

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