文化基因算法求解多工藝路線煉鋼-連鑄生產調度問題

李 玲，唐秋華，張利平

(武漢科技大學機械自動化學院，湖北 武漢，430081)

文化基因算法求解多工藝路線煉鋼-連鑄生產調度問題

李 玲，唐秋華，張利平

(武漢科技大學機械自動化學院，湖北 武漢，430081)

針對包含多工藝路線的煉鋼-連鑄生產調度問題，綜合考慮生產過程中的多種約束條件，以文化基因算法為基礎提出一種新的求解方法。在文化基因算法設計過程中，對于不同工藝路徑的機器選擇，采用啟發式規則指導的機器指派方法；在算法優化中，通過引入基于連接矩陣的相似工件塊交叉方法和基于基因位全插入的鄰域搜索算子，從全局和局部搜索角度全面提高算法性能。最后，通過對多組算例進行對比分析，驗證了本文算法的可行性和優越性。

煉鋼-連鑄；生產調度；文化基因算法；多工藝路線；啟發式規則；鄰域搜索

鋼鐵生產中的煉鋼-連鑄階段操作過程復雜，工藝約束條件多，是生產調度的難點。在煉鋼車間實際生產中，往往由于鋼種不同而需要多種工藝路線混合作業，因此有必要針對該生產狀況下的煉鋼-連鑄調度問題進行研究。

煉鋼-連鑄生產調度問題的研究方向可大致分為最優化方法、智能算法和啟發式方法三類。Xuan等[1]和Mao等[2]分別建立了煉鋼-連鑄生產調度問題的整數規劃模型，并基于拉格朗日松弛方法進行求解。葉云等[3]針對具有多緩沖的煉鋼-連鑄生產調度問題，建立了基于單元特定事件的連續時間混合整型線性規劃模型并進行求解。李鐵克等[4]以混合流水車間調度理論為基礎研究煉鋼-連鑄調度問題，結合線性規劃方法提出一種兩階段遺傳算法。馬文強等[5]建立了煉鋼-連鑄生產調度數學模型，并提出一種混合教與學優化算法進行求解。孫亮亮等[6]根據各澆次的鑄機選擇結果來構造澆次集合，設計了一種基于啟發式規則的深度優先搜索算法進行連鑄過程調度。

上述研究針對不同生產狀況下的煉鋼-連鑄問題都提出了有效的調度方法。但是，除文獻[5]以外，其余文獻研究的都是確定的單一工藝路線條件下的煉鋼-連鑄調度。例如，在文獻[1]、[4]、[6]中，加工工藝路線是煉鋼-精煉-連鑄；文獻[2]中的工藝路線為煉鋼-精煉(RH精煉+LF精煉)-連鑄；文獻[3]中的工藝路線是煉鋼-精煉(AOD精煉+LF精煉)-連鑄。上述文獻研究的工藝路線具有單一性，即每個爐次所經過的加工工藝路線均相同。然而在實際生產中，由于訂單日趨多樣化，工藝路線混合生產逐漸成為常態，故各鋼包的工藝路線可以有多種。

本文針對多工藝路線煉鋼-連鑄生產調度問題，以文化基因算法為基礎，考慮不同工藝路線中機器選擇的不同，采用啟發式規則進行機器指派。另外，在算法設計中通過相似工件塊單點交叉的方法更有效地保留精英個體中高性能的工件組合,并采用鄰域搜索等方式來提高算法的優化性能。最后通過多組算例對該算法進行測試，并與遺傳算法進行結果對比，以檢驗本文算法的有效性。

1 多工藝路線煉鋼-連鑄生產調度

1.1 工藝路線

鑒于煉鋼和精煉工藝的多樣性，不同煉鋼廠的生產過程有所差異，本文研究的煉鋼-連鑄工藝過程源于武漢某鋼鐵公司，如圖1所示，其工藝流程包括轉爐煉鋼(LD)、吹氬(AR)、鋼包精煉處理(LF)、真空脫氣(RH)、回轉臺吊裝(CW)和連鑄(CC)多個階段，每個階段又包含若干臺具有相同處理能力的并行機。

圖1 煉鋼-連鑄多工藝路線流程示意圖

由于鋼種成分及規格要求存在差異，不同鋼種的工藝路線可能不同，如重軌鋼、簾線鋼等品質要求較低的鋼種，生產過程只需要經過LF或RH精煉，而如硅鋼等高品質鋼種，往往需要經過多重精煉。本文根據企業實際情況，考慮了4種常見的工藝路線，分別為LD-LF-CW-CC、LD-AR-CW-CC、LD-LF-RH-CW-CC和LD-RH-CW-CC。

1.2 煉鋼-連鑄生產調度

煉鋼-連鑄生產屬于流水作業，必須滿足流水作業車間調度的一般性約束。同時煉鋼生產具有高溫作業特性，因此各工序間需要連續加工。在連鑄之前的工藝階段，鋼水以爐次為單位，通過鋼水包經由天車進行轉運，可在同一階段任意機器上進行加工。在連鑄階段，由于鑄機的工藝約束，通常要求若干爐成分相同或近似的爐次組成一個澆次。屬于同一澆次的各爐次必須在同一臺鑄機上進行連澆連鑄，即煉鋼-連鑄生產在最后階段通常以澆次為單位實行批量化作業。

煉鋼-連鑄生產調度是在澆次任務(包括各澆次的爐次數)、設備狀況已知的條件下，確定各爐次在各階段的機器選擇以及開始、結束時間，同時要滿足前述各項約束。常見的生產調度目標主要包括最小化最大完工時間、最小化總完工時間、最小化機器等待時間、最大化設備利用率等。本文選取最小化最大完工時間作為優化目標。

2 算法設計

2.1 文化基因算法

文化基因算法[7](memetic algorithm，MA)是一種模擬社會文化進化的新型智能算法。該算法認為模擬生物進化機制的變異操作屬于含有一定噪聲的爬山搜索，在進化過程的眾多變種中通過一次簡單擾動來提高整體性能具有很大的盲目性。因此，在機理上文化基因算法認為變異過程需要大量“專業知識”支撐，在實際操作中則通過引入局部啟發式搜索實現。

文化基因算法強調局部搜索算子的作用，能夠結構性優化算法性能，因此在生產調度領域得到了大量應用。特別是在解決實際工程問題中，通過引入啟發式規則指導搜索方向可以大大提高算法的性能和效率。針對具有多工藝路線的煉鋼-連鑄生產調度問題，本文以文化基因算法為基礎進行求解，將煉鋼-連鑄調度問題的特性融入編碼、解碼過程和算子設計中，以保證算法的可行性。

2.2 針對煉鋼-連鑄調度問題的算法求解

多工藝路線條件下，由于不同澆次的生產路徑不同，確定各任務的機器選擇也變得更為復雜。以澆次為單位，根據算法生成的澆次順序來依次確定各澆次內爐次的機器選擇是最簡單的思路，但這種方法在對當前澆次進行機器選擇時沒有有效信息作為參考，只能以貪婪的方式進行決策，而對后續澆次的決策不具有前瞻性。同時，在各階段有并行設備的情況下，必然存在兩個澆次在連鑄前的設備中交錯加工的情況，此時由于前一個澆次的分配已經確定，導致設備在未來的若干個時間區間上提前被占用，這就使得后續澆次的可行開澆時間難以確定。

本文采用文化基因算法，利用自然數編碼方式產生澆次序列，結合倒推方法和啟發式規則進行解碼，并根據問題特性，采用基于相似工件塊的單點交叉方法和局部搜索算子進行優化求解。

2.3 面向混合流水作業的編碼與解碼

在多工藝路線混合的生產條件下，不同澆次的階段數不同，機器選擇情況復雜，故先通過算法確定各澆次的開澆時間順序，再通過啟發式規則實現解碼。

編碼：由于算法只用于確定澆次順序，故采用基本的自然數編碼方式，基因位順序即為澆次順序，基因位上的值即為該位置的澆次編號。

解碼：為滿足各澆次在鑄機上的連續澆鑄約束，本文采用倒推的方法，以澆次序列的逆序作為各澆次開澆時間的順序，利用最早可用機器優先規則將其安排在鑄機上；然后以爐次為單位，同時采用最早完工時間優先規則和最早可用機器優先規則，將各爐次任務以倒排的方法分配在鑄機前的各個工序上；最后按正常工藝順序將整個調度的計劃時間進行翻轉，得到可行的調度計劃表。

2.4 面向多工藝路線的全局搜索算子

選擇操作：由于本研究的優化目標為最小化問題，故選取最大完工時間的倒數作為適應度函數值f，以輪盤賭方式進行選擇。

交叉操作：由于工藝路線的多樣性，澆次之間的組合必然在很大程度上影響著整個生產計劃的最大完工時間。研究表明[8]，在種群進化過程中會逐步形成許多高性能的工件組合，稱為工件塊，這些工件塊可能出現在不同染色體的同一位置或不同位置。因此，保留高性能染色體上重復出現的工件組合能更好地保留較優染色體的有用信息，有助于整個種群的進化。如果交叉操作破壞了這些工件塊，生成低劣后代染色體的可能性就較大。

本文采用一種相似工件塊單點交叉(similar block one-point crossover, SBOPX)的方法，首先從當前種群中選出一定比例的精英個體，并從這些精英染色體中提取工件塊信息。記Λ=[λj′,j]m×m為工件的連接矩陣，其中λj′,j表示在精英染色體中工件對(j′,j)出現的次數。初始時令Λ=[0]m×m，逐步掃描每一個精英個體，掃描結束后如果λj′,j>1，就稱工件對(j′,j)為工件塊。

例如，有3個精英個體分別為：

π1={3,4,7,5,2,8,6,9,1} ，

π2={2,1,3,4,5,6,9,8,7},

π3={6,3,2,1,9,8,7,5,4},

可計算得到工件的連接矩陣如表1所示。

表1 連接矩陣

基于連接矩陣，SBOPX的操作步驟如下，結果如圖2所示。

(1)根據連接矩陣查找父代染色體上的工件塊，直接把它們復制到相應子代染色體的相同位置上。

(2)隨機產生一個交叉點。

(3)復制父代染色體1位于交叉點之前的部分到子代染色體1的相同位置上，將子代染色體1缺失的工件從父代染色體2上依次復制到空余位置。

(4)復制父代染色體2位于交叉點之前的部分到子代染色體2的相同位置上，將子代染色體2缺失的工件從父代染色體1上依次復制到空余位置。

圖2 SBOPX的操作過程

2.5 面向多工藝路線的局部搜索算子

多工藝路線混合生產條件下，機器使用情況呈現出很強的無規律性，通過傳統調度方法和經驗方法都難以制定出高效的調度方案。在文化基因算法設計中，通過采用基因位全插入的大規模局部搜索算法系統地優化鄰域結構，提高設備利用率，同時有效防止算法陷入局部最優。局部搜索過程如下：

(1)令i=1:PS(PS為種群規模)，對每一條染色體生成全局搜索后的一個初始解π。

(2)令n=1(n為局部搜索次數)。

(3)隨機從π中無重復地抽取一個工件，將該工件分別插入到π的所有位置(原位置除外)。評價所得到的排列，令π′為其中最好的排列。

(4)若f(π′)

2.6 算法偽代碼

//初始化

定義鄰域搜索次數N；

種群大小PS；

最大澆次數CAST_NUM；

fori=1 toPSdo

隨機生成所有染色體；

end for

while (計算時間未滿足終止條件) do

//計算適應度函數

fori=1 toPSdo

Fitness(i)=Fitfun(Parent(i));

end for

Population=Sort(Parent(i)); //將種群按適應度值降序排列

//全局搜索算子

fori=1 toPSdo

Parent(i)=Roulette Selection(Population);//輪盤賭選擇

end for

for(j=1;j

(Offspring(j),Offspring(j+1))=SBOPX(Parent(i)，Parent(i+1));//交叉

end for

//局部搜索算子

定義π為全局搜索后的染色體，作為鄰域搜索的初始解；

fori=1 toPS

n=1;//局部搜索次數

while(n

隨機選擇一個工作(沒有重復)；

π′=Neighborhood search(π);//對初始解進行鄰域搜索

if Fitness(π′)

then break;//跳出循環

elsen=n+1;

end while

end for

Population=Sort(Offspring);//更新原種群

end while

3 算法測試與結果分析

為了驗證所提出算法的性能，分別采用實際生產數據和隨機模擬生成的數據進行測試計算，并與遺傳算法的計算結果進行比較。遺傳算法(GA)是智能算法領域最為經典也最為有效的算法之一，在流水車間調度中得到了廣泛應用。本文作為對比實驗的遺傳算法是根據文獻[9]中遺傳算法的結構進行設計的，在該遺傳算法的基礎上，對交叉策略又進行了相應改進。所有算法均采用C語言編程，程序運行環境為CPU 3.00 GHz，內存為2 GB。

3.1 參數設置

由于算法性能受參數影響較大，故需要通過多因素方差分析確定最優的參數組合。對于文化基因算法，共考慮種群規模、交叉概率、精英個體比例三個參數，其中種群規模設置(20,40,60)三個水平，交叉概率設置(0.7,0.8,0.9)三個水平，精英個體比例設置(0.2,0.5,0.8)三個水平。設計正交試驗，對每個參數組合單獨運行10次，取其平均值作為最終結果，然后用SPSS軟件對所求結果進行方差分析。結果表明，對目標函數的影響程度上，種群規模>交叉概率>精英個體比例，最終選取的目標水平如下：種群規模為60，交叉概率為0.9，精英個體比例為0.8。

為保證對比實驗的公平性，遺傳算法進行同樣的參數選擇。對遺傳算法，考慮種群規模、交叉概率和變異概率三個參數，前兩個因素水平設置同上，變異概率取(0.05,0.1,0.2)三個水平，經多因素方差分析，得到最佳的因素水平組合：種群規模為40，交叉概率為0.7，變異概率為0.1。

3.2 實際生產數據測試結果與分析

本文所采用的實際生產數據參照文獻[5]，如表2所示，測試結果如表3所示。

表2 實例數據

表3 實例測試結果

由表3可以看到，文化基因算法獲得的最優解要好于遺傳算法獲得的最優解。同時，與文獻[5]中算法獲得的最優解(1976 min)相比，文化基因算法獲得的結果優化了5.72%，可見本文算法中基于問題屬性設計的解碼方式及算子結構有效提升了算法性能。

3.3 隨機生成數據測試結果與分析

為了進一步驗證文化基因算法的有效性，本文隨機生成規模不同的若干組數據進行測試。澆次數在(5,40)之間隨機產生，共生成8組案例，每個澆次的爐次數在(3,7)之間隨機產生，各工序的加工時間根據實際情況在合理范圍內隨機產生。為保證算法對比的公平性，參照文獻[10]，各算法均采用計算時間t為終止條件：t=200p(q/2) ms，其中p為任務數、q為機器數。計算結果如表4所示。

表4 隨機生成數據測試結果

由表4可見，雖然對于小規模案例，GA和MA兩種算法都能得到相同最優解，但隨著問題規模的增大，MA所得最優解及均值都要好于GA計算結果。總之，在相同的計算時間內，文化基因算法明顯改進了解的質量，其性能優于遺傳算法。

4 結語

本文針對具有多工藝路線的煉鋼-連鑄生產調度問題，設計了一種高效的文化基因算法。該算法考慮實際問題特性，引入基于工件連接矩陣的相似工件塊單點交叉方法和以基因位全插入操作為核心的局部搜索方法，有效提高了算法性能。通過設計不同規模的測試算例，并與遺傳算法進行結果對比，驗證了本文算法的可行性和高效性。

[1] Xuan Hua, Tang Lixin. Scheduling a hybrid flowshop with batch production at the last stage[J]. Computers and Operations Research,2007,34(9):2718-2733.

[2] Mao Kun, Pan Quanke, Pang Xinfu, et al. A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process[J]. European Journal of Operational Research, 2014, 236(1):51-60.

[3] 葉云, 唐秋華, 易磊, 等. 基于單元特定事件的多緩沖煉鋼連鑄生產調度建模[J].武漢科技大學學報， 2013,36(2):104-107.

[4] 李鐵克,蘇志雄. 煉鋼連鑄生產調度問題的兩階段遺傳算法[J]. 中國管理科學,2009,17(5):68-74.

[5] 馬文強,張超勇,唐秋華,等. 基于混合教與學優化算法的煉鋼連鑄調度[J]. 計算機集成制造系統,2015,21(5):1271-1278.

[6] 孫亮亮,劉煒,柴天佑. 基于深度優先搜索算法的連鑄過程調度方法的研究[J].控制理論與應用, 2010,27(12):1705-1710.

[7] Moscato P. An introduction to population approaches for optimization and hierarchical objective functions: a discussion on the role of tabu search[J]. Annals of Operations Research, 1993,41(2):85-121.

[8] Ruiz R, Maroto C, Alcaraz J. Two new robust genetic algorithms for the flowshop scheduling problem[J]. Omega, 2006,34(5):461-476.

[9] 秦艷. 改進交叉策略的GA在流水車間多目標調度中的應用[J]. 現代制造工程,2010(12):29-32.

[10]Pan Quanke, Ruiz R. An estimation of distribution algorithm for lot-streaming flow shop problems with setup times[J]. Omega, 2012,40(2):166-180.

[責任編輯 尚 晶]

Memetic algorithm for steelmaking-continuous casting production scheduling
with multiple process routes

LiLing,TangQiuhua,ZhangLiping

(College of Machinery and Automation, Wuhan University of Science and Technology, Wuhan 430081, China)

On the basis of memetic algorithm, a new method considering the multiple constrains in production is put forward to solve the scheduling problem of steelmaking-continuous casting production with multiple process routes. During the design of memetic algorithm, the heuristic rules guided assignment method is used to choose the machine for different process routes. Then the similar block one-point crossover operator based on the connection matrix and the neighborhood search operator based on a fully inserted method are adopted to improve the performance of global and local searching. Finally, contrastive analysis of several cases verifies the feasibility and superiority of the proposed algorithm.

steelmaking-continuous casting; production scheduling; memetic algorithm; multiple process route; heuristic rule; neighborhood search

2016-09-29

國家自然科學基金資助項目(51275366,51305311)；高等學校博士學科點專項科研基金課題(博導類)(2013421911002)；中國博士后科學基金資助項目(2013M542073).

李 玲(1991-)，女，武漢科技大學碩士生.E-mail: 1299105704@qq.com

唐秋華(1970-)，女，武漢科技大學教授，博士生導師.E-mail: tangqiuhua@wust.edu.cn

10.3969/j.issn.1674-3644.2017.01.004

TF087；TP29

A

1674-3644(2017)01-0017-06