融合啟發(fā)式規(guī)則和文化基因算法的多緩沖煉鋼—連鑄生產(chǎn)調(diào)度

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

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

0 引言

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

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

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

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

1.1 問(wèn)題描述

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

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

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

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

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

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為無(wú)緩沖能力的階段s；

USs為無(wú)限緩沖階段s；

LSs為有限緩沖階段s；

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

Ps為相鄰澆次之間的準(zhǔn)備時(shí)間；

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

Zkn表示澆次順序?yàn)槎獩Q策變量，若澆次k分到澆次事件點(diǎn)n，則Zkn=1，否則Zkn=0；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1.1 澆次完工時(shí)間確定

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

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

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

2.1.2 緩沖區(qū)分配

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 全局搜索算子

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

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

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

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

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

3.2 局部搜索算子

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

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

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

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

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

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

3.3 算法求解流程

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

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 參數(shù)分析

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

表2 ANOVA分析

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

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

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

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

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

4.3 算法性能分析

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

表4 算例分析

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

5 結(jié)束語(yǔ)

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

［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)度問(wèn)題的兩階段遺傳算法［J］.中國(guó)管理科學(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］.計(jì)算機(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)先搜索算法的連鑄過(guò)程調(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）.［馬文強(qiáng)，唐秋華，張超勇，等.基于離散人工蜂群算法的煉鋼連鑄調(diào)度優(yōu)化方法［J］.計(jì)算機(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)度問(wèn)題及算法［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）.［王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析［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.