彭琨琨,李新宇,高 亮,鄧旭東

(1.武漢科技大學(xué) 管理學(xué)院,湖北 武漢 430065； 2.華中科技大學(xué) 機(jī)械科學(xué)與工程學(xué)院,湖北 武漢 430074)

0 引言

鋼鐵工業(yè)為很多重要工業(yè)提供原材料，是國民經(jīng)濟(jì)重要的基礎(chǔ)產(chǎn)業(yè)。目前，我國鋼鐵工業(yè)正面臨著高端供給不足等問題。煉鋼-連鑄(Steelmaking-Continuous Casting, SCC)是鋼鐵工業(yè)生產(chǎn)中的瓶頸[1]，高效的SCC調(diào)度算法可較大地提高鋼鐵工業(yè)的生產(chǎn)效率。SCC調(diào)度問題是一個復(fù)雜的工業(yè)調(diào)度問題[2]，屬于NP難組合優(yōu)化問題。因此，該研究具有重要的工程意義和理論價值。

已有SCC調(diào)度算法中，智能優(yōu)化方法得到了廣泛應(yīng)用，例如，文獻(xiàn)[3]和文獻(xiàn)[4]分別提出了求解SCC調(diào)度和重調(diào)度的果蠅優(yōu)化算法，文獻(xiàn)[5]設(shè)計(jì)了差分進(jìn)化算法，在已有的SCC智能優(yōu)化調(diào)度算法中，人工蜂群算法[6-7]得到了較多關(guān)注。此外，拉格朗日松弛方法[2]和啟發(fā)式[8-9]也吸引了很多研究。

當(dāng)前SCC調(diào)度算法的研究很多都將連鑄階段的加工時間視為固定。然而，實(shí)際生產(chǎn)過程中，連鑄機(jī)的加工速度可在一定范圍內(nèi)調(diào)整，即爐次加工時間在一定范圍內(nèi)調(diào)整[10]，這可增加生產(chǎn)和調(diào)度的柔性，相應(yīng)的SCC調(diào)度問題稱為可調(diào)加工時間SCC調(diào)度問題。與考慮固定加工時間SCC調(diào)度問題研究相比，當(dāng)前針對可調(diào)加工時間SCC調(diào)度的研究相對較少。例如，文獻(xiàn)[10]設(shè)計(jì)了針對考慮允許可跳躍階段的可調(diào)加工時間SCC調(diào)度的改進(jìn)遺傳算法，文獻(xiàn)[11]研究了拉格朗日啟發(fā)式重調(diào)度方法。

灰狼優(yōu)化(Grey Wolf Optimizer, GWO)算法是一種較新且高效的群智能優(yōu)化算法，由Mirjalili等[12]于2014年提出，目前已引起很多學(xué)者的關(guān)注，已成功求解鑄造生產(chǎn)調(diào)度[13]、焊接車間調(diào)度[14-15]等NP難組合優(yōu)化問題。

本文借鑒GWO算法的優(yōu)良特性，結(jié)合可調(diào)加工時間SCC調(diào)度的問題特征，研制了求解該問題的GWO算法。從解碼方法、種群初始化、基于多操作的搜索算子及重啟操作等角度著手設(shè)計(jì)，較大地提升了GWO算法解決可調(diào)加工時間SCC調(diào)度的求解性能。

1 可調(diào)加工時間煉鋼-連鑄調(diào)度問題

SCC生產(chǎn)過程主要包含煉鋼階段、精煉階段和連鑄階段3個順序的生產(chǎn)階段[1]。煉鋼階段主要利用轉(zhuǎn)爐將高爐的鐵水轉(zhuǎn)化為鋼水，去除某些雜質(zhì)；精煉階段使用精煉設(shè)備對鋼水進(jìn)行精煉，進(jìn)一步去除某些雜質(zhì)，調(diào)節(jié)鋼水的成分和溫度，該階段可能包含多個精煉階段，稱為多重精煉；而連鑄階段則使用連鑄機(jī)將精煉階段生成的鋼水連續(xù)澆鑄生成板坯[9,16]。煉鋼階段和精煉階段的最小工作單元為爐次，相當(dāng)于車間調(diào)度問題中的工件，而連鑄階段的最小工作單元為澆次，澆次為一組爐次的集合[16-17]。如圖1所示為SCC生產(chǎn)過程簡單示意圖。圖中：從左往右依次為煉鋼階段、3個精煉階段、連鑄階段。其中：煉鋼階段包含3臺轉(zhuǎn)爐，分別為1#LD、2#LD和3#LD；第1個精煉階段包含3臺精練設(shè)備，分別為1#RH、2#RH和3#RH，類似地，第2、3個精煉階段也各自包含3臺精練設(shè)備；連鑄階段包含3臺連鑄機(jī)，分別為1#CC、2#CC和3#CC。

可調(diào)加工時間SCC調(diào)度問題可描述如下，給定一定的假設(shè)條件(例如已事先給定各澆次在連鑄機(jī)上的分配情況等)，要求編制一個滿足實(shí)際生產(chǎn)狀況和多個復(fù)雜約束的優(yōu)化調(diào)度方案，其中各爐次在連鑄階段的加工時間可在一定范圍內(nèi)調(diào)整[10]，該優(yōu)化調(diào)度方案給出了在煉鋼階段、精煉階段和連鑄階段，各爐次分別在何時開工、完工，以及各爐次在煉鋼階段和精煉階段在哪臺機(jī)器上加工。本文考慮的優(yōu)化目標(biāo)為最小化平均逗留時間、澆次的提前連鑄時間、澆次的滯后連鑄時間，考慮的復(fù)雜約束包括：同一個澆次內(nèi)的爐次在連鑄階段必須連續(xù)加工；對于在同一臺機(jī)器上加工的兩個爐次，只有在前者完成之后，后者才能開始加工等約束[1]。

2 解決可調(diào)加工時間煉鋼-連鑄調(diào)度問題的灰狼優(yōu)化算法

基本GWO算法是針對連續(xù)優(yōu)化問題而設(shè)計(jì)的，不能直接求解可調(diào)加工時間SCC調(diào)度問題這一組合優(yōu)化問題，本文專門裁剪了GWO算法來解決該問題。下面首先介紹了基本GWO算法，隨后給出了本文設(shè)計(jì)的GWO算法，依次從編碼、新解碼方法、種群初始化、社會等級分層、基于多操作的搜索算子、重啟操作、算法框架等7個方面來進(jìn)行詳細(xì)說明。

2.1 基本灰狼優(yōu)化算法

基本GWO算法[12]將一個初始灰狼種群作為搜索起點(diǎn)，接著執(zhí)行社會等級分層，隨后執(zhí)行搜索算子、社會等級分層的循環(huán)進(jìn)化操作，直至達(dá)到算法終止條件[12]。其主要思想是不斷更新種群中的最好的3個解：最好解α、次好解β、第三好解δ，并利用它們來引導(dǎo)其他解的進(jìn)化搜索。

2.2 編碼

本文使用了爐次排序?qū)膺M(jìn)行編碼，爐次順序?qū)?yīng)于爐次的操作順序，編碼中的每一個數(shù)字對應(yīng)一個爐次。

2.3 解碼方法

解碼是實(shí)現(xiàn)解與調(diào)度方案之間映射的橋梁，對于GWO算法非常關(guān)鍵。本文考慮了問題特征，基于文獻(xiàn)[1]和文獻(xiàn)[9]的工作，提出一種新的解碼方法，包含正向解碼、連鑄階段加工時間調(diào)整、反向解碼3個階段。本文的編碼方法與文獻(xiàn)[1]編碼方法的不同主要在于：文獻(xiàn)[1]中的編碼方法將連鑄階段加工時間視為固定，僅包括正向解碼和反向解碼，而本文的編碼方法在文獻(xiàn)[1]中的編碼方法基礎(chǔ)上，考慮了連鑄階段加工時間可調(diào)，解碼時在正向解碼與反向解碼之間增加了連鑄階段加工時間調(diào)整。具體描述如下：

步驟1正向解碼。

在煉鋼階段和精煉階段，按編碼中爐次排序依次選擇爐次，為其選擇最早的可用機(jī)器，在連鑄階段，按各澆次中的爐次順序加工。

步驟2連鑄階段加工時間調(diào)整。

步驟2.1 連鑄階段加工時間調(diào)整I。

在連鑄階段，對每個澆次，如果任意兩個連續(xù)爐次(假設(shè)i和i+1)之間存在斷澆，則爐次i的加工時間增加min{Δti,CBi,i+1}，其中：Δti為爐次i的當(dāng)前加工時間最大可增加值，CBi,i+1為爐次i和i+1之間的斷澆時間。隨后更新CBi,i+1和Δti。

步驟2.2 連鑄階段加工時間調(diào)整Ⅱ。

在連鑄階段，對每個澆次，如果不存在斷澆，則轉(zhuǎn)下一澆次，否則，執(zhí)行以下步驟：

(1)計(jì)算該澆次的斷澆時間之和，記為CBSum。

(2)進(jìn)而計(jì)算addAver=CBSum/n，其中n為該澆次中首爐次至最后一個斷澆之間的爐次數(shù)目。

(3)對前n-1個爐次(假設(shè)為j)，將其加工時間增加min{Δtj,addAver}，將第n個爐次的加工時間增加min{Δtn,CBSum-addAver×(n-1)}，隨后更新CBi,i+1。

步驟3反向解碼。

步驟3.1 在連鑄階段，對每個澆次，如果不存在斷澆，則轉(zhuǎn)下一澆次，否則，從該澆次的倒數(shù)第二個爐次開始，同時右移其完工時間和開工時間，使其完工時間等于下一個爐次的開工時間。

步驟3.2 在精煉階段，對所有爐次，按編碼中的爐次順序，從倒數(shù)第一個爐次開始，將其完工時間和開工時間右移。

步驟3.3 在煉鋼階段，對所有爐次執(zhí)行類似步驟3.2的操作。

2.4 種群初始化

好的初始種群很可能有助于加快GWO算法的收斂。本文設(shè)計(jì)了如下方法以得到具有一定質(zhì)量且保持多樣性的初始種群。

步驟1根據(jù)事先定義的澆次的計(jì)劃開工時間及每個澆次中各爐次的順序，獲得每個爐次在連鑄階段的開工時間，按非降排序[1]。得到的爐次排列記為P1。

步驟2對P1重復(fù)執(zhí)行N次Multiswap算子，生成的N個解記為P2,…,PN+1。

步驟3對P1重復(fù)執(zhí)行N次Swap算子，生成的N個解記為PN+2,…,P2N+1。

步驟4對P1重復(fù)執(zhí)行N次Pairwiseexchange算子，生成的N個解記為P2N+2,…,P3N+1。

步驟5對爐次進(jìn)行隨機(jī)排序，重復(fù)執(zhí)行M-3N-1次，生成剩余的M-3N-1個初始解。

2.5 社會等級分層

更新歷史最好解α、歷史次好解β及歷史第三好解δ，即若當(dāng)前解Ptj優(yōu)于α，設(shè)置δ=β，β=α，α=Ptj；若Ptj僅優(yōu)于β，設(shè)置δ=β，β=Ptj；若Ptj僅優(yōu)于δ，設(shè)置δ=Ptj。

不同于基本GWO算法，只有在整個種群更新完畢后，才執(zhí)行社會等級分層。在本文GWO算法中，一旦得到一個新解，就執(zhí)行社會等級分層。目的在于及時更新α、β、δ，提高GWO算法的集中性。

2.6 基于多操作的搜索算子

搜索算子是GWO算法的關(guān)鍵和核心，直接決定了GWO算法的搜索性能。本文專門設(shè)計(jì)了一種基于多操作的搜索算子，可在一定程度上實(shí)現(xiàn)集中性和多樣性的平衡。

給定當(dāng)前解Ptj，基于多操作的搜索算子可描述如下：

步驟1在區(qū)間[0,1]內(nèi)生成一個隨機(jī)數(shù)rd1，若rd1<1/3，轉(zhuǎn)步驟3執(zhí)行基于部分映射交叉操作(Partially Mapped Crossover, PMX)的操作算子1；若1/3≤rd1<2/3，轉(zhuǎn)步驟4執(zhí)行基于PMX的操作算子2；若2/3≤rd1<1，轉(zhuǎn)步驟5執(zhí)行局部搜索算子。

步驟2在區(qū)間[0,1]內(nèi)生成一個隨機(jī)數(shù)rd2，若rd2<1/3，設(shè)置St=α；若1/3≤rd2<2/3，設(shè)置St=β；若2/3≤rd2<1，設(shè)置St=δ。

步驟3基于PMX的操作算子1。

步驟3.1 執(zhí)行步驟2。

步驟3.2 以St和Ptj為父代個體執(zhí)行PMX，從兩個子代個體中隨機(jī)選擇一個，記為Pt+1,j。

步驟4基于PMX的操作算子2。

步驟4.1 執(zhí)行步驟2。

步驟4.2 對St執(zhí)行NNSize次Multiswap算子，得到NNSize個新解，將其中的最好解記為Sp。

步驟4.3 以Sp和Ptj為父代個體執(zhí)行PMX，從兩個子代個體中隨機(jī)選擇一個，記為Pt+1,j。

步驟4.4 如果Sp優(yōu)于Ptj和Pt+1,j，則設(shè)置Pt+1,j=Sp。

步驟5局部搜索算子。

步驟5.1 設(shè)置t=1。

步驟5.2 對Ptj執(zhí)行NNSize次Multiswap算子，得到NNSize個新解，將其中的最好解賦值給Ptj。

步驟5.3 設(shè)置t=t+1。若t≤T，轉(zhuǎn)步驟5.2；否則，設(shè)置Pt+1,j=Ptj。

基于多操作的搜索算子具有以下4個優(yōu)點(diǎn)：(1)對3種不同操作以等概率選擇執(zhí)行。同時，執(zhí)行基于PMX的操作算子1和2時，從兩個子代中隨機(jī)選擇一個來更新當(dāng)前解。這可探索不同的搜索路徑，提升了GWO的多樣性。

(2)基于PMX的操作算子1可學(xué)習(xí)α，β，δ的優(yōu)良特性。

(3)基于PMX的操作算子2可學(xué)習(xí)α，β，δ較好鄰域解的優(yōu)良特性，在其鄰域內(nèi)進(jìn)行一定的探索。

(4)局部搜索算子可對當(dāng)前解的鄰域執(zhí)行搜索，提升了GWO算法的集中性。

2.7 重啟操作

為提升GWO算法的多樣性，進(jìn)一步設(shè)計(jì)了一種重啟操作。其主要思想是，若某一個解(記為Pgj)連續(xù)多代未改進(jìn)，它可能陷入了局部最優(yōu)。以等概率選擇3種操作算子中的一個，對它執(zhí)行該算子，希望將其引導(dǎo)至新的尚未搜索過的區(qū)域。該重啟操作類似于文獻(xiàn)[6]中的偵察蜂階段。具體地，該操作可描述如下：

步驟1若解Pgj連續(xù)多代仍未改進(jìn)，轉(zhuǎn)步驟2。

步驟2對Pgj以等概率(即1/3)執(zhí)行如下3種操作之一：①連續(xù)執(zhí)行3次Multiswap算子；②連續(xù)執(zhí)行3次Swap算子；③連續(xù)執(zhí)行3次Insert算子。將得到的新解記為Pnew。

步驟3設(shè)置Pg+1,j=Pnew。

2.8 算法框架

給定GWO算法的參數(shù)：種群規(guī)模M，連續(xù)未改進(jìn)的允許最大迭代次數(shù)NI，執(zhí)行Multiswap算子的次數(shù)NNSize，局部搜索算子的最大循環(huán)次數(shù)T，如圖2所示為GWO算法的流程圖。由圖2可以看出，GWO算法首先需要設(shè)置算法參數(shù)，然后利用兩種初始化策略生成具有一定質(zhì)量和多樣性的初始種群，并對種群執(zhí)行社會化等級分層操作。隨后，對種群中每個個體分別執(zhí)行基于多操作的搜索算子、對種群執(zhí)行社會化等級分層操作、對種群執(zhí)行重啟操作，循環(huán)執(zhí)行這3個步驟，直至達(dá)到GWO算法的終止條件(允許的最大CPU運(yùn)行時間或允許最大迭代次數(shù))，最后輸出GWO算法搜索到的歷史最好解。

3 實(shí)驗(yàn)與結(jié)果

為驗(yàn)證所提GWO算法的高效性，本章將其與文獻(xiàn)中的4種調(diào)度算法進(jìn)行了對比，包括兩種有效的SCC調(diào)度算法和兩種有效的車間調(diào)度算法：改進(jìn)人工蜂群算法(Improved Artificial Bee Colony, IABC)[6]、果蠅優(yōu)化算法(Fruit Fly Optimization, FOA)[3]、迭代局部搜索(Iterated Local Search, ILS)[18]、遺傳算法(Genetic Algorithm, GAR)[19]。

本文使用C++對算法在Visual Studio 2013中進(jìn)行編程，在Windows 7操作系統(tǒng)下配置為2.13 GHz和2 G內(nèi)存的計(jì)算機(jī)上執(zhí)行。GWO算法的參數(shù)設(shè)置如下：M=30，NI=50，NNSize=5，T=5。每種對比算法都使用了本文的編碼和解碼方法。對于每個算例，每種算法獨(dú)立運(yùn)行10次，并計(jì)算這10次運(yùn)行的平均目標(biāo)函數(shù)值。使用相對百分比增加(Relative Percentage Increase，RPI)來評價算法性能，其中使用了每種算法的10次的平均值來計(jì)算RPI，即

(1)

式中：fC為對比算法C獨(dú)立運(yùn)行10次的平均值，C是指GWO、IABC、FOA、ILS、GAR，fbest是指對比算法中的最好值。

3.1 算例說明

使用文獻(xiàn)[1]中的算例生成方法生成30個算例。共有3臺轉(zhuǎn)爐，5臺精煉爐，4臺連鑄機(jī)。每個連鑄機(jī)加工3～4個澆次，而每個澆次包含8～12個爐次。煉鋼階段到精煉階段的轉(zhuǎn)移時間、精煉階段到連鑄階段的轉(zhuǎn)移時間均在區(qū)間[10,15]內(nèi)取值。爐次j在煉鋼階段、精煉階段的加工時間分別在如下范圍內(nèi)取值：PT1j=38，PT2j∈[36,50]，爐次j在連鑄階段的一般加工時間在如下范圍內(nèi)取值：PT3j∈[38,44]，而PT3j的最小與最大加工時間分別為0.9PT3j和1.1PT3j。

3.2 基于多操作的搜索算子的重要性

為驗(yàn)證基于多操作的搜索算子對于GWO算法的重要性，本節(jié)執(zhí)行實(shí)驗(yàn)來對比GWO算法與使用另外兩種搜索算子的GWO算法。其中，第一種GWO算法使用基于PMX的操作算子1，記為GWOPMX算法，而第二種GWO算法使用文獻(xiàn)[15]中的搜索算子(記為shift算子)，記為GWOs，GWOPMX算法和GWOs算法的其余成分與GWO算法相同。使用了3種算法終止條件進(jìn)行實(shí)驗(yàn)，即CPU時間分別為10 s、20 s和30 s。

表1給出了CPU時間為10 s下，3種對比算法的RPI。由表1知，在CPU時間10 s下，GWO算法的性能明顯好于GWOPMX算法和GWOs算法，GWO算法的RPI平均值為0.01%，在30中的29個測試算例上，GWO算法的RPI為0，而GWOPMX算法和GWOs算法的RPI平均值分別為4.50%和15.12%。表2給出了CPU時間為20 s和30 s下，3種對比算法的平均RPI。由表2可知，在CPU時間為20 s和30 s下，GWO算法依然優(yōu)于GWOPMX算法和GWOs算法，3種對比算法的平均值分別為0，3.65%，15.50%。當(dāng)CPU時間為20 s時，3種對比算法的RPI平均值分別為0，3.80%，15.39%。而在CPU時間為30 s下，3種對比算法的RPI平均值分別為0，3.50%，15.60%。該實(shí)驗(yàn)對比表明基于多操作的搜索算子優(yōu)于PMX和shift算子，從而說明其有效性。

表1 CPU時間為10 s下的不同搜索算子的RPI對比結(jié)果

表2 CPU時間為20 s和30 s下的不同搜索算子的平均RPI對比結(jié)果

3.3 與4種調(diào)度算法的對比

本節(jié)將GWO算法與IABC、FOA、ILS、GAR進(jìn)行了對比，同樣使用了3種算法終止條件，即CPU時間分別為10 s、20 s和30 s。IABC、FOA、ILS、GAR的參數(shù)設(shè)置與相應(yīng)文獻(xiàn)相同，CPU時間為10 s下的對比結(jié)果如表3所示。由表3可知，在CPU時間為10 s下，GWO優(yōu)于IABC、FOA、ILS、GAR，GWO的平均RPI僅為0.79%，而IABC、FOA、ILS、GAR的平均RPI分別為1.26%、2.15%、4.32%和12.00%。

表4給出了CPU時間為20 s和30 s下5種對比算法的平均RPI。根據(jù)表4，GWO仍然優(yōu)于IABC、FOA、ILS、GAR，GWO的平均值為0.80%，而IABC、FOA、ILS、GAR的平均值分別為1.56%、1.98%、3.34%和9.91%。具體地，在CPU時間為20 s下，GWO算法優(yōu)于IABC、FOA、ILS、GAR，它們的平均RPI分別為0.78%、1.46%、1.95%、3.61%和10.35%。而在CPU時間為30 s下，GWO算法依然優(yōu)于IABC、FOA、ILS、GAR，相應(yīng)的平均RPI分別為0.81%、1.65%、2.01%、3.07%和9.46%。由此說明GWO算法可高效地解決可調(diào)加工時間SCC調(diào)度問題。

表3 CPU時間為10 s下的算法RPI對比結(jié)果

續(xù)表3

表4 CPU時間為20 s和30 s下的算法平均RPI對比結(jié)果

4 結(jié)束語

本文提出了解決可調(diào)加工時間SCC調(diào)度問題的高效GWO算法。利用連鑄階段加工時間可調(diào)這一特性，設(shè)計(jì)了新解碼方法。并研究了種群初始化方法，可得到具有一定質(zhì)量和多樣性的初始種群。其次，研制了高性能的基于多操作的搜索算子，可在一定程度上實(shí)現(xiàn)集中性和多樣性的平衡。此外，開發(fā)了重啟操作以幫助GWO算法跳出局部最優(yōu)。通過實(shí)驗(yàn)對比驗(yàn)證了GWO算法的有效性。本文提出的解碼方法、種群初始化及基于多操作的搜索算子也可用于求解可調(diào)加工時間SCC調(diào)度問題的其他算法，此外，GWO算法也可用于解決其他調(diào)度問題，如SCC重調(diào)度[20]、混合流水車間重調(diào)度[21]等。