郭欣哲 王浩洋 劉崢 孫學(xué)峰 施金豆 李明壯

摘 要：在鋼材制造業(yè)中，針對鋼材切割下料的問題，提高原材料利用率是各個企業(yè)迫切需要解決的問題。本文通過對幾種版式不同的原材料進(jìn)行切割，通過將其規(guī)整為1.5維問題，結(jié)合充分的線性約束，結(jié)合遺傳算法與蟻群算法的新式算法，建立數(shù)學(xué)模型，計算出最優(yōu)的排樣方案，節(jié)省原材料，使其在理論價值和生活實際中具有重要作用，提高企業(yè)經(jīng)濟效益。

關(guān)鍵詞：二維切割問題? 調(diào)度策略NP? 動態(tài)規(guī)劃? 線性約束? 新式啟發(fā)算法

中圖分類號：TG50? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ? ? ? ? ? ? ? 文章編號：1674-098X（2021）05（c）-0061-06

The problem of steel cutting in the steel manufacturing industry

GUO Xinzhe? WANG Haoyang? LIU Zheng? SUN Xuefeng? SHI Jindou? LI Mingzhuang

（Shenyang University of Aeronautics and Astronautics， Shenyang， Liaoning? Province， 110000? China）

Abstract： In the steel manufacturing industry， aiming at the problem of steel cutting and blanking， improving the utilization rate of raw materials is an urgent problem to be solved by various enterprises. In this paper， several raw materials with different formats are cut， which are regularized into 1.5-dimensional problems， combined with sufficient linear constraints， combined with the new algorithm of genetic algorithm and ant colony algorithm， a mathematical model is established to calculate the optimal layout scheme， save raw materials， make it play an important role in theoretical value and life practice， and improve the economic benefits of enterprises.

Key Words： Two-dimensional cutting problem; Scheduling strategy NP; Dynamic programming; Linear constraint; New heuristic algorithm

隨著社會生產(chǎn)力的不斷提高，生產(chǎn)規(guī)模不斷擴大，鋼材的原材料消耗量也隨之增加，但是由于鋼材價格的上漲，導(dǎo)致企業(yè)生產(chǎn)成本大幅上升，由此綜合利潤極劇下降，一些企業(yè)甚至出現(xiàn)虧損等情況。為了減輕企業(yè)壓力，當(dāng)務(wù)之急是在鋼材切割下料生產(chǎn)環(huán)節(jié)有效提高鋼材利用率，節(jié)省鋼材，降低產(chǎn)品的生產(chǎn)成本。本文闡述的鋼結(jié)構(gòu)產(chǎn)品排樣系統(tǒng)通過算法構(gòu)建了一個排樣效率高、計算速度快和排樣效果好的方法，充分地提高了鋼材的利用率，減少余料剩余及廢料的數(shù)量，大大提高了企業(yè)的生產(chǎn)力與效益。

1? 問題分析

1.1 問題回顧

某鋼材生產(chǎn)制造商的鋼材切割流程。其中開卷上料環(huán)節(jié)將原材料鋼卷放在開卷機上，展開、放平送至右側(cè)操作區(qū)域剪切過程在剪切臺上完成，剪切臺上依次有切頭剪和圓盤剪。

工廠未來一批訂單需求已給出，訂單需求數(shù)量必須恰好滿足（不允許超額供應(yīng)）。根據(jù)工廠現(xiàn)有原料切割訂單，每種原料的使用數(shù)目不能超過其庫存，如表1、表2所示。

1.2 初步分析

本文研究的主要問題就是二維板材切割問題，其中夾雜著眾多約束。如表1所示，對于原料下料問題首先要確實采用那些合理的模式[1]。本題要求不允許超額供應(yīng)，即為線性等式約束。其次根據(jù)題目要求的變量，將其數(shù)據(jù)化處理：排刀走刀限制、原料限制、余料限制等。可以將產(chǎn)品的長設(shè)為l，寬設(shè)為W，原料的長為L，寬為W，在研究面積的同時，把長度和寬度也作為兩個維度放入問題進(jìn)行研究。但因為面積與長寬有乘積關(guān)系，所以可以近似看成2.5個維度。運用數(shù)學(xué)思想，找出每一個問題的所求函數(shù)關(guān)系，然后根據(jù)約束條件，分別添加到不同的問題中，主要運用遺傳算法，設(shè)置合理的參數(shù)進(jìn)行模擬仿真下料，然后求解。

1.3 符號變量選取

符號變量如表3所示。

1.4 維切割模型的假設(shè)與建立

（1）假設(shè)切割過程無操作失誤導(dǎo)致原料浪費。

（2）假設(shè)無追加訂單。

（3）假設(shè)切割的鋼材全為合格品。

2? 數(shù)學(xué)模型

2.1 問題分析

一共有10種原料，在本問題中，考慮5種訂單。使用最少的原材料，將這些訂單合理排布在原料鋼材上，將問題數(shù)據(jù)化。

（1）目標(biāo)函數(shù)：總原材料最少。

（2）適度函數(shù)：總的成材率最高。

（3）決策變量：使用的材料序號，不同訂單的序號，材料數(shù)目，訂單數(shù)目。

（4）約束條件：滿足板料的需求量（不能超額供應(yīng)），材料庫存，排刀上限，余量標(biāo)準(zhǔn)。

2.2 蟻群算法和遺傳算法融合模型

遺傳算法是通過數(shù)學(xué)思維對達(dá)爾文生物進(jìn)化論中的自然選擇和遺傳思想進(jìn)行模擬的進(jìn)化過程推演，是一種通過將自然進(jìn)化的轉(zhuǎn)置到計算機上的過程搜索最優(yōu)解的方法。該算法通過數(shù)學(xué)的方式，利用計算機模擬運算，將問題求解過程轉(zhuǎn)化為類似于生物進(jìn)化中染色體基因交叉變異的過程。在求解復(fù)雜的組合優(yōu)化問題時，與一些傳統(tǒng)的優(yōu)化算法相比，通?？梢钥焖佾@得更好的優(yōu)化結(jié)果。

遺傳算法的基本運算過程如下。

（1）重置：設(shè)置進(jìn)化解析幾何電子計數(shù)器t=0，設(shè)置更大的進(jìn)化解析幾何T，隨機生成M個個體作為原始種群P（0）。

（2）個體評論：計算組P（t）中每個個體的相關(guān)性。

（3）選擇計算：選擇算法應(yīng)用于組。選擇的目的是將上升個體的基因立即遺傳給下一代或基于匹配交叉使新個體遺傳到下一代。選擇的實際操作是建立對群體中個體相關(guān)性的基本評估。

（4）交叉計算：交叉算法應(yīng)用于種群。進(jìn)化算法中的主導(dǎo)作用是交叉算法。

（5）變異運算：將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P（t）經(jīng)過選擇、交叉、變異運算之后得到下一代群體P（t+1）。

（6）終止條件判斷：若t=T，則以進(jìn)化過程中所得到的具有最大適應(yīng)度個體作為最優(yōu)解輸出，終止計算。

蟻群算法是一種用于尋找提升路徑的概率優(yōu)化算法。這類優(yōu)化算法具有普適計算、信息內(nèi)容反饋調(diào)整和啟發(fā)式搜索的特點，它本質(zhì)上是進(jìn)化算法中的研究型全局蟻群算法。將粒子群算法應(yīng)用于優(yōu)化問題的理論基礎(chǔ)是：螞蟻的行走路徑用于表示待優(yōu)化問題的可行解，所有螞蟻群的所有路徑構(gòu)成了該室內(nèi)空間。有待優(yōu)化的問題。路徑較短的螞蟻會釋放大量的引誘劑。隨著時間的推移，在較短路徑上積累的引誘物濃度逐漸增加，選擇這條路徑的螞蟻數(shù)量也在增加。最后，所有螞蟻在反饋調(diào)整的作用下都會集中在最佳路徑上，此時的匹配就是待優(yōu)化問題的最優(yōu)解。

（1）采用正反饋機制，使得搜索過程不斷收斂，最終逼近最優(yōu)解。

（2）每個個體可以通過釋放信息素來改變周圍的環(huán)境，且每個個體能夠感知周圍環(huán)境的實時變化，個體間通過環(huán)境進(jìn)行間接的通訊[4]。

（3）啟發(fā)式算法擁有其獨特的概率搜索方式，很容易達(dá)到全局最優(yōu)的情況。

遺傳算法雖然具有快速全局搜索能力，但是對于系統(tǒng)中的反饋信息卻沒有利用，往往導(dǎo)致無效的積冗迭代，求得的解往往不是最優(yōu)解[2]，而蟻群算法是通過信息的積累收集和更新，來預(yù)測收斂最優(yōu)路徑，但是算法開始階段信息匱乏，可使用信息較少，會導(dǎo)致算法速度變慢，前期準(zhǔn)確性降低，誤差積累到后期會導(dǎo)致誤差較大[3]。通過將兩種算法融合，一方面克服了遺傳算法陷入局部最優(yōu)解的情況，另一方面對照遺傳算法父代，減少蟻群算法的誤差，優(yōu)勢互補，形成了一種時間效率準(zhǔn)確性都比較好的啟發(fā)式算法[4]，并通過仿真模擬，進(jìn)行計算二維切割問題。

2.3 MIN（原材料）數(shù)學(xué)模型

原材料消耗最少數(shù)學(xué)模型：

，

且為整數(shù)。

余料約束：

適額約束：

長度與寬度約束：

面積約束：

目標(biāo)函數(shù)：

最優(yōu)解存在，但干擾近似解也同樣很多。我們將數(shù)學(xué)模型代入Lingo，求得最優(yōu)解如表4所示。

將得到的特解反向代入在MATLAB中構(gòu)建的啟發(fā)式算法中，得到遺傳算法迭代圖和蟻群算法軌跡圖[5]。如下圖1、圖2所示。

由圖3可知，在遺傳算法100次迭代之后，目標(biāo)函數(shù)優(yōu)化曲線已經(jīng)觸碰到最優(yōu)值，但波動較大，在經(jīng)過500次迭代之后，曲線的波動性減弱，漸漸平穩(wěn)于最優(yōu)解。在蟻群算法軌跡圖中，可以看出在經(jīng)歷多次迭代之后，軌跡圖形成閉環(huán)，且路程最短，可以判定函數(shù)已經(jīng)找到最優(yōu)解。將從Lingo得出的答案代入啟發(fā)式算法函數(shù)，結(jié)果滿足約束條件，且全局最優(yōu)。

2.4 二維矩件排樣模型

工廠加工要求使用圓盤剪前，需根據(jù)訂單切割方案進(jìn)行排刀。假設(shè)排刀架上可以以任意間距排刀，但刀具數(shù)量是有限制的，一次排刀上限不能超過5刀。用同一排刀方案切割得到的訂單稱為一組訂單，切割不同組時需要工人重新排刀，稱為一次換刀。切割每卷原材料之間均需要換刀[6]。切頭剪為“一刀切”，即將整個鋼板橫向完全切斷。經(jīng)過橫向切割后，當(dāng)且僅當(dāng)某些訂單還需要額外橫向一刀將其與廢料分開，則將這些訂單移至小機器再次切割[7]。同一組內(nèi)相同訂單可以通過一刀同時變成成品。鋼材切割訂單有兩種，分別是板料訂單和卷料訂單，切完的板料訂單直接通過下料小車包裝入庫[8]。

運用遺傳算法，將在Lingo中求得的數(shù)據(jù)進(jìn)行排樣，然后直接進(jìn)行優(yōu)化處理。遺傳算法設(shè)計如下。

（1）編碼：采用十進(jìn)制整數(shù)編碼方式。

（2）適應(yīng)度函數(shù)：將適應(yīng)度函數(shù)定義為f? = Area / Area1，其中，Area是待排入矩形零件的面積總和，Area1是所得排樣圖高度輪廓線以下的矩形板材面積。

（3）初始種群：使用隨機函數(shù)來生成一定數(shù)量的十進(jìn)制整數(shù)序列組成父輩群體，設(shè)定種群規(guī)模 M=50。

（4）交叉算子：采用單點交叉和雙點交叉設(shè)置交叉概率pc=1，單點交叉與雙點交叉各占一半。

（5）變異算子：采用位置變異和旋轉(zhuǎn)變異設(shè)置位置變異概率pm1=0.1和旋轉(zhuǎn)變異概率pm2=0.1。

（6）選擇算子：根據(jù)適應(yīng)度函數(shù)值從大到小排列執(zhí)行完交叉、變異操作的個體，選擇前M個個體組成下一代父輩群體。

（7）結(jié)束條件：設(shè)置迭代多少代，設(shè)置maxgen = 500。

針對矩形板材排樣問題，建立了整數(shù)規(guī)劃模型，利用Lingo，給出了多種限制的條件下的最優(yōu)排樣方案。通過軟件計算，需要切割的訂單的總面積為s=2336.8，原材料面積S=2715.6m2。

目標(biāo)函數(shù)為零件面積所占板材面積最大：

約束條件：

對于上述線性規(guī)劃，結(jié)合已求的原材料數(shù)量，利用Lingo軟件求解，得到了最優(yōu)排樣方案，如表5所示。

2.5 切割方案

得到具體切割方案，如表6所示。

3? 結(jié)語

（1）通過利用數(shù)學(xué)工具和各種編程軟件，嚴(yán)格地對模型進(jìn)行求解，具有科學(xué)性。

（2）本文針對矩形鋼材地優(yōu)化排版切割問題，建立了在不同限制條件下地約束方程，得到了可以解題地各個優(yōu)化模型，通俗易懂，且在保證使用最少原材料地基礎(chǔ)上，同時擁有較高地成材率，模型可以推廣到其他二維切割領(lǐng)域使用。

（3）同時對于可行解較多的模型計算，采用了不同的數(shù)學(xué)工具，大大減少計算時間，利用遺傳算法和蟻群算法的啟發(fā)式算法對計算過程和計算結(jié)果進(jìn)行優(yōu)化，得到了模型的最優(yōu)解，使模型的可操作性提高。

（4）本文數(shù)學(xué)模型建立在原材料供應(yīng)充足，并且完全切割的情況。但是在實際生產(chǎn)生活中，原材料供給不足，刀具損毀等多種情況發(fā)生，影響企業(yè)效益，那么在這種情況下如何改變參數(shù)和約束條件是今后研究的方向。

（5）本文研究并解決了一些特殊的切割問題，即1.5維切割問題。不僅把切割材料的長和寬作為思考方向，而且加入了面積因素。同時因為面積被材料的長和寬所限制，所以把面積以一個0.5維度放入問題進(jìn)行考慮。針對其特殊性，采用蟻群和遺傳算法進(jìn)行求解。計算結(jié)果表明，該新式混合算法對解決1.5維問題行之有效。其次對于可進(jìn)一步減小切割損耗的切割路徑優(yōu)化問題進(jìn)行討論。通過對比切割路徑優(yōu)化問題和旅行商問題，這雙方之間有很多共同之處，最終采用遺傳算法求解。最后為了進(jìn)一步減少浪費，對排樣切割所剩下的廢料采取進(jìn)一步的優(yōu)化措施。經(jīng)過一次切割之后，由于所剩廢料的數(shù)量和大小都不同，因此針對這些余料可建立二維切割矩形模型，解法同上。

參考文獻(xiàn)

[1] 熊慧，黃菊永.基于貪心啟發(fā)式算法的多目標(biāo)二維切割問題[J].電子技術(shù)與軟件工程，2016（24）：154-155.

[2] 丁建立，陳增強，袁著祉.遺傳算法與螞蟻算法融合的馬爾可夫收斂性分析[J].自動化學(xué)報，2004，30（4）： 629-634.

[3] 李淑芳.數(shù)控切割下料誤差產(chǎn)生的原因及應(yīng)對策略[J].自動化應(yīng)用，2018（10）：155-156.

[4] 武小年，奚玉昂，張潤蓮.DEM中基于遺傳與蟻群的混合路徑規(guī)劃算法[J].計算機應(yīng)用研究，2020，37（9）： 2694-2697.

[5] 李明.基于特征粒子算法的云資源調(diào)度策略研究[J].計算機與數(shù)字工程，2016，44（2）：307-310，342.

[6] 姚奕，鄭瀟，張文聰，等.重工鋼材智能切割管控系統(tǒng)軟件設(shè)計[J].電子技術(shù)與軟件工程，2021（8）：83-84.

[7] 張衡.基于二維平面裝箱模型的產(chǎn)品切割問題研究[J].運籌與模糊學(xué)，2019，9（4）：249-263.

[8] 何雙池，陳學(xué)松.二維矩形件排樣的切割式填充算法[J].數(shù)學(xué)的實踐與認(rèn)識，2019，49（18）：132-139.