唐秋華，鄭 鵬，張利平，張啟敏，陳 立

（1.武漢科技大學(xué) 機械自動化學(xué)院，湖北 武漢 430081；2.武漢鋼鐵股份有限公司，湖北 武漢 430081）

0 引言

鋼鐵是國家的基礎(chǔ)工業(yè)之一，是國民經(jīng)濟的重要支柱。鋼鐵生產(chǎn)包括煉鐵、煉鋼、澆鑄、軋制等工序，其中煉鋼到連鑄是核心工藝流程。在該過程中，物理變化和化學(xué)反應(yīng)交織融合，原材料、半成品和成品的溫度、形態(tài)及成分在各工序均不同。生產(chǎn)組織方式前后各異，在煉鋼和精煉階段以爐次為基本單位，采用間歇生產(chǎn)模式，而在連鑄階段以澆次為基本單位，同一澆次內(nèi)多爐鋼水連澆連鑄。為保證生產(chǎn)的連續(xù)性，工序間設(shè)有多種不同類型的緩沖區(qū)?？梢姡瑹掍撨B鑄生產(chǎn)既有流水車間的特點，又有其特殊性，可歸納為一種多緩沖、無等待、最后階段為成批處理的流水車間調(diào)度問題，其計算復(fù)雜度比一般流水車間調(diào)度更高。

煉鋼連鑄生產(chǎn)調(diào)度算法主要有最優(yōu)化、智能算法和啟發(fā)式方法等。Hua等［1］建立了煉鋼連鑄生產(chǎn)調(diào)度的整數(shù)規(guī)劃模型，基于拉格朗日松弛進行批次解耦，繼而求解；Mao等［2］以最小化加權(quán)提前和拖期懲罰及最小化任務(wù)等待時間為目標，建立了混合整數(shù)規(guī)劃模型，再用拉格朗日松弛方法求解；Abdelkader Sbihi等［3］針對一個三階段的煉鋼連鑄調(diào)度問題，建立了相應(yīng)的混合整數(shù)規(guī)劃模型，并通過GAMS／Cplex求解。最優(yōu)化方法能求得最優(yōu)解，但隨著問題規(guī)模的增大，計算時間呈指數(shù)增長。針對大規(guī)模問題，智能算法和啟發(fā)式方法能在極短的時間內(nèi)獲得近優(yōu)解乃至最優(yōu)解，同時滿足企業(yè)在計算效率和調(diào)度方案性能方面的要求。李鐵克等［4］將煉鋼連鑄生產(chǎn)過程抽象為混合流水車間，結(jié)合遺傳算法（Genetic Algorithm，GA）和線性規(guī)劃提出一種兩階段GA；陳立等［5］建立了約束滿足優(yōu)化模型，融合約束滿足技術(shù)與遺傳優(yōu)化對原問題進行求解。與智能算法相比，啟發(fā)式方法針對特定問題提煉出啟發(fā)式規(guī)則，再融于問題求解中，具有直觀、簡單、易用的特點。孫亮亮等［6］針對澆次與鑄機的關(guān)系構(gòu)造出澆次集合，提出一種基于啟發(fā)式的深度優(yōu)先搜索算法；Hubert Missbauer等［7］將煉鋼連鑄過程分解為四個子問題，針對不同的子問題，采用包括與工序相關(guān)的啟發(fā)式規(guī)則、線性規(guī)劃松弛等方法進行求解。

上述算法主要考慮煉鋼連鑄生產(chǎn)的工藝約束、最后階段成批生產(chǎn)約束等，很少考慮多緩沖約束。針對包含多緩沖的煉鋼連鑄問題，現(xiàn)有的研究成果較少。Li等［8］基于單元特定事件的連續(xù)時間建模方法，建立了混合整數(shù)線性規(guī)劃模型，并用GAMS／Cplex進行求解；馬文強等［9］建立了緩沖區(qū)數(shù)量和時間受限的帶約束的調(diào)度模型，并通過離散人工蜂群（Discrete Artificial Bee Colony，DABC）算法進行求解；于艷輝等［10］將原問題轉(zhuǎn)化為無等待的三階段混合流水車間調(diào)度問題，提出組合啟發(fā)式算法進行求解。上述文獻將各類緩沖區(qū)均視為加工時間為0的工序，忽略了不同類型緩沖區(qū)的差異性，沒有將其進行區(qū)別對待。另外，生產(chǎn)調(diào)度以爐次為單位，計算復(fù)雜度較高。因此，本文面向具有多緩沖的煉鋼連鑄生產(chǎn)，以澆次為基本生產(chǎn)單位，針對不同類型的緩沖區(qū)提出澆次內(nèi)分配和澆次間定時兩種啟發(fā)式規(guī)則，以保證生產(chǎn)的高效順行，再用文化基因算法（Memetic Algorithm，MA）來保證澆次序列的優(yōu)化，最后用不同規(guī)模的24 組實例檢驗所提算法的性能。

1 煉鋼連鑄生產(chǎn)調(diào)度問題

1.1 問題描述

煉鋼連鑄生產(chǎn)一般包括煉鋼、精煉和連鑄三個階段。以Pacciarelli等［11］提出的問題為例，其生產(chǎn)階段是先用電弧爐（EAF）煉鋼生成鋼水，再用氬氧精煉（AOD）和鋼包處理（LF）確保鋼水成分精確、溫度均勻，最后用連鑄（CC）將鋼水直接澆鑄成型，加工成不同的坯料。其生產(chǎn)組織的最大特點是在連鑄工序以澆次為生產(chǎn)組織單位，屬于同一澆次的各爐次需連澆連鑄，而兩個相鄰澆次間需預(yù)留一定的準備時間，以更換中間包。

為保證生產(chǎn)的連續(xù)性，在相鄰工序間設(shè)有三種不同類型的緩沖區(qū)：①無限緩沖區(qū)，設(shè)在EAF 和AOD間，有3個，每個緩沖區(qū)僅可容納1個鋼水包，且允許其無限停留；②有限緩沖區(qū)，設(shè)在LF 和CC間，僅1個，由于連鑄溫度要求，其停留時間受限；③可加工緩沖區(qū)，LF 爐不僅具有工藝上的加工能力，還可對鋼水包進行緩沖。

由于LF爐通常設(shè)有兩個工位，按Pacciarelli等的處理方法［8-9，11］，將其轉(zhuǎn)化為兩個串行工位LF1和LF2。于是，圖1所示的煉鋼連鑄生產(chǎn)調(diào)度問題變成具有特殊性的9階段置換流水車間調(diào)度問題。其中要完成的澆次數(shù)、各澆次的爐次數(shù)、各爐次在每道工序的處理時間、澆次間換包的準備時間等數(shù)據(jù)已知，需要合理決策澆次順序及各設(shè)備的具體操作時間，以使最大完工時間最小化。

1.2 煉鋼—連鑄生產(chǎn)調(diào)度模型

為描述方便，首先說明參數(shù)和符號：

I為爐次集合，I=｛1，2，…，i，…，I｝；

K為澆次集合，K=｛1，2，…，k，…，K｝；

S為階段集合，S=｛1，2，…，s，…，S｝；

N為澆次事件集合，N=｛1，2，…，t，…，K｝；

T為爐次事件集合，T=｛1，2，…，t，…，I｝；

Ik為澆次k中包含的爐次集合；

If為所有澆次第一爐構(gòu)成的集合；

Nk為澆次k中包含的爐次總數(shù)；

NSs為無緩沖能力的階段s；

USs為無限緩沖階段s；

LSs為有限緩沖階段s；

Pi為有限緩沖區(qū)的最大允許停留時間；

Ps為相鄰澆次之間的準備時間；

Ptks為k澆次在s階段處理一爐所需的時間；

Zkn表示澆次順序為二元決策變量，若澆次k分到澆次事件點n，則Zkn=1，否則Zkn=0；

Xit為連續(xù)變量，表示爐次i分到事件點t；

Tsst表示s階段事件點t的開始時間，為連續(xù)變量；

Tfst表示階段事件點t的結(jié)束時間，s為連續(xù)變量；

Cmax表示最大完工時間，為連續(xù)變量。

煉鋼連鑄生產(chǎn)調(diào)度問題的目標是令最大完工時間最小化，在此基礎(chǔ)上，還需滿足澆次排序、澆次內(nèi)和澆次間的時間三類約束：

（1）分配及排序約束 煉鋼連鑄生產(chǎn)調(diào)度的核心任務(wù)是決定澆次順序。每一澆次都必須分配，且每一事件點僅能分配一個澆次。當澆次順序確定后，每澆次中各爐次的順序就已知。

（2）澆次內(nèi)時間約束 在同一機器上必須前一任務(wù)完成后下一任務(wù)才能開始，在鑄機上同一澆次內(nèi)各爐次必須連澆連鑄。另外，為保證工藝需求及生產(chǎn)連續(xù)性，使用了多種緩沖區(qū)。式（4）～式（6）為同一工序相鄰任務(wù)間及同一任務(wù)相鄰工序間的基本時間約束，式（7）和式（8）定義了無限緩沖區(qū)，式（9）定義了有限緩沖區(qū)。

（3）澆次間時間約束 在連鑄階段需考慮相鄰澆次之間的準備時間，同時在其他設(shè)備上仍存在設(shè)備和物料的可用性保障，即除式（10）外，式（4）～式（9）對澆次間亦有效。

目標函數(shù)為最大完工時間最小化。

聯(lián)立式（1）～式（11），構(gòu)成上述多緩沖煉鋼連鑄生產(chǎn)調(diào)度問題模型。

由于可加工緩沖區(qū)兼具無限緩沖區(qū)和操作工序的特點，其定義用式（4）～式（7）共同完成。同時，由式（7）～式（9）可見，由于煉鋼連鑄生產(chǎn)中的前后兩道工序之間無等待，存儲在無限緩沖區(qū)中的鋼水離開本工序時，該存儲任務(wù)才結(jié)束。不同于操作時間，緩沖區(qū)存儲沒有明確的時間長度，當調(diào)度問題中涉及多個多種類型的緩沖區(qū)時很難協(xié)調(diào)其工作。綜合上述分析，本文以澆次為研究對象進行煉鋼連鑄生產(chǎn)調(diào)度。

2 面向多緩沖的澆次內(nèi)和澆次間啟發(fā)式規(guī)則

在煉鋼連鑄生產(chǎn)調(diào)度問題中，需處理無限、有限和可加工三種緩沖區(qū)類型，同時還需要滿足置換流水車間的一般性約束，以及爐次駐留時間受限、最后階段成批生產(chǎn)、澆次間最短準備時間等特殊約束。對于煉鋼連鑄過程中的多約束，多將整個工藝流程簡化為煉鋼—精煉—連鑄三個階段，使用罰函數(shù)等進行約束處理。例如，通過設(shè)置爐次等待懲罰［1，4，8］、斷澆懲 罰［4，6，8］等，保證爐次駐 留時間受限和最后階段成批生產(chǎn)約束。對于煉鋼連鑄過程中的多緩沖，當前研究較少，一般是將緩沖區(qū)當作加工時長為0的工序，進而將原問題轉(zhuǎn)化為多階段、無等待的流水車間調(diào)度問題［10-11］。然而，這種方法缺少對不同類型緩沖區(qū)的差異化處理。

緩沖區(qū)存儲時間的不確定導(dǎo)致生產(chǎn)計劃編排的多樣性。若緩沖時間較短，則可能導(dǎo)致后續(xù)工序約束不滿足（如CC的連鑄約束）；若緩沖時間較長，則可能導(dǎo)致后續(xù)工序機器的不必要等待。更重要的是，成批生產(chǎn)約束位于最后一道工藝，若以爐次為單位進行生產(chǎn)計劃編排，則必然造成緩沖區(qū)分配的重復(fù)調(diào)整，產(chǎn)生極大的計算復(fù)雜度。本文考慮最后階段的成批生產(chǎn)，以澆次為單位，提出澆次內(nèi)和澆次間的兩種啟發(fā)式規(guī)則，先用澆次內(nèi)規(guī)則分配各爐次緩沖時間，再使用澆次間規(guī)則進行調(diào)整，通過兩次計算即可完成緩沖區(qū)處理。

2.1 澆次內(nèi)啟發(fā)式規(guī)則

澆次內(nèi)啟發(fā)式規(guī)則通過澆次完工時間確定和緩沖區(qū)的初次分配，實現(xiàn)生產(chǎn)順行，保證最后階段的成批生產(chǎn)和各工序機器閑置時間的最小化。

2.1.1 澆次完工時間確定

與一般的置換流水車間相比，煉鋼連鑄生產(chǎn)的特殊之處在于同一澆次內(nèi)的連澆連鑄。為此，采用回溯法倒排方式，使得同一澆次內(nèi)的各爐次能滿足置換流水車間的一般性約束和最后階段成批生產(chǎn)的約束，據(jù)此確定澆次完工時間。具體思路如下：

（1）引用批處理作業(yè)調(diào)度模型［12］，保證澆次內(nèi)的各爐次滿足置換流水車間的一般約束。因為該模型中設(shè)定的所有任務(wù)在第一道工序上的加工都是連續(xù)的，而煉鋼連鑄生產(chǎn)調(diào)度在最后一個階段是成批生產(chǎn)，所以將所有工序（包括緩沖區(qū)）倒排。倒排后連鑄CC成為第一道工序，可以保證連澆連鑄，如圖2a所示。通過回溯法［12］倒排，即使同一澆次內(nèi)各爐次的加工時間存在差異，仍可求出最優(yōu)排產(chǎn)結(jié)果。

（2）將倒排結(jié)果進行翻轉(zhuǎn)，求得正常工藝順序下的澆次完工時間。將固定倒排結(jié)果中CC上第一爐的開始時間、EAF上最后一爐的結(jié)束時間（Makespan）作為該澆次的固定時間域，再將工藝順序翻轉(zhuǎn)，根據(jù)流水車間特性，從固定時間域的結(jié)束時間開始，從后向前推算出各爐次在各工序的開始和結(jié)束時間。圖2b即為翻轉(zhuǎn)后同一澆次內(nèi)各爐次的最優(yōu)排產(chǎn)結(jié)果。

2.1.2 緩沖區(qū)分配

經(jīng)回溯法翻轉(zhuǎn)后，澆次完工時間已知，且各爐次處理順序已滿足工藝約束。但由于沒有考慮緩沖區(qū)的存儲功能，設(shè)備利用率不高、生產(chǎn)過程不緊湊。為此，以最短加工時間（Shortest Processing Time，SPT）為目標，結(jié)合最早空閑機器優(yōu)先（First Available Machine，F(xiàn)AM）規(guī)則，設(shè)計了如圖3 所示的緩沖區(qū)分配方法。

根據(jù)工藝順序，該緩沖區(qū)分配方法主要包括三部分：

（1）若EAF工序上后一爐次開始時間與前一爐次結(jié)束時間之間有間隔，且B1～B3中至少一個有空閑，則可利用B1～B3的無限緩沖功能使EAF連續(xù)加工，從而集合其閑置時間，便于濺渣護爐。

根據(jù)旅游統(tǒng)計公報顯示，2013-2016年中國國內(nèi)旅游人次和國內(nèi)居民出境人次均保持增長，其中中國國內(nèi)旅游人次增長率穩(wěn)定在10%以上，并有持續(xù)增長趨勢。2016年中國國內(nèi)旅游人次和國內(nèi)居民出境人次分別達到44.4億人次和1.2億人次，隨著用戶旅游經(jīng)驗的積累，對于個性化和深度旅游需求不斷增加，為在線自助游奠定發(fā)展基礎(chǔ)。

（2）若AOD 工序上后一爐次開始時間與前一爐次結(jié)束時間之間有間隔，且間隔時間在LF 可調(diào)整范圍內(nèi)，則可通過LF的存儲特性使AOD 連續(xù)加工，減少機器等待時間。

（3）對于B1～B3無限緩沖區(qū)的選擇，先將各緩沖區(qū)的釋放時間按升序排列，優(yōu)先使用最早可用的緩沖區(qū)，若釋放時間相同，則按緩沖區(qū)編號依次使用。

通過澆次內(nèi)啟發(fā)式規(guī)則處理后，在同一澆次內(nèi)各爐次的所有約束均已滿足，且機器等待時間實現(xiàn)了最小化。

2.2 澆次間啟發(fā)式規(guī)則

澆次間啟發(fā)式規(guī)則通過緩沖區(qū)時間調(diào)整，滿足相鄰澆次間的準備時間約束，最終完成各澆次中全部爐次的定時。假設(shè)澆次1和澆次2為兩個相鄰澆次，澆次2緊跟在澆次1后面，進行具體爐次定時的步驟如下：

步驟1 按照澆次內(nèi)啟發(fā)式規(guī)則分別對澆次1、澆次2內(nèi)的各爐次時間進行初步排定，再將澆次2置于澆次1之后，繼而將澆次2整體往左平移（如圖4a），直至某一工序的開始時間與澆次1相應(yīng)工序的結(jié)束時間重合，此時澆次2各工序的開始時間達到下界。

步驟2 核查兩澆次在連鑄階段的時間間隔Δt1，若大于準備時間Ps，則澆次1和澆次2排產(chǎn)結(jié)束，對下一澆次重復(fù)步驟1；否則，轉(zhuǎn)步驟3進行緩沖區(qū)調(diào)整。

步驟3 因為工序之間無等待，若使用靠前工序間的緩沖區(qū)，則其后各工序的開始、結(jié)束時間均需依次后移，所以規(guī)定各類緩沖區(qū)的使用順序依次為B4，LF2，LF1，B3，B2，B1。圖4b中Δt2為利用緩沖區(qū)B4，LF2，LF1全部存儲能力下鑄機CC的調(diào)整結(jié)果，若在此調(diào)整之后Δt2仍不滿足準備時間約束，則利用無限緩沖區(qū)B1～B3 的剩余存儲能力進行調(diào)整，若仍不滿足，則將澆次2整體右移直至達到準備時間。此時澆次1和澆次2排產(chǎn)結(jié)束，對下一澆次重復(fù)步驟1，直至所有澆次排產(chǎn)完畢。

3 煉鋼連鑄調(diào)度問題求解

MA 的基本步驟包括編碼、解碼、全局搜索和局部搜索。在算法設(shè)計過程中，利用面向多緩沖的澆次內(nèi)和澆次間啟發(fā)式規(guī)則實現(xiàn)解碼，在局部搜索算子中加入基于優(yōu)先組合矩陣的優(yōu)化機制，通過自適應(yīng)交叉概率控制全局搜索，以提升算法的性能和效率。

3.1 全局搜索算子

澆次序列采用自然數(shù)編碼方法，染色體上的基因位表示澆次排序，基因位上的值表示排在該順序的澆次序號，染色體的長度為總澆次數(shù)。

為加快求解速度、提高算法效率，采用NEH（Nawaz-Enscore-Ham）算法與隨機排序結(jié)合的方法初始化種群。其中，第一條染色體由NEH 算法生成，其余染色體按隨機排序方式產(chǎn)生，以保證初始種群的多樣性。適應(yīng)度值為最大完工時間，故以適應(yīng)度值的倒數(shù)為權(quán)值，通過輪盤賭進行選擇操作。

在迭代過程中，染色體間的相似度會越來越高。為穩(wěn)定種群的多樣性、避免早熟，通過自適應(yīng)交叉概率［16］來控制交叉算子，即

式中：fmax為每代種群中個體的最大適應(yīng)度值；favg為每代種群的平均適應(yīng)度值；f′為被選擇執(zhí)行交叉操作的兩個個體中較大的適應(yīng)度值；pc1和pc2需滿足pc1+pc2=1且pc1＞pc2。只要設(shè)定pc1，pc2取（0，1）區(qū)間的值，就可以對交叉概率進行自適應(yīng)調(diào)整。交叉概率隨適應(yīng)度值自動改變，當種群各個體的適應(yīng)度值趨于一致或者趨于局部最優(yōu)時，增大交叉概率可以提高種群多樣性。

澆次排序問題要求所生成的序列不能有重復(fù)任務(wù)，對此選擇了單點交叉（Set-Partition Crossover，SPX）、部分映射交叉（Partial Mapped Crossover，PMX）、順序交叉（Order Crossover，OX）三種可行的交叉方法，最后通過多因素方差分析實驗確定最終的交叉方案為順序交叉。

3.2 局部搜索算子

MA 強調(diào)局部搜索，但一般的局部搜索算法都具有較大的時間復(fù)雜度。本文結(jié)合具體問題的特性，通過加入優(yōu)先組合矩陣來保留部分排列片段，再對剩余片段進行多種鄰域結(jié)構(gòu)的變鄰域搜索，可以有效兼顧搜索性能和計算復(fù)雜度。

煉鋼連鑄澆次排產(chǎn)時，由于各澆次工序時間有差異，澆次排序時必然存在一些性能較好的局部組合。在進行局部搜索之前，若能首先保留這些組合塊，則不但可以保證解的性能，還能大大減少局部搜索的運算次數(shù)。據(jù)此設(shè)計了一種基于優(yōu)先組合矩陣的變鄰域搜索算法作為局部搜索算子。

以總機器閑置時間最小化為目標，用澆次間啟發(fā)式規(guī)則對任意兩個澆次進行求解，得到各澆次的優(yōu)先組合矩陣。表1所示為一個包含10個澆次任務(wù)的優(yōu)先組合矩陣，Ⅰ，Ⅱ，Ⅲ表示各澆次組合的優(yōu)先級，例如第2列中澆次1的最優(yōu)組合對象為澆次7，次優(yōu)對象為澆次2，再次對象為澆次10。

表1 澆次間優(yōu)先組合矩陣

在進行局部搜索時，首先保留染色體中滿足優(yōu)先組合矩陣的高性能組合塊，再對其余部分進行多種鄰域結(jié)構(gòu)的變鄰域搜索。若相鄰兩個基因位構(gòu)成Ⅰ級組合，則直接保留；若存在多個級別的組合，則保留較高級別；若存在兩個連續(xù)的、同級的基因組合，則保留前一組。如圖5所示，最后保留了［7，3］［2，1］［4，9］三個組合塊，對［6，5，10，8］進行變鄰域搜索。該方法可有效減少鄰域結(jié)構(gòu)的規(guī)模，提高算法的搜索效率。以插入鄰域為例，對于n個任務(wù)的一個序列π，其插入鄰域的規(guī)模為（n-1）2，設(shè)序列π中有個優(yōu)先組合塊，則相應(yīng)的鄰域規(guī)模減少為（n-2m-1）2。

變鄰域搜索的鄰域結(jié)構(gòu)通常要根據(jù)問題的特性設(shè)計，常見的有交換（swap）、插入（insert）、逆序（inverse）三種鄰域結(jié)構(gòu)，通過多因素方差分析實驗，最后選擇后兩種鄰域結(jié)構(gòu)進行變鄰域搜索。

3.3 算法求解流程

綜合上述全局算子及局部算子的構(gòu)造方法，結(jié)合第2章澆次內(nèi)和澆次間的兩階段啟發(fā)式規(guī)則，所提算法可用偽代碼表示如圖6所示。

4 實驗結(jié)果與分析

為驗證算法的有效性，對不同規(guī)模的算例進行求解分析。算法均采用C 語言編程，程序運行環(huán)境為CPU 2.20GHz，內(nèi)存2GB。

4.1 參數(shù)分析

算法性能受參數(shù)的影響較大，故需要通過多因素方差分析（ANalysis of VAriance，ANOVA）確定各參數(shù)值。共考慮4個因素的3種水平：種群規(guī)模設(shè)置3個水平，即10，20，30；自適應(yīng)交叉概率參數(shù)（Pc1，Pc2）設(shè)置3 個水平，分別為（0.9，0.1），（0.8，0.2），（0.7，0.3）；交叉類型設(shè)置3 個水平，分別為SPX，PMX，OX；鄰域結(jié)構(gòu)設(shè)置3 個水平，分別為Swap+Insert，Swap+Inverse，Insert+Inverse。對于每組正交實驗，在所給參數(shù)組合的情況下對算法進行10次運算，取其均值作為參數(shù)分析的目標函數(shù)，最終結(jié)果如表2所示。

表2 ANOVA分析

將最大完工時間的相對百分增量作為響應(yīng)變量，根據(jù)F值和P值分析試驗結(jié)果。其中，P值越接近0，表明因素水平之間存在的差異越顯著；F值為組間方差與組內(nèi)方差的比率，通常一個因素的F值越大，該因素對結(jié)果的影響也越大。從表2可以看出，自適應(yīng)交叉概率參數(shù)（Pc1，Pc2）對響應(yīng)變量的影響最大。（Pc1，Pc2）有三個水平，在95%的置信水平下，所得響應(yīng)變量的平均值和最小顯著差數(shù)間隔（LSD intervals）如圖7所示?？梢钥闯?，當自適應(yīng)交叉概率取（0.8，0.2）時響應(yīng)變量值最小，故設(shè)定其取值（0.8，0.2）。

用同樣方法可以得到其他因素的最優(yōu)水平，最終設(shè)定參數(shù)如下：種群規(guī)模20，自適應(yīng)交叉概率（0.8，0.2）；交叉類型選擇OX方式；鄰域結(jié)構(gòu)選擇Insert+Inverse。在后續(xù)實驗中均采用此因素水平。

4.2 啟發(fā)式規(guī)則的性能分析

本文針對多緩沖煉鋼連鑄問題提出澆次內(nèi)和澆次間兩種啟發(fā)式規(guī)則，分別用于算法的初始化和解碼兩個階段。為檢驗兩種規(guī)則的性能，選取8組算例進行對比實驗，設(shè)定算法均選用MA 算法。實驗中只使用澆次內(nèi)啟發(fā)式規(guī)則時，澆次間的替代措施是后一澆次整體延后，以滿足最小準備時間約束。該替代措施與澆次間啟發(fā)式規(guī)則的差異在于，后者更能利用緩沖區(qū)的存儲功能。僅使用澆次間啟發(fā)式規(guī)則時，對澆次內(nèi)僅保證連鑄約束，不對機器等待時間進行優(yōu)化。對比結(jié)果如表3所示。

表3 啟發(fā)式規(guī)則性能分析

由表3可以看出，使用兩種啟發(fā)式規(guī)則特別是澆次間啟發(fā)式規(guī)則，對解的性能提升效果顯著。這是因為澆次內(nèi)啟發(fā)式規(guī)則是在保證各澆次最大完工時間最小化的基礎(chǔ)上，對中間工序閑置時間進行的優(yōu)化。此優(yōu)化可提高機器稼動率，集合其閑置時間，便于其他生產(chǎn)準備或輔助工作。澆次間啟發(fā)式規(guī)則通過緩沖區(qū)的時間調(diào)整，在很大程度上減少了因準備時間約束而延后的工序數(shù)，提高了生產(chǎn)效率。

4.3 算法性能分析

為驗證算法的有效性，基于某鋼廠的實踐設(shè)計了24 個不同規(guī)模的算例，分別使用GAMS／CPLEX、GA、DABC和MA 進行求解，并從最優(yōu)解、均值和標準差三個方面評價算法性能。上述智能算法中所用的參數(shù)為基于多因素方差分析獲得的最優(yōu)參數(shù)組合，每組實驗均運行10次。為保證算法對比的公平性，參照文獻［17］，各算法均以計算時間（T=n×（m／2）×200ms）為終止條件，其中：n為任務(wù)數(shù)，m為機器數(shù)?？紤]最優(yōu)化方法的求解機理，GAMS／Cplex運行時間設(shè)為5h，實驗結(jié)果如表4所示。

表4 算例分析

相比于文獻［9］和文獻［11］中的算例，表4算例中各澆次的爐次數(shù)以及各工序的加工時間差異都很大，澆次間的準備時間不能彌補不合理調(diào)度的時間損失，問題難度較大。從表4可以看出，隨著問題規(guī)模的增大，GAMS／Cplex在5h內(nèi)對大部分問題都無法求得最優(yōu)解。對于小規(guī)模問題，三種智能算法均能找到問題的下界，但隨著問題規(guī)模的增大，DABC和MA 算法的性能顯著優(yōu)于GA。與DABC相比，MA 獲得了與其相同的9個問題的下界，還找到了2個更優(yōu)解。從算法穩(wěn)定性上來看，DABC 和GA 隨著問題規(guī)模的增大，標準差逐漸變大，而MA在求解不同規(guī)模問題時的性能均較穩(wěn)定。

5 結(jié)束語

本文針對多種不同的緩沖區(qū)類型，提煉了澆次內(nèi)和澆次間兩種啟發(fā)式規(guī)則，通過緩沖區(qū)的分配和定時，保證了生產(chǎn)順行，減少了機器的閑置等待。提出一種融合啟發(fā)式規(guī)則和MA 的求解方法，將啟發(fā)式規(guī)則融入算法的初始化和解碼流程，實現(xiàn)了澆次序列的有效求解。構(gòu)造了一種基于優(yōu)先組合矩陣的變鄰域搜索算法，在保證解的性能的前提下，提升了搜索效率，減少了運算時間。下一步的研究目標是將該方法擴展到包含并行機的煉鋼連鑄生產(chǎn)調(diào)度問題中，研制高效算法，以解決大規(guī)模的復(fù)雜工程問題。

［1］XUAN Hua，TANG Lixin.Scheduling a hybrid flowshop with batch production at the last stage［J］.Computers &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］ABDELKADER S，BELLABDAOUI A，JACQUES T.Solving a mixed integer linear program with times setup for the steel-continuous casting planning and scheduling problem［J］.International Journal of Production Research，2014，52（24）：7549.

［4］LI Tieke，SU Zhixiong.Two-stage GA algotithm on steel-making continuous-casting problem［J］.China Management Science，2009，17（5）：68-74（in Chinese）.［李鐵克，蘇志雄.煉鋼連鑄生產(chǎn)調(diào)度問題的兩階段遺傳算法［J］.中國管理科學(xué)，2009，17（5）：68-74.］

［5］CHEN Li，TANG Qiuhua，CHEN Weiming，et al.Production scheduling of steelmaking-continuous casting via hybridizing constraint satisfaction and genetic optimization［J］.Computer Integrated Manufacturing Systems，2013，19（11）：2834-2846（in Chinese）.［陳 立，唐秋華，陳偉明，等.融合約束滿足和遺傳優(yōu)化的煉鋼連鑄生產(chǎn)調(diào)度［J］.計算機集成制造系統(tǒng)，2013，19（11）：2834-2846.］

［6］SUN Liangliang，LIU Wei，CHAI Tianyou.Scheduling continuous casting process by in-depth priority search algorithm［J］.Control Theory &Applications，2010，27（12）：1705-1710（in Chinese）.［孫亮亮，劉 煒，柴天佑.基于深度優(yōu)先搜索算法的連鑄過程調(diào)度方法的研究［J］.控制理論與應(yīng)用，2010，27（12）：1705-1710.］

［7］HUBERT M，WOLFGANG H，WERNER S.A scheduling system for the steelmaking-continuous casting process.a case study from the steel-making industry［J］.International Journal of Production Research，2009，47（15）：4147-4172.

［8］LI Jie，XIAO Xin，TANG Qiuhua，et al.Production scheduling of a large-scale steelmaking continuous casting process via unit-specific event-based continuous-time models：short-term and medium-term scheduling［J］.Industrial &Engineering Chemistry Research，2012，51（21）：7300-7319.

［9］MA Wenqiang，TANG Qiuhua，ZHANG Chaoyong，et al.Steel-making continuous-casting scheduling method based on DABC algorithm［J］.Computer Integrated Manufacturing Systems，2014，20（3）：586-594（in Chinese）.［馬文強，唐秋華，張超勇，等.基于離散人工蜂群算法的煉鋼連鑄調(diào)度優(yōu)化方法［J］.計算機集成制造系統(tǒng)，2014，20（3）：586-594.］

［10］YU Yanhui，LI Tieke.Heuristic scheduling method for a class of two-stage hybrid flow shop with limitrd buffers［J］.Industrial Engineering Journal，2013，13（4）：105-110（in Chinese）.［于艷輝，李鐵克.一類緩沖區(qū)有限的兩階段混合流水車間調(diào)度問題及算法［J］.工業(yè)工程，2013，13（4）：105-110.］

［11］PACCIARELLI D，PRANZO M.Production scheduling in a steelmaking-continuous casting plant［J］.Computers and Chemical Engineering，2004，28（12）：2823-2835.

［12］WANG Xiaodong.Computer algorithms design and analysis［M］.Beijing：Publishing House of Electronics Industry，2007：127（in Chinese）.［王曉東.計算機算法設(shè)計與分析［M］.北京：電子工業(yè)出版社，2007：127.］

［13］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（1-4）：85-121.

［14］GAO Liang，QIAN Weirong，LI Xinyu，et al.Application of memetic algorithm in assembly sequence planning［J］.International Journal of Advanced Manufacturing Technology，2010，49（9-12）：1175-1184.

［15］TAVAKKOLI M R，SAFAEI N，SASSANI F.A memetic algorithm for the flexible flow line scheduling problem with processor blocking［J］.Computers &Operations Research，2009，36（2）：402-414.

［16］SRINIVAS M，PATNAIK L M.Adaptive probabili-ties of crossover and mutation in genetic algorithms［J］.IEEE Transactions on Systems，Man and Cybernetics，1994，24（4）：656-667.

［17］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.