多階段人機(jī)協(xié)同的煉鋼—連鑄調(diào)度方法

趙 寧，李 亮，杜彥華

（北京科技大學(xué) 機(jī)械工程學(xué)院，北京 100083）

0 引言

煉鋼—連鑄是將鐵水等原料通過(guò)煉鋼轉(zhuǎn)化為液態(tài)鋼水，再通過(guò)精煉和連鑄轉(zhuǎn)化為固態(tài)鋼坯的生產(chǎn)過(guò)程。該過(guò)程的加工對(duì)象是煉鋼后放在鋼包中的鋼水，因此煉鋼—連鑄生產(chǎn)調(diào)度一般以煉鋼爐中的鋼水為調(diào)度對(duì)象，稱(chēng)為爐次。煉鋼—連鑄生產(chǎn)調(diào)度計(jì)劃是在批量計(jì)劃的基礎(chǔ)上，以爐次為最小計(jì)劃單位，在滿(mǎn)足溫度、連鑄等約束的前提下，追求綜合評(píng)價(jià)函數(shù)，如等待時(shí)間最小、提前／拖期費(fèi)用和總流程時(shí)間最少等最佳情況下的一類(lèi)排序問(wèn)題［1］。相對(duì)其他調(diào)度問(wèn)題，煉鋼—連鑄調(diào)度存在約束多、節(jié)拍緊的特點(diǎn)，被認(rèn)為是最難的流水車(chē)間調(diào)度問(wèn)題之一［2］。煉鋼—連鑄調(diào)度問(wèn)題具有很高的研究?jī)r(jià)值與實(shí)用價(jià)值，也有很多優(yōu)化目標(biāo)，其中最小化總流程時(shí)間（Makespan）是相對(duì)最重要的優(yōu)化目標(biāo)，并吸引著眾多研究者參與其中。

早期關(guān)于煉鋼—連鑄調(diào)度的研究側(cè)重于機(jī)器調(diào)度，即通過(guò)計(jì)算機(jī)和算法快速尋找最優(yōu)或滿(mǎn)意的調(diào)度解。因此，機(jī)器調(diào)度又可分為最優(yōu)和近優(yōu)兩大類(lèi)，最優(yōu)方法包括整數(shù)規(guī)劃法［3］和拉格朗日算法［4］等，它們大都是以遍歷問(wèn)題的所有可行解為手段，適合規(guī)模小、約束條件少的調(diào)度計(jì)劃編制問(wèn)題；近優(yōu)方法包括蜂群算法［5］、遺傳算法［6］、粒子群算法［7］和鄰域搜索方法［8］等，這些近優(yōu)方法得到的結(jié)果雖然不一定最優(yōu)，但是計(jì)算的效率高，對(duì)解決大規(guī)模調(diào)度問(wèn)題很有效。

盡管機(jī)器調(diào)度已經(jīng)取得了很多研究成果［3-8］，但在實(shí)際的煉鋼—連鑄生產(chǎn)調(diào)度時(shí)，仍存在很多需要依靠經(jīng)驗(yàn)的情形，具體表現(xiàn)在：

（1）煉鋼調(diào)度存在一些經(jīng)驗(yàn)規(guī)則，如盡量將相似鋼種安排在同一設(shè)備、盡量將鋼水安排在以往質(zhì)量較穩(wěn)定的設(shè)備、鋼水等待時(shí)間盡量少、盡量考慮設(shè)備維護(hù)的影響等。這些規(guī)則并非在每次調(diào)度時(shí)都要遵守，在實(shí)際生產(chǎn)時(shí)仍要依據(jù)不同的鋼種、不同的生產(chǎn)狀況由調(diào)度員憑經(jīng)驗(yàn)掌握。

（2）實(shí)際生產(chǎn)的狀況千變?nèi)f化，目前的調(diào)度模型難以涵蓋生產(chǎn)現(xiàn)場(chǎng)隨時(shí)可能提出的各種調(diào)度需求，當(dāng)機(jī)器調(diào)度難以滿(mǎn)足需求時(shí)，仍要依賴(lài)調(diào)度員的經(jīng)驗(yàn)調(diào)度。

因此很多文獻(xiàn)都指出，在目前的煉鋼—連鑄調(diào)度中，調(diào)度員的經(jīng)驗(yàn)仍不可替代［9-12］。很多學(xué)者在煉鋼—連鑄調(diào)度領(lǐng)域開(kāi)展人機(jī)協(xié)同調(diào)度的研究，取得了一些成果［9-14］，并已經(jīng)在一些鋼廠獲得實(shí)際應(yīng)用，產(chǎn)生了經(jīng)濟(jì)效益。但這些方法仍存在如下不足：

（1）人工調(diào)度和機(jī)器調(diào)度分工明確、各自為政，調(diào)度員可以干預(yù)調(diào)度結(jié)果，但無(wú)法涉足優(yōu)化過(guò)程，調(diào)度員難以參與各種優(yōu)化算法的運(yùn)算過(guò)程，調(diào)度算法也難以與調(diào)度員的經(jīng)驗(yàn)相結(jié)合。

（2）這些方法都是由機(jī)器調(diào)度產(chǎn)生一個(gè)初始解，再由調(diào)度員憑借經(jīng)驗(yàn)對(duì)調(diào)度解加以調(diào)整。煉鋼—連鑄調(diào)度存在緊前約束、設(shè)備資源約束、連鑄約束和運(yùn)輸時(shí)間約束等調(diào)度約束，在調(diào)整過(guò)程中調(diào)度員不得不投入大量精力來(lái)滿(mǎn)足這些調(diào)度約束，影響人機(jī)協(xié)同的調(diào)度效率。

本文針對(duì)以上問(wèn)題提出一種多階段人機(jī)協(xié)同調(diào)度方法（Multi-Stage Man Machine Cooperated scheduling method，MSMMC），該方法提供了調(diào)度員參與優(yōu)化過(guò)程的接口，可以將機(jī)器調(diào)度的特點(diǎn)與調(diào)度員的經(jīng)驗(yàn)相結(jié)合，通過(guò)人機(jī)協(xié)同的方式實(shí)現(xiàn)調(diào)度解的調(diào)整和優(yōu)化。與已有方法相比，本文所提方法具有以下優(yōu)勢(shì)：

（1）使調(diào)度員更容易理解機(jī)器調(diào)度過(guò)程并參與其中，從而更好地發(fā)揮調(diào)度經(jīng)驗(yàn)的優(yōu)勢(shì)。

（2）可訓(xùn)練并增強(qiáng)人的調(diào)度能力，當(dāng)出現(xiàn)機(jī)器調(diào)度難以處理的情形時(shí)，人工調(diào)度會(huì)發(fā)揮更多優(yōu)勢(shì)。

2 多階段調(diào)度優(yōu)化

本文的主要目標(biāo)是縮短整個(gè)調(diào)度計(jì)劃的完工時(shí)間Makespan。建立調(diào)度數(shù)學(xué)模型如下：

其中：i為爐次序號(hào)；Ω 為沒(méi)有澆鑄結(jié)束的爐次的集合，i∈Ω，|Ω|為爐次總數(shù)；n為澆次號(hào)，N 為澆次數(shù)，n=1，2，…，N；Ωn為第n 澆次中沒(méi)有澆鑄結(jié)束的爐次集合，Ω1∩Ω2∩… ∩ΩN=?，且Ω1∪Ω2∪… ∪ΩN=Ω；Si為爐次i的工序總數(shù)，由于精煉總數(shù)的不同，所有爐次計(jì)劃的工序總數(shù)不完全相同；j為工序序號(hào)，1≤j≤Si；Θ′i為爐次i的所有工序集合；Θi為爐次i沒(méi)有開(kāi)始生產(chǎn)的工序集合；M 為機(jī)器總臺(tái)數(shù)；k為機(jī)器序號(hào)，1≤k≤M；kij為爐次i工序j所在的機(jī)器序號(hào)；stijk為 爐次i工序j 在機(jī)器k上的加工開(kāi)始時(shí)間；Xijk為爐次i工序j 在機(jī)器k 上調(diào)度優(yōu)化后的加工開(kāi)始時(shí)間，選為模型的決策變量；ptijk為爐次i在工序j的機(jī)器k 上的工藝加工時(shí)間；tmax為鋼包在兩工序間的最大等待時(shí)間；tmin為鋼包在兩工序間的最小等待時(shí)間；utkk′為爐次從機(jī)器k到機(jī)器k′的運(yùn)輸時(shí)間；SI（i，j，k）為爐次i在工序j的機(jī)器k上的緊后爐次。

式（1）為目標(biāo)函數(shù)，即調(diào)度計(jì)劃的完工時(shí)間最短；式（2）表示在同一臺(tái)設(shè)備上相鄰爐次間要等到前一爐次加工完后才可進(jìn)行下一爐次的加工；式（3）表示同一爐次相鄰工序間要等到前一工序加工完后才可進(jìn)行下一工序的加工；式（4）表示同一爐次的相鄰工序在進(jìn)行設(shè)備間運(yùn)輸?shù)倪^(guò)程中，運(yùn)輸時(shí)間必須在一定范圍內(nèi)，否則會(huì)導(dǎo)致鋼水溫度不滿(mǎn)足溫度約束；式（5）表示同屬一個(gè)澆次的爐次在連鑄機(jī)上加工時(shí)要保證連續(xù)生產(chǎn)約束，否則會(huì)導(dǎo)致斷澆事故；式（6）表示每爐次的開(kāi)始時(shí)間應(yīng)大于等于0。

以上模型表達(dá)了本文所考慮的煉鋼—連鑄調(diào)度的優(yōu)化目標(biāo)和約束條件。此處假定所有爐次可在任一并行機(jī)上加工，則調(diào)度的內(nèi)容是確定所有爐次的加工設(shè)備、先后次序和開(kāi)始時(shí)間，在滿(mǎn)足所有約束條件的基礎(chǔ)上使總加工周期最短。以上模型雖然表達(dá)了煉鋼—連鑄調(diào)度的約束和目標(biāo)，但是無(wú)法描述前文所述的依靠調(diào)度經(jīng)驗(yàn)的情形。這些情形較難納入調(diào)度模型中考慮，在實(shí)際生產(chǎn)中一般都需調(diào)度員憑借經(jīng)驗(yàn)手動(dòng)調(diào)整。

為了使機(jī)器調(diào)度與手工調(diào)度能夠優(yōu)勢(shì)互補(bǔ)，有必要設(shè)計(jì)一種便于調(diào)度員理解和參與的調(diào)度算法，使調(diào)度經(jīng)驗(yàn)?zāi)軌蛉谌霗C(jī)器調(diào)度過(guò)程中。因此，本文設(shè)計(jì)了MSMMC，該方法借鑒經(jīng)典調(diào)度中的鄰域搜索和關(guān)鍵路徑方法。其基本思路是先產(chǎn)生一個(gè)初始調(diào)度解，再根據(jù)該調(diào)度解的關(guān)鍵路徑對(duì)該調(diào)度解進(jìn)行鄰域搜索，調(diào)度員可參與機(jī)器搜索過(guò)程并在搜索過(guò)程中添加約束，通過(guò)人機(jī)協(xié)同調(diào)度直至找到滿(mǎn)意的調(diào)度解。MSMMC 的優(yōu)化調(diào)度過(guò)程具體分為如下幾個(gè)階段：

（1）第一階段 以手動(dòng)調(diào)度或其他自動(dòng)調(diào)度方式生成初始調(diào)度解。

（2）第二階段 調(diào)度員判斷調(diào)度解是否滿(mǎn)足要求，如果不滿(mǎn)意則可憑借經(jīng)驗(yàn)手動(dòng)調(diào)整工序所在的煉鋼、精煉設(shè)備以及工序加工順序，系統(tǒng)采用貪心和反貪心算法對(duì)人工調(diào)整解進(jìn)行自動(dòng)修正，在滿(mǎn)足各項(xiàng)約束的基礎(chǔ)上盡量縮短生產(chǎn)周期。

（3）第三階段 采用極值法對(duì)關(guān)鍵路徑進(jìn)行鄰域搜索，并采用約束聯(lián)動(dòng)方法獲得滿(mǎn)足約束的優(yōu)化解。調(diào)度員評(píng)價(jià)優(yōu)化解的生產(chǎn)周期是否滿(mǎn)意，如果滿(mǎn)意則調(diào)度結(jié)束；否則可再次對(duì)優(yōu)化解進(jìn)行人工調(diào)整，然后重復(fù)該階段直至滿(mǎn)意。MSMMC 調(diào)度過(guò)程如圖1所示。

在圖1所示的MSMMC優(yōu)化過(guò)程中，人工調(diào)整是第二階段和第三階段的核心。人工調(diào)整的方法有調(diào)整工序、加工順序、調(diào)整工序設(shè)備、調(diào)整工序開(kāi)始時(shí)間等。此處采取的是基于關(guān)鍵路徑的鄰域搜索方法，其搜索過(guò)程相對(duì)更容易被調(diào)度員理解，而調(diào)度員在人工調(diào)整過(guò)程中只需考慮需要憑借調(diào)度經(jīng)驗(yàn)解決的問(wèn)題，調(diào)度模型中的約束則由機(jī)器加以保障。當(dāng)人工調(diào)度結(jié)束后，系統(tǒng)再不斷以調(diào)度員的調(diào)整解為基礎(chǔ)進(jìn)行新一輪鄰域優(yōu)化，直至獲得滿(mǎn)意的調(diào)度解。與以往的方法相比，多階段人機(jī)優(yōu)化調(diào)度方法在優(yōu)化過(guò)程上提供了多個(gè)調(diào)度員的參與點(diǎn)，從而能將調(diào)度經(jīng)驗(yàn)更好地融入優(yōu)化過(guò)程，實(shí)現(xiàn)機(jī)器和調(diào)度經(jīng)驗(yàn)的優(yōu)勢(shì)互補(bǔ)。特別地，如果不需要調(diào)度經(jīng)驗(yàn)干預(yù)，則可在多階段人機(jī)優(yōu)化調(diào)度過(guò)程中跳過(guò)人工調(diào)整，進(jìn)行下一輪鄰域搜索，從而起到快速尋優(yōu)的效果。

3 關(guān)鍵技術(shù)

下面依次對(duì)多階段人機(jī)協(xié)同調(diào)度過(guò)程中存在的關(guān)鍵技術(shù)進(jìn)行說(shuō)明。

3.1 貪心算法與反貪心算法

貪心算法是根據(jù)給定的調(diào)度方案，計(jì)算每道工序的開(kāi)始加工時(shí)間，通過(guò)縮短同臺(tái)設(shè)備上工序與工序間的間隔時(shí)間，使工序的可開(kāi)始加工時(shí)間變得最早，通過(guò)該策略對(duì)調(diào)度解進(jìn)行修正，使調(diào)度解滿(mǎn)足約束并變得更為緊湊。以爐次i的工序j 為例，在計(jì)算最早開(kāi)始加工時(shí)間時(shí)，需要按照以下公式進(jìn)行計(jì)算：

式中：i′和j′分別表示與爐次i的工序j 安排在同一設(shè)備上相鄰的前序爐次，表示爐次i 的第j 道工序的最早開(kāi)始加工時(shí)間，表示爐次i 的第j 道工序的完工時(shí)間。式（7）表達(dá)了最早開(kāi)始時(shí)間等于該爐次上一工序的結(jié)束時(shí)間加最短運(yùn)輸時(shí)間與同一設(shè)備上一工序結(jié)束時(shí)間的最大值，式（8）表示最早結(jié)束時(shí)間可由最早開(kāi)始時(shí)間與加工時(shí)間之和求得。

算法1 貪心算法。

步驟1 按式（7）和式（8）計(jì)算爐次i工序j 的開(kāi)始時(shí)間和結(jié)束時(shí)間。

步驟2 j=j+1，按式（7）和式（8）計(jì)算下一工序的開(kāi)始時(shí)間和結(jié)束時(shí)間，直至遍歷爐次i的所有工序。

步驟3 針對(duì)與爐次i的工序j 同一設(shè)備的下一工序，按式（7）和式（8）計(jì)算開(kāi)始時(shí)間和結(jié)束時(shí)間，直至遍歷爐次i的工序j 同設(shè)備的所有后續(xù)工序。

可見(jiàn)，貪心算法是在保證緊前約束和設(shè)備資源約束的基礎(chǔ)上獲得最早可開(kāi)始時(shí)間，并將每一工序按其最早可開(kāi)始時(shí)間調(diào)度，從而使Makespan 盡可能短。同理，反貪心算法則是由最后一道工序的開(kāi)始時(shí)間推算，在保證緊前約束和設(shè)備資源約束的基礎(chǔ)上依次獲得以上每道工序的最晚可開(kāi)始時(shí)間，并將每一工序按其最晚可開(kāi)始時(shí)間進(jìn)行調(diào)度，反貪心算法與貪心算法的計(jì)算過(guò)程則完全相反，這里不再贅述。貪心算法忽視了連鑄約束和運(yùn)輸時(shí)間約束，追求最早可開(kāi)始時(shí)間，可用于Makespan 的優(yōu)化；而反貪心算法則用于確保連鑄約束和運(yùn)輸時(shí)間約束，可用于優(yōu)化后的人工調(diào)整。

3.2 基于關(guān)鍵路徑的鄰域搜索

關(guān)鍵路徑是指煉鋼—連鑄調(diào)度計(jì)劃中對(duì)整個(gè)調(diào)度計(jì)劃影響最大的加工路徑，通過(guò)對(duì)關(guān)鍵路徑進(jìn)行領(lǐng)域搜索，可以有效提高搜索效率。根據(jù)已知的調(diào)度方案選擇出最后完工的爐次工序，利用逆推法決定關(guān)鍵路徑，通過(guò)交換關(guān)鍵塊中的工序次序和更換連鑄設(shè)備實(shí)現(xiàn)鄰域搜索。

逆推法首先將最后完工工序設(shè)為關(guān)鍵工序，再將關(guān)鍵工序所在設(shè)備的前驅(qū)工序和同一爐次的前驅(qū)工序進(jìn)行比較，取結(jié)束時(shí)間較大的前驅(qū)工序作為下一個(gè)關(guān)鍵工序，依次類(lèi)推，直至找到開(kāi)始時(shí)間最早的工序。按照這一方法可以得到一條對(duì)整個(gè)調(diào)度計(jì)劃影響較大的關(guān)鍵路徑。在逆推過(guò)程中，如果遇到設(shè)備前驅(qū)工序的結(jié)束時(shí)間與爐次前驅(qū)工序的結(jié)束時(shí)間相等，則取爐次前驅(qū)工序作為下一個(gè)關(guān)鍵工序，這是因?yàn)闋t次前驅(qū)工序約束等級(jí)高于設(shè)備約束等級(jí)。

本文將鄰域分為鄰域由關(guān)鍵路徑?jīng)Q定和鄰域由鑄機(jī)選擇決定兩部分。其中關(guān)鍵路徑鄰域搜索的基本思路是：根據(jù)逆推法可獲得任一調(diào)度方案的關(guān)鍵路徑，更換關(guān)鍵路徑中的工序順序、獲得新的調(diào)度方案，新調(diào)度方案即為舊調(diào)度方案的鄰域。在得到的關(guān)鍵路徑中必定包括了轉(zhuǎn)爐設(shè)備的工序塊、精煉設(shè)備的工序塊和連鑄機(jī)設(shè)備的工序塊，在關(guān)鍵路徑中放置于轉(zhuǎn)爐和精煉設(shè)備上并受設(shè)備資源約束限制的連續(xù)工序稱(chēng)為關(guān)鍵塊。關(guān)鍵塊中的工序兩兩置換后得到的新調(diào)度解稱(chēng)為原調(diào)度解的鄰域。如果關(guān)鍵塊中只有一道關(guān)鍵工序，則不需要交換，如果關(guān)鍵塊中有兩道以上關(guān)鍵工序，則依次進(jìn)行兩兩交換。在所有關(guān)鍵塊都交換完畢后得到的鄰域解中取最優(yōu)解，如果最優(yōu)鄰域解優(yōu)于原調(diào)度解，則保留最優(yōu)鄰域解并開(kāi)始新一輪鄰域交換，反之則搜索完畢。

鑄機(jī)選擇鄰域搜索是本文定義的另一鄰域搜索方法，僅將鑄機(jī)選擇作為搜索范疇主要基于如下考慮：

（1）鑄機(jī)是煉鋼過(guò)程的最后一臺(tái)設(shè)備，因此鑄機(jī)選擇對(duì)生產(chǎn)周期有直接影響。

（2）如果將所有設(shè)備的選擇都作為鄰域搜索的范疇，則會(huì)極大地增加搜索空間，影響搜索速度，導(dǎo)致調(diào)度人員等待時(shí)間過(guò)長(zhǎng)，影響人機(jī)協(xié)同效果。

本文僅將連鑄設(shè)備的選擇納入鄰域搜索，煉鋼、精煉設(shè)備的選擇通過(guò)人工調(diào)整完成。當(dāng)然，調(diào)度員也可對(duì)機(jī)器選擇的鑄機(jī)進(jìn)行手動(dòng)調(diào)整，但此時(shí)最終調(diào)度方案的生產(chǎn)周期可能會(huì)比機(jī)器搜索方案的生產(chǎn)周期更長(zhǎng)。

鑄機(jī)選擇鄰域搜索的基本思路是采用極值優(yōu)化（Extremal Optimization，EO）方法，該方法是受復(fù)雜系統(tǒng)自組織臨界進(jìn)化模型的啟發(fā)形成的一種啟發(fā)式智能算法［16］。EO 方法的基本出發(fā)點(diǎn)是將問(wèn)題分解成低耦合度的局部變量，考查各變量對(duì)解的貢獻(xiàn)，并將其量化為適應(yīng)度。對(duì)適應(yīng)度最低的變量取值進(jìn)行修改，使其適應(yīng)度提高，從而提高解的質(zhì)量。

算法2 EO 算法。

步驟1 找出調(diào)度方案中最晚完工的機(jī)器，令其為M1。

步驟2 找到M1 的末道工序，將其定義為當(dāng)前工序A。

步驟3 在A 的可加工機(jī)器集合上找到最早結(jié)束加工的機(jī)器，令其為M2。根據(jù)不同情形，將工序A 變換到M2設(shè)備上，變換時(shí)依據(jù)式（2）和式（3）計(jì)算變換工序的開(kāi)始時(shí)間和結(jié)束時(shí)間。

（1）若設(shè)備M2的末道工序B 的結(jié)束時(shí)間小于A 的開(kāi)始加工時(shí)間，則直接將設(shè)備M1上的末道工序A 排在B的后面。如圖2所示。

（2）若M2上的末道工序B 的結(jié)束時(shí)間大于等于A 的開(kāi)始時(shí)間，則從設(shè)備M2的末道工序開(kāi)始向前查找加工時(shí)間小于A 的加工時(shí)間的工序，然后進(jìn)行交換。如圖3所示。

（3）如果B的加工時(shí)間小于A 的加工時(shí)間，則把A 與B進(jìn)行交換。如果B 的加工時(shí)間大于等于A 的加工時(shí)間，則在設(shè)備M2上從B 開(kāi)始向前尋找加工時(shí)間小于A 的工序C，然后進(jìn)行交換。如圖4所示。

步驟4 判斷變換后的新方案，若仍存在上述三種情形，則轉(zhuǎn)步驟3，否則算法結(jié)束。

在以上兩種鄰域搜索方法的基礎(chǔ)上，對(duì)任一初始解，依次結(jié)合關(guān)鍵路徑法和EO 算法進(jìn)行鄰域搜索，每次都會(huì)得到一個(gè)完工時(shí)間更小的新調(diào)度方案。新調(diào)度方案又會(huì)產(chǎn)生新的關(guān)鍵路徑，可進(jìn)一步通過(guò)關(guān)鍵路徑和鑄機(jī)選擇搜索更優(yōu)的新調(diào)度方案。如此循環(huán)，當(dāng)完工時(shí)間不再縮小時(shí)搜索結(jié)束。值得一提的是，如果調(diào)度員不滿(mǎn)意，則可在結(jié)果的基礎(chǔ)上調(diào)整煉鋼和精煉設(shè)備的選擇，調(diào)整之后的鄰域搜索可望獲得更好的結(jié)果。

3.3 基于約束的聯(lián)動(dòng)調(diào)整

在通過(guò)關(guān)鍵路徑搜索得到優(yōu)化解的基礎(chǔ)上，考慮約束模型中的緊前約束、設(shè)備資源約束、連鑄約束和運(yùn)輸時(shí)間約束，在保證上述約束的基礎(chǔ)上實(shí)現(xiàn)調(diào)度解的聯(lián)動(dòng)調(diào)整，從而減輕調(diào)度員的負(fù)擔(dān)。具體的聯(lián)動(dòng)調(diào)整步驟如下：

算法3 約束聯(lián)動(dòng)調(diào)整算法。

步驟1 針對(duì)調(diào)度員調(diào)整后的結(jié)果，按加工順序遍歷所有爐次的所有工序。

步驟2 對(duì)遍歷工序按照式（2）和式（3）進(jìn)行緊前和設(shè)備資源約束判定，對(duì)有約束沖突的工序按貪心算法進(jìn)行調(diào)整，以滿(mǎn)足約束。

步驟3 針對(duì)上述調(diào)整結(jié)果，按反向加工順序遍歷所有爐次的所有工序。

步驟4 對(duì)遍歷工序按照式（4）進(jìn)行連鑄約束判定，對(duì)不滿(mǎn)足連鑄約束的按反貪心算法調(diào)整鑄機(jī)工序。

步驟5 對(duì)遍歷工序按照式（5）進(jìn)行運(yùn)輸時(shí)間約束判定，對(duì)不滿(mǎn)足約束的按運(yùn)輸時(shí)間調(diào)整算法進(jìn)行調(diào)整。

其中步驟5的運(yùn)輸時(shí)間調(diào)整算法如下：

算法4 運(yùn)輸時(shí)間調(diào)整算法。

步驟1 先進(jìn)行精煉爐到連鑄機(jī)的運(yùn)輸時(shí)間調(diào)整，對(duì)精煉爐上的工序，從每臺(tái)精煉設(shè)備上的末道工序開(kāi)始，依次進(jìn)行設(shè)備前驅(qū)工序前推。

步驟2 根據(jù)精煉爐上工序的結(jié)束時(shí)間和該工序的后繼工序開(kāi)始時(shí)間進(jìn)行差值計(jì)算，設(shè)差值為ΔT。如果ΔT ＞tmax，則進(jìn)行精煉爐上該工序的后移，后移值為ΔT-tmin。

步驟3 調(diào)整完精煉爐后，利用相同的原理調(diào)整轉(zhuǎn)爐到精煉爐的運(yùn)輸時(shí)間。按連鑄機(jī)工序順序前移，轉(zhuǎn)步驟1，直至遍歷所有鑄機(jī)工序。

以圖5為例說(shuō)明算法4的思路。從圖5可以看出：1-12-2到1-12-3的運(yùn)輸輔助時(shí)間ΔT ＞tmin，因此1-12-2號(hào)工序需要進(jìn)行調(diào)整。將1-12-2道工序的開(kāi)始時(shí)間加上ΔT-tmin，使得該工序的結(jié)束時(shí)間與后續(xù)工序開(kāi)始時(shí)間的時(shí)間差為tmin，從而保證了約束模型中運(yùn)輸時(shí)間的限制和計(jì)劃的可行性。

4 實(shí)例分析及性能測(cè)試

基于上述內(nèi)容開(kāi)發(fā)了煉鋼—連鑄調(diào)度系統(tǒng)，并進(jìn)行了實(shí)例分析和性能測(cè)試。

4.1 實(shí)例分析

以文獻(xiàn)［15］中機(jī)器調(diào)度的最終優(yōu)化結(jié)果對(duì)比說(shuō)明本文方法。在該實(shí)例中的生產(chǎn)工藝路線為轉(zhuǎn)爐、精煉和連鑄，使用轉(zhuǎn)爐2臺(tái)、精煉爐3臺(tái)、連鑄機(jī)3臺(tái)，針對(duì)一個(gè)澆次的18爐鋼進(jìn)行生產(chǎn)計(jì)劃調(diào)度。在調(diào)度系統(tǒng)中建立文獻(xiàn)［15］最終的優(yōu)化結(jié)果，如圖6所示。

以該結(jié)果為初始解，利用貪心算法進(jìn)行方案的初步調(diào)度優(yōu)化，得到的結(jié)果如圖7所示。

可以看出，貪心算法計(jì)算后的方案在完工時(shí)間上雖然較之前的方案沒(méi)有改進(jìn)，但大幅提前了煉鋼和精煉階段工序的開(kāi)始時(shí)間，在此基礎(chǔ)上可進(jìn)一步通過(guò)關(guān)鍵路徑法優(yōu)化。圖7中的關(guān)鍵路徑為1-1-1，1-3-1，1-3-2，1-3-3，1-6-3，1-9-3，1-12-3，1-15-3，1-18-3，如圖8所示。

對(duì)圖8中關(guān)鍵路徑所形成的鄰域進(jìn)行搜索并進(jìn)行約束聯(lián)動(dòng)調(diào)整，優(yōu)化結(jié)果與圖8一致，調(diào)度員去除等待時(shí)間約束的優(yōu)化結(jié)果如圖9所示。

由圖9可見(jiàn)，優(yōu)化后的生產(chǎn)周期比初始解減少了15min，但造成第2，4，6，8，10，14等多個(gè)爐次的轉(zhuǎn)爐結(jié)束時(shí)間與精煉開(kāi)始時(shí)間的差距過(guò)大，雖然滿(mǎn)足了運(yùn)輸時(shí)間約束，但整體等待時(shí)間過(guò)大會(huì)造成溫度損耗并給生產(chǎn)帶來(lái)隱患。因此，圖9 結(jié)果與圖6結(jié)果相比，雖然生產(chǎn)周期更優(yōu)，但整體衡量未必更好，這從另一方面也說(shuō)明了文獻(xiàn)［15］的機(jī)器調(diào)度結(jié)果在2臺(tái)轉(zhuǎn)爐情況下已較優(yōu)，而本文方法可達(dá)到文獻(xiàn)［15］的同等效果。

假設(shè)此時(shí)調(diào)度條件發(fā)生變化，生產(chǎn)現(xiàn)場(chǎng)要求將17，18爐次轉(zhuǎn)做方坯，同時(shí)要求生產(chǎn)周期盡量縮短，調(diào)度員可憑借調(diào)度經(jīng)驗(yàn)（考慮鋼種類(lèi)似、等待時(shí)間較多的爐次）在圖9的基礎(chǔ)上手動(dòng)調(diào)整3，6，9，12，15，17，18等工序的加工設(shè)備，利用貪心算法修正后的結(jié)果如圖10所示。

由圖10可見(jiàn)，人工調(diào)整后使用了轉(zhuǎn)爐3和方坯鑄機(jī)1，生產(chǎn)周期比初始方案縮短了75 min。在人工調(diào)整的基礎(chǔ)上進(jìn)一步利用鄰域搜索優(yōu)化，再用約束聯(lián)動(dòng)方法修補(bǔ)約束后的調(diào)度結(jié)果，如圖11所示。

圖11所示結(jié)果的生產(chǎn)周期比初始方案提前90 min，同時(shí)各爐次間滿(mǎn)足等待時(shí)間約束。如果該方案仍不滿(mǎn)足要求或生產(chǎn)現(xiàn)場(chǎng)提出新的調(diào)度要求，則可再次利用人工調(diào)整，結(jié)合機(jī)器調(diào)度算法進(jìn)行新一輪優(yōu)化，直到滿(mǎn)意為止。

4.2 性能測(cè)試

在人機(jī)結(jié)合調(diào)度過(guò)程中，機(jī)器算法的運(yùn)算效率對(duì)人機(jī)結(jié)合調(diào)度的效果有較大影響。為了檢驗(yàn)本文算法的響應(yīng)速度，針對(duì)爐數(shù)在10爐～30 爐的調(diào)度計(jì)劃隨機(jī)生成不同的初始解，對(duì)初始解進(jìn)行算法優(yōu)化并對(duì)算法效率進(jìn)行測(cè)試，測(cè)試結(jié)果如圖12所示。

從圖12可以看出，算法運(yùn)算時(shí)間會(huì)隨爐次的增加而增加，但在30爐時(shí)最長(zhǎng)也不超過(guò)10s，在人能夠承受的等待時(shí)間范圍內(nèi)。此外，由第15 爐和26爐的對(duì)應(yīng)時(shí)間可知，算法運(yùn)算時(shí)間并不平滑，這一現(xiàn)象可能是由不同的初始解造成的。對(duì)于是否會(huì)有個(gè)別初始解造成運(yùn)算時(shí)間非常長(zhǎng)的情況，以18爐鋼為例，隨機(jī)形成30個(gè)不同的初始調(diào)度方案，實(shí)驗(yàn)結(jié)果如圖13所示。結(jié)果顯示，18爐鋼的算法執(zhí)行時(shí)間平均為2s，最長(zhǎng)時(shí)間不超過(guò)8s，整體仍處于可承受范圍之內(nèi)。因此，算法具有較好的計(jì)算效率，在人機(jī)協(xié)同過(guò)程中不會(huì)導(dǎo)致調(diào)度員等待較長(zhǎng)時(shí)間。

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

本文針對(duì)煉鋼—連鑄調(diào)度問(wèn)題提出一種多階段人機(jī)協(xié)同調(diào)度方法。該方法以最小完工時(shí)間為目標(biāo)，采用最早完工貪心算法進(jìn)行初優(yōu)化，再結(jié)合關(guān)鍵路徑和鄰域搜索方法進(jìn)行優(yōu)化，調(diào)度員憑借經(jīng)驗(yàn)可干預(yù)優(yōu)化過(guò)程，從而更快地獲得滿(mǎn)意調(diào)度解。通過(guò)實(shí)例表明，本文提出的多階段人機(jī)協(xié)同調(diào)度方法可以充分發(fā)揮調(diào)度人員的經(jīng)驗(yàn)，能夠獲得更好的調(diào)度解。算法性能測(cè)試表明，本文提出的機(jī)器調(diào)度算法具有較好的計(jì)算性能，能夠配合調(diào)度員快速有效地對(duì)調(diào)度方案進(jìn)行優(yōu)化。

目前本文工作還停留在煉鋼—連鑄的靜態(tài)調(diào)度階段，而動(dòng)態(tài)調(diào)度是更能發(fā)揮人機(jī)協(xié)同優(yōu)勢(shì)的調(diào)度領(lǐng)域。因此，開(kāi)展人機(jī)協(xié)同動(dòng)態(tài)調(diào)度的研究將是未來(lái)的研究方向。

［1］WANG Bailin，LI Tieke，ZHANG Chunsheng，et al.Dynamic CSP based scheduling algorithm for steelmaking &continuous casting with conticaster breakdown［J］.Computer Integrated Manufacturing Systems，2011，17（10）：2185-2193（in Chinese）.［王柏琳，李鐵克，張春生，等.基于動(dòng)態(tài)約束滿(mǎn)足的考慮連鑄機(jī)故障的煉鋼連鑄調(diào)度算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（10）：2185-2193.］

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

［3］NAPHADE K S，WU S D，STORER R H，et al.Melt seheduling to trade off material waste and shipping Performance［J］.Operations Research，2001，49（5）：629-645.

［4］XUAN Hua.Three-stage HFS scheduling problem with serial batching machines［J］.Computer Integrated Manufacturing Systems，2012，18（5）：1006-1010（in Chinese）.［軒 華.含串行批處理機(jī)的三階段混合流水車(chē)間調(diào)度問(wèn)題［J］.計(jì)算機(jī)集成制造系統(tǒng)，2012，18（5）：1006-1010.］

［5］PAN Quanke，WANG Ling，MAO Kun.An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process［J］.IEEE Transactions on Automation Science and Engineering，2013，10（2）：307-322.

［6］SANTOS C A，SPIM J A，GARCIA A.Mathematical modeling and optimization strategies（genetic algorithm and knowledge base）applied to the continuous casting of steel［J］.Engineering Applications of artificial Intelligence，2003，16（6）：511-527.

［7］TANG Lixin，WANG Xianpeng.An improved particle swarm optimization algorithm for the hybrid flowshop scheduling to minimize total weighted completion time in process industry［J］.IEEE Transactions on Control Systems Technology，2010，18（6）：1303-1314.

［8］DONG Hongyu，HUANG Min.Improved varible neighborhood search for integrated tundish planning in steelmaking process［J］.International Journal of Production Research，2012，50（20）：5747-5761.

［9］CHEN Kai，ZHENG Zhong，GAO Xiaoqiang.Computer-aided planning and scheduling system for steelmaking-continuous casting［J］.Journal of Iron and Steel Research International，2010，17（2）：29-34.

［10］YU Shengping，CHEN Wenming，PANG Xinfu，et al.Simulation system of dynamic scheduling of steelmaking &continuous casting based on graphic edit platform［J］.Journal of System Simulation，2009，21（16）：5145-5149（in Chinese）.［俞勝平，陳文明，龐新富，等.基于圖形化編輯平臺(tái)的煉鋼連鑄動(dòng)態(tài)調(diào)度仿真系統(tǒng)［J］.系統(tǒng)仿真學(xué)報(bào)，2009，21（16）：5145-5149.］

［11］ZHAO Ning，DU Yanhua，DONG Shaohua.Dynamic simulation scheduling oriented to temperature constraints and continuous production constraints［J］.Computer Integrated Manufacturing Systems，2013，19（1）：97-105（in Chinese）.［趙 寧，杜彥華，董紹華.溫度和連續(xù)生產(chǎn)約束下的動(dòng)態(tài)仿真調(diào)度［J］.計(jì)算機(jī)集成制造系統(tǒng)，2013，19（1）：97-105.］

［12］WANG Chao，LI Tieke，ZHANG Wenxue.Dynamic scheduling for steelmaking &continuous casting based on humancomputer interaction［J］.Application Research of Computers，2011，28（4）：1378-1381（in Chinese）.［王 超，李鐵克，張文學(xué).基于人機(jī)交互的煉鋼連鑄動(dòng)態(tài)調(diào)度［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（4）：1378-1381.］

［13］WANG Xiuying，CHAI Tianyou，ZHENG Binglin.Intelligent scheduling software &its application in steelmaking &continuous casting［J］.Computer Integrated Manufacturing Systems，2006，12（8）：1220-1226（in Chinese）.［王秀英，柴天佑，鄭秉霖.煉鋼—連鑄智能調(diào)度軟件的開(kāi)發(fā)及應(yīng)用［J］.計(jì)算機(jī)集成制造系統(tǒng)，2006，12（8）：1220-1226.］

［14］ZHAO Ning，DING Wenying，DONG Shaohua，et al.Dynamic schedule of steel making-continuous casting based on group adjustment orienting restrict［J］.Systems Engineering—Theory &Practice，2011，31（11）：2176-2184（in Chinese）.［趙 寧，丁文英，董紹華，等.基于約束聯(lián)動(dòng)的煉鋼—連鑄動(dòng)態(tài)調(diào)度［J］.系統(tǒng)工程理論與實(shí)踐，2011，31（11）：2176-2184.］

［15］YU Shengping，PANG Xinfu，CHAI Tianyou，et al.Production mode and optimization scheduling model for steelmaking and continuous casting［J］.Systems Engineering—Theory &Practice，2011，31（11）：2166-2176（in Chinese）.［俞勝平，龐新富，柴天佑，等.煉鋼連鑄生產(chǎn)模式及優(yōu)化調(diào)度模型［J］.系統(tǒng)工程理論與實(shí)踐，2011，31（11）：2166-2176.］