改進的差分進化算法求解煉鋼-連鑄動態調度問題

金 焰，王秀英

(青島科技大學 信息科學技術學院，山東 青島 266061)

0 引言

鋼鐵的生產關系著制造業未來的發展方向，而煉鋼-連鑄是鋼鐵工業生產的關鍵過程，該過程的高效調度能夠有效縮短生產周期、降低生產成本和能源消耗、提高鋼鐵質量和生產效率。煉鋼-連鑄生產過程中主要包括三大工藝過程：煉鋼、精煉和連鑄[1]。由于煉鋼和精煉的生產過程是離散的，而連鑄階段為了提高產量需要連續生產，因此煉鋼-連續生產過程是離散和連續相結合的復雜生產過程。

近年來，國內外研究者們對煉鋼-連鑄生產調度問題主要方向仍然是靜態調度，動態調度的研究仍亟待求解。在煉鋼-連鑄實際的生產過程中，由于工藝復雜，多約束、多設備、多目標和隨機性等特點[2]，常常會出現各種不確定的擾動事件，使得實際生產無法按原始的調度計劃執行，如開工時間延遲、設備故障、緊急訂單添加等擾動事件[3]。煉鋼-連鑄動態調度的任務，就是當生產過程中出現擾動時，實時調整調度計劃表，保證連續生產的前提下，盡可能的減少能源消耗和等待時間，提高生產效率，降低生產成本[4]。羅小川[5]等針對煉鋼-連鑄中作業時間沖突引起的調度優化問題，提出了分部分求解的方案，先用線性規劃法解決調度問題，再用極大值原理解決連鑄機拉速變化問題，優化了煉鋼-連鑄生產過程中可能因時間擾動導致的調度過程出現時間沖突而導致斷澆的問題。張春生[6]等針對故障下的煉鋼-連鑄動態調度問題，提出了基于動態約束滿足技術建模機制，該機制靈活反映了實際生產車間中各種動態因素，能根據煉鋼-連鑄生產過程中出現的故障擾動程度實時制定不同的調度策略，保證了煉鋼-連鑄生產過程穩定進行。王柏琳[7]等針對煉鋼-連鑄生產過程中連鑄機出現故障而引起的動態調度問題，建立了動態約束滿足模型，提出了基于約束滿足的優化方法，通過動態調整策略調整澆次計劃，優化了煉鋼-連鑄兩階段故障引起的調度問題。Yu[8]等針對煉鋼-連鑄生產過程中轉爐故障引起的動態調度問題，建立了多目標非線性規劃模型，提出了兩階段動態最優調度方案，設計并開發了動態最優排產軟件系統，優化了煉鋼-連鑄生產過程中的加工時間和排產調度，縮短了爐次在工序間的等待時間。Hou[9]等研究了當生產車間遇到各種實時擾動時對生產車間的影響問題，并提出當機器故障時，通過基本的識別和分析可得出對機器故障引起的問題的調度方案。Jiang[10]等針對煉鋼-連鑄生產過程中產生的擾動事件引起的調度問題，提出了一種基于改進差分進化的多階段動態軟調度算法，解決了因擾動事件引起的全局調度問題和局部調度問題。錢承星[11]針對煉鋼-連鑄的實際生產過程中出現的動態擾動因素引起的調度問題，開發了煉鋼-連鑄生產調度決策支持系統，加入自適應規則改進差分進化算法，應用動態優化思想并嵌入記憶種群形成動態差分進化算法，以某大型鋼鐵企業為研究對象，將差分進化算法與標準差分進化算法和人工模擬算法進行比較，改進后的動態差分進化算法在煉鋼-連鑄生產調度過程中更具有實用性。趙月[12]先以生產調度為研究背景，對生產過程中出現的動態因素因其的動態優化問題進行分析，提出了動態差分進化算法，再以煉鋼-連鑄生產調度為研究對象，提出了增量式動態差分進化算法，當動態擾動事件發生時，快速響應并生成新的調度方案。

本文針對煉鋼-連鑄動態調度問題，提出一種以爐次最小化總完工時間、最小化總斷澆時間、最小化總等待時間和最小化總偏差量為優化目標，將拉格朗日插值算法與差分進化算法相融合，利用拉格朗日插值算法提高差分進化算法的局部搜索能力，通過自適應控制差分進化算法的進化參數，避免了算法陷入局部收斂的現象。最后，通過對國內某大型鋼廠的實驗數據進行仿真實驗，驗證了模型和算法的有效性。

1 問題描述

1.1 煉鋼-連鑄生產工藝過程

煉鋼-連鑄生產過程主要包含煉鋼、精煉和連鑄共3個環節。在同一個轉爐里經過煉鋼、精煉到連鑄階段結束統稱為一個爐次，多個爐次組合成一個澆次，同一個澆次必須持續澆鑄不能斷澆。

1.1.1 煉鋼

如圖1中所示，高爐(圖1中的BF)將生鐵和廢鋼進行熔化，通過轉爐(圖1中的LD)將生鐵和廢鋼按照鋼種的要求進行氧化和脫硫處理，調整其成分的含量到一定的范圍內且符合一定的出鋼溫度，即為鐵水。將鐵水通過高爐轉運到轉爐后，加入廢鋼，進行加熱處理去除雜質調整鋼水中的碳含量，將處理后的鋼水倒入鋼包中，通過吊車將其轉移至精煉爐中進行精煉。

圖1 煉鋼-連鑄生產工藝流程圖

1.1.2 精煉

精煉階段是為了進一步調整鋼水中的成分含量，去除雜質，添加所需的合金成分，生產出特定級別的鋼水。鋼水溫度需要保持在一定的范圍內，若鋼水的溫度過高或過低，都將影響連鑄階段的效果。由于不同級別的鋼種質量要求不同，鋼水包需經過的精煉爐的種類和數量也不同，根據鋼水包經過的精煉爐數量將精煉過程命名為一重精煉(例如一重精煉鋼水包只需經過1#RH精煉設備)、二重精煉(二重精煉鋼水包需經過2#RH和1#CAS兩個精煉設備)和三重精煉(三重精煉鋼水包需經過3#RH、2#CAS和1#KIP三個精煉設備進行處理)[13]。

1.1.3 連鑄

高溫鋼水經過連鑄機的處理，將熔融的金屬不斷澆入結晶器中，冷卻后的鑄件可通過結晶器的另一端拉出任意長度的鑄件，即具有一定鋼和規格的板坯。在連鑄過程中，需要進行連續澆鑄，若不能連續澆鑄而產生斷澆，會消耗過多的能源和時間。因此，為了提高生產效益、降低生產成本，連鑄過程要保持連續澆鑄。

1.2 煉鋼連鑄動態調度問題

煉鋼-連鑄動態調度問題可以歸類為作業車間調度問題[14]。煉鋼-連鑄生產調度問題實際上是對生產工序中運輸時間、生產工藝路徑存在的回環和最后階段是同一爐次連續加工的特殊生產問題[15]。而實際煉鋼-連鑄生產車間中，在滿足生產約束的前提條件下，需實時調整并確定某一爐次在某工序的某臺機器上進行加工及其開始時間和順序，盡可能的縮短爐次在煉鋼-連鑄生產過程中的總完工時間、總斷澆時間、總等待時間和時間偏差量，提高煉鋼-連鑄生產車間的生產效率，減少生產能耗。

1.3 數學模型

1.3.1 基本假設

煉鋼-連鑄生產過程是一個集離散和連續相混合的復雜過程。為了解決實際問題，通常使用數學模型對該問題進行描述。為確保生產過程的連續性，在正常的生產情況下，爐次依次在設備間傳遞且無重疊，連鑄機的拉速是恒定的，當遇到不可預測的擾動時，可在合理范圍內進行調節連鑄機拉速，且有初始調度計劃表。

1.3.2 符號定義

其中：

1.3.3 目標函數及約束條件

1)目標函數：

F=f1+f2+f3+f4

(1)

f1=minε1Cmax

(2)

(3)

(4)

(5)

2)約束條件：

(6)

(7)

(8)

?j∈Ji,k∈Mj,(i,i′)∈{(i,i′)|j∈Ji∩Ji′}

(9)

?p≠P,m∈Mq

bp=adpq,?p∈P

(10)

(11)

(12)

(13)

?i∈I,j∈Jj,m∈Mj,m′∈Mδ(i,j)

(14)

?i∈I,j∈Jj,m∈Mj

uijmaij≥uijmrm,?i∈I,j∈Jj,m∈Mj

(15)

(16)

(17)

(18)

(19)

uijm∈{0,1}

(20)

vpm∈{0,1}

(21)

(22)

式(1)表示目標函數由式(2)～(5)組成，其中，式(2)表示最小化總完工時間，式(3)表示最小化總斷澆時間，式(4)表示最小化總等待時間，式(5)表示最小化時間偏差量。式(6)表示在生產過程中爐次在各機器上僅可以被分配到一臺機器上進行加工；式(7)表示連鑄機上的一個澆次在同一時刻僅可以被分配到一臺連鑄機上澆鑄；式(8)表示任意一臺機器僅被允許一個爐次進行加工；式(9)表示表示連鑄機在同一時刻僅允許一個澆次進行澆鑄；式(10)表示連鑄機的開澆時間等于該連鑄機上第一個爐次開始澆鑄的時間；式(11)表示連鑄機的結束工作時間是該連鑄機上最后一個爐次的澆鑄結束時間；式(12)表示在同一個澆次中，后一爐次的澆鑄開始時間等于前一爐次在該連鑄機上的澆鑄結束時間與兩個爐次之間的斷澆時間的和；式(13)表示某一爐次的下一工序的開始時間等于前一工序的結束時間與工序間的運輸時間和等待時間之和；式(14)表示機器發生故障時該時間段內爐次不能在該機器上進行加工；式(15)表示爐次在各工序之間的加工開始時間不小于該機器上上一爐次的結束時間；式(16)表示煉鋼-連鑄生產調度的總完工時間；式(17)表示爐次在進行下一工序前的可等待時間范圍；式(18)表示爐次的加工時間范圍；式(19)表示連鑄上斷澆的時間范圍；式(20)表示爐次在工序上可分配到的機器數；式(21)表示澆次可被分配的機器數；式(22)表示對工序的開始加工時間、澆次的開始澆鑄時間和澆次的結束澆鑄時間沒有具體的限制。

2 改進差分進化算法的設計與求解

2.1 差分進化算法基本原理

差分進化算法(DEA，different evolution algorithm)由Storn和Price[16]于1995年提出的一種基于群體的全局優化算法[17]。差分進化算法通過模擬自然界生物種群的生存法則進化發展規律而形成的一種具有隨機啟發式的搜索算法。差分進化算法中，每個個體都有一個解向量，通過變異操作對種群個體進行差分，并將生成的差分向量與初始基向量進行交叉操作，通過選擇操作選取最優個體，并將該最優個體保存至下一代，最終生成新的種群，通過不斷的迭代，直到找到最優解。差分進化算法因結構簡單、容易實現、魯棒性強等特點，而被廣泛應用于各個領域[18]。

2.2 差分進化算法的基本流程

差分算法的流程如下[19]：

1)設置參數；

2)隨機產生初始種群；

3)對初始種群中個體計算適應度值；

4)判斷是否達到最大迭代次數。若達到，則結束循環；否則，繼續執行操作；

5)對未達到最大迭代次數的種群個體進行變異和交叉操作，將變異向量vi,g與父向基向量xi,g進行交叉操作，得到一個第j維的新個體，交叉操作公式如下：

(23)

其中：CR是交叉概率，jrand是維數[1,D]之間的均勻分布的隨機數。

6)將得到的新個體向量與基向量進行選擇操作，選取最優個體保留至下一代種群。選擇操作的計算公式為：

(24)

7)迭代數加1，轉至步驟4)。

2.3 拉格朗日插值

通過對同一物理量進行多個角度觀察,可得多個不同的觀測值,獲得的多個觀測值可由一個多項式表示,則該多項式稱為拉格朗日插值多項式[20]。即拉格朗日插值是在已知多個坐標點的情況下，通過坐標點獲得近似函數的一種建模方法[21]。

拉格朗日插值法基本原理：在需要插值的點附近隨機選取若干個合適的點，構造一個簡單的插值函數y=q(x)，且該構造的插值函數需通過隨機選取的插值點。在所選的插值點區間內將插值函數值作為原函數f(x)的值，使函數f(xi)=p(xi),i=1,2,3,…,n成立。拉格朗日插值法的實質是根據已知的選取的插值點構造一個插值函數，并利用該插值函數快速獲取原函數在該插值點上的位置，這種利用多個節點數據來構造插值基函數的方法稱為拉格朗日插值法[22-23]。

在區間[a,b]上，有n+1個點x0,x1,…,xn，且過該n+1個點的函數值為y0,y1,…,yn，對這n+1個點，每個xi均可得到其對應的函數值yi，公式如下：

(25)

式(25)中，Ln(x)為拉格朗日多項式；為次數不超過n的多項式，即插值基函數。此時，拉格朗日插值階數為n，滿足如下公式：

(26)

具體計算公式為：

(27)

將式(26)代入式(27)得到n次拉格朗日多項式的計算式為：

(28)

2.4 拉格朗日插值改進差分進化算法

利用拉格朗日插值法構建的近似函數是一個恰好穿過二維平面上若干個已知點的多項式函數，該函數可以通過已知的信息來推測未知信息，獲取更優解。已知坐標點(x0,y0),(x1,y1),…,(xD,yD),其中xi為種群個體，yi為種群個體的適應度值。通過已知的多個解建立近似函數，得到n次拉格朗日插值多項式：

(29)

本文取n∈{0,1,2}，代入式中得到拋物線式插值，將其簡化成二次函數的數學模型如下：

fn(x)=ax2+bx+c

(30)

式(30)中：a、b及c為方程式的系數，其計算過程分別為:

(31)

(32)

c=c0+c1

(33)

其中：

n0=x0-x1

(34)

n1=x1-x2

(35)

n2=x2-x0

(36)

(37)

(38)

(39)

2.5 自適應調整差分進化算法搜索方向

將當前種群中各個個體進行適應度函數值大小排序，將適應度函數值小的個體放在前面，并將前m(m∈[1,2,…,NP])個個體定義為當前種群的優質解。通過隨機選取的種群中的優質解來引導搜索方向，保證了前期種群的多樣性，使得迭代后期尋優結果趨于最優解。變異策略DE/rand-to-best/1的具體計算公式如下所示：

(40)

(41)

式(41)中，g表示當前進化代數，gmax表示最大進化代數，s(x)表示大于x的最小整數。m在種群的前期搜索速率較慢，算法可在較大的范圍內尋求最優解，增強了算法的局部搜索能力；而在種群后期搜索速率較快，通過優質解中的最優解得到位置分布。當m=1時，xmbest,g=xbest,g為當前種群最優解，算法更傾向于在全局最優解附近搜索，從而加快了算法的收斂速度。

為了利用拉格朗日插值優化差分進化算法搜索局部最優值，本文以當前變異的最優個體和最優個體附近的隨機生成的兩個個體從而得到3個點x0、x1、x2，其中，x0為最優個體，x1、x2由下列公式生成：

x1=x0-δ

(42)

x2=x0+δ

(43)

δ=a×(rand-0.5)

(44)

其中：a為極小系數，本文設置a=0.01。

利用二次拉格朗日插值可獲得一條經過x0、x1、x2三點的二次函數，通過對二次函數的計算可獲得全局最優解。為了平衡全局搜索和局部搜索，引入權重w加以控制，權重的計算表達式如下：

(45)

其中：分別設置wmax、wmin為0.9和0.4；t為種群迭代次數；maxDT為當前種群最大迭代次數。w的選取決定了種群的搜索能力，w越小時，其種群的全局搜索能力越強，反之局部搜索能力越強。在拉格朗日插值算法改進差分進化算法的過程中，權重系數w在種群前期的主要是為了擴大種群搜索范圍，而在迭代后期，權重系數w的引入能夠加快種群的局部搜索速度。

2.6 改進的差分進化算法流程

如圖2所示，拉格朗日插值改進的差分進化算法具體步驟如下：

圖2 LGDE算法流程圖

1)設置算法的種群大小NP，最大進化代數為maxDT以及其他進化參數。初始化種群，計算各個個體的適應度，記錄最優個體xbest以及f(xbest)；

2)判斷結果是否達到maxDT，若是退出計算，否則，進入步驟3)；

3)計算當前權重w，若w≤0.75，則進入步驟4)，否則進入步驟5)；

4)取xbest和附近兩點x1、x2，做拉格朗日插值計算，求得最小值min，計算min的適應度值并與xbest的適應度值相比較，當f(xbest)f(min)，用min替換xbest；

5)使用DE/rand-to-best/1策略進行變異操作；

6)進行交叉和選擇操作，并計算種群中每個個體的適應度值，迭代次數加1；

7)判斷是否滿足結束條件，若是，則結束循環;否則，轉至步驟3)。

3 實驗結果與分析

表1是某大型鋼廠的實際生產數據，包含3個澆次計劃、10個爐次計劃和兩種精煉方式。以表1中的澆次計劃進行仿真試驗。

表1 澆次計劃

將本文所提出的改進的差分進化算法與標準差分進化算法對上述問題求解，設置種群規模為50，變異算子為0.5，交叉概率為0.3，迭代次數為1 000，對數據進行50次獨立實驗，計算每一代目標函數值，獲得折線如圖3所示，改進后的差分進化算法的收斂曲線均優于標準差分進化算法的收斂曲線，證明了本文所提的改進后的差分進化算法有較好的收斂性。

圖3 改進后的差分進化算法的收斂曲線

在實際的生產車間中，通過對該鋼廠實際生產的相關數據的提取，當機器運行至7∶30分時，2#LD轉爐突然出現故障，導致后面的爐次不能繼續在該轉爐上進行加工，需要分配新的轉爐，如圖4，2#LD轉爐出現故障，導致在該轉爐上還未開始加工的第7爐次和第4爐次開工延遲，從而導致第7爐次和第4爐次在連鑄機上出現斷澆，動態調整前的調度甘特圖如圖4所示。

圖4 動態調度調整前的甘特圖

通過改進的差分進化算法對原始調度計劃進行調整，對故障下導致延遲的第7爐次和第4爐次重新分配新的轉爐機器，調整后的甘特圖如圖5所示。

圖5 動態調度調整后的甘特圖

通過仿真實驗結果顯示，本文提出的改進的差分進化算法能夠有效解決煉鋼連鑄生產過程中轉爐出現故障的擾動事件，并生成新的較優的調度計劃表。

4 結束語

1)針對煉鋼-連鑄生產動態調度問題，結合某大型鋼廠的實際生產車間的數據，以爐次在煉鋼-連鑄生產過程中最小化總完工時間、最小化總斷澆時間、最小化爐次間總等待時間和最小化總偏差量為優化目標，建立了煉鋼-連鑄動態調度數學模型。

2)在給定原始調度計劃表的前提下，提出了以拉格朗日插值改進差分進化算法的方法來求解煉鋼-連鑄動態調度問題，并提出了自適應調整策略和權重系數的判斷，來平衡全局搜索和局部搜索。

3)以某大型鋼廠的實際生產數據為研究對象，建立數學模型并進行仿真實驗，結果表明，所提出的算法能夠有效地縮短爐次在煉鋼-連鑄生產過程中的總完工時間，當實際生產現場出現擾動事件時，及時響應并做出相應調整，確保了煉鋼-連鑄生產車間的順利進行。本文所提的改進的差分進化算法未來可更多應用于多組合多約束優化問題。