基于遺傳算法的兩階段切割問題的研究

劉志宏 喻曉旭

摘要

切割問題因切割模式數量非常龐大，存在較多局部最優解，被看作一個NP-hard問題。本文所研究的兩階段切割問題是基于無縫鋼管制造過程，將無縫鋼管的熱軋和冷軋過程抽象成一個兩階段切割問題，以對其進行數學建模。同時利用遺傳算法求解非線性規劃問題的優勢，并使用MATLAB工具對遺傳算法進行實驗模擬仿真，從而得出實驗結果數據，經研究顯示遺傳算法是一種很理想的求解兩階段切割問題的算法。

【關鍵詞】遺傳算法 兩階段 切割問題MATLAB

切割問題常見于我國制造業中，包括布料、造紙、玻璃、皮革機、鋼鐵等行業。根據Dyckhoff的分類方法，切割問題按維度數可劃分為一維、二維和三維切割問題。國內就一維切割問題的研究進展較大，目前使用較為廣泛的有啟發式算法、單純型算法等，都能取得較好的實驗結果，但現有研究對余料控制問題尚有不足。

1兩階段切割問題數學模型

無縫鋼管的制造包括兩個加工流程：熱軋和冷軋。鋼管的熱軋和冷軋過程非常復雜。在傳統一維切割問題中，通常把原材料直接進行一次加工切割，這種方式會產生大量的余料。而兩階段切割是從訂單合同交貨長度出發，形成一定量的鋸切長度管坯，再進行二次切割，從而減少余料的方法。為了便于研究，可把問題簡單描述如下：在生產過程中，將原料管坯通過第一階段熱軋，切割成鋸切長度;之后將第一階段的鋸切長度鋼管進行第二階段冷軋，從而變成訂單合同交貨長度鋼管，如圖1所示。訂單合同可根據交貨合同長度不同劃分為兩種，即定尺合同和非定尺合同。定尺合同對鋼管的單根交貨長度和總交貨量進行了明確規定;非定尺只給出了單根管子的交貨長度區間和總交貨長度。

本文不考慮鋸切損失的問題，同時，由于非定尺合同存在較大的不確定性，很難直接進行最優化求解，對此，本文提出一種將非定尺合同轉為定尺合同的簡單方法，從而將兩階段切割問題轉化為直接針對定尺合同問題進行研究。非定尺合同轉化為定尺合同的步驟如下.

（1）取出第一個合同，計算出符合交貨區間長度的最小根數flmin和最大根數flmax。

（2）根據[flmin，flmax]區間，從小到大順序依次計算出根數所對應的交貨長度，如有符合的交貨長度，則結束，若無，則取交貨長度十分位最大者，將它作為新的定尺合同長度。

以下給出模型建立的變量定義：

Id，（d∈l…n）：定尺合同集合。If，（f∈1…n）：非定尺合同集合。

Id，（d∈1…n）：定尺合同集合。Li，（i∈Id）：定尺合同交貨長度。

DNi，（i∈Id）：定尺合同交貨數量。Y∈[Ymin，Ymax]：原料管坯長度。

SL∈[SLmin，SLmax]：鋸切長度。

從而可得出兩階段切割問題數學模型：

階段一：熱軋切割模型。模型建立的過程如下：首先，從數據庫中取出{Li，DN.}，兩個參數以確定第一階段的切割長度;其次，對數據進行預處理，這個過程對切割數量非常少的合同十分重要;第三，按照定尺合同的長度進行字典排序;第四，根據參數建立切割數學模型，求出SL長度，即第一次熱軋的鋸切長度。具體模型如下：

SL=∑ni=1aiβiLi，

（1）

具體參數說明如下，DN.表示第個合同的定尺長度，ai是調整系數的權重，ai∈（O，10），表示所占比重，計算公式如下ai=m*Pi，這里m取10，Pi表示第2個長度切割在所有合同占的比重，公式如下：

βi表示是否選擇這個做為有效的長度，定義如下：

這個系數通過對于DN，的排序進行選擇。

階段二：冷軋切割模型。模型建立過程如下：從數據庫中取出{Li，DNi）兩個參數，根據上述計算出的鋸切長度SL，以求解余料最少為最終問題。

min f（1，x），其中1表示SL，x是一組向量，表示定尺長度L.，表達式如下：

f（l，x）=∑i（l-∑，xi Li），

（3）

S.T. l-∑ixiLi>o，

（4）

實際上就是切割1分成定尺長度Li，屬于帶約束的線性規劃問題，xi的確定方法同上。

2遺傳算法

遺傳算法通過模擬人類進化論的自然選擇和遺傳學機理的生物進化過程所建立的計算模型，并通過不斷的自然進化搜索最優解的方法。遺傳算法常用于求解線性規劃方面的問題，其主要步驟如下：

（1）編碼。

（2）初始化種群。

（3）評估個體適應度。評估種群中所對應個體的適應度。

（4）選擇。參照適應度函數，遵照適應度越高，選擇概率越大的原則，從種群中選擇兩個個體作為父方和母方。

（5）交叉。將父方和母方染色體進行交叉，產生新的子代。

（6）變異。對子代染色體進行變異。

（7）演化。重復3/4/5/6步驟，直至產生新的種群。

（8）結束。3實驗仿真

由于兩階段問題可行性解數量較大，當合同數量達到50個時，切割模式數量可達到700多種，迭代次數3275次。原料管坯長度lOOOmm，本次仿真取3個合同集，具體參數如表l所示。

在實驗仿真時，使用MATLAB進行實驗仿真，該軟件自帶遺傳工具箱，通過迭代不斷逼近最優解。

上述最優解為：原料管坯共使用47根，鋸切長度為500mm，一共需鋸切94根鋸切長度，余料為1650mm，余料比率為3.5106%。

4結論

兩階段切割問題是公認的NP-hard問題，存在大量的局部最優解，在第三部分的實驗仿真階段可以看出，遺傳算法可以很好地解決兩階段切割問題中最優解問題，同時計算效率較高，余料控制比較理想。由于合同問題中的非定尺合同長度具有較大的不確定性，本文通過把非定尺合同定尺化的方法，將難點進行轉移。這一做法在尋找最優解的過程中是非常關鍵的一步。

參考文獻

[1] Dyckhoff， H.A typology of cuttinga packing problem[J]. EuropeanJournal of Operational Research，1939 （44）：145 -159.

[2]劉桂林，鋼管生產短尺寸合同與非定尺合同組批優化算法[J].寶鋼技術，2007 （02）： 42-44.

[3]王紫萍，線材下料問題

目標函數的一個注記[J]，中國科技信息，2008 （21）.