基于離散人工蜂群算法的煉鋼連鑄調(diào)度優(yōu)化方法

馬文強(qiáng)，唐秋華，張超勇＋，邵新宇

（1．華中科技大學(xué) 機(jī)械學(xué)院數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074；2．武漢科技大學(xué) 機(jī)械自動化學(xué)院，湖北 武漢 430081）

0 引言

鋼鐵行業(yè)是我國的一項(xiàng)重要產(chǎn)業(yè)，對推動我國經(jīng)濟(jì)發(fā)展有重要作用。煉鋼連鑄是鋼鐵生產(chǎn)過程中的重要階段，有效的調(diào)度方案能夠有效減少生產(chǎn)成本、降低能耗、提高鋼鐵質(zhì)量和生產(chǎn)效率。然而，煉鋼連鑄生產(chǎn)調(diào)度是一類復(fù)雜的無等待混合流水車間調(diào)度組合優(yōu)化問題，屬于NP－h(huán)ard問題，不存在確定的多項(xiàng)式時(shí)間最優(yōu)解求解算法。該問題的約束條件復(fù)雜，具有許多動態(tài)不確定事件，生產(chǎn)過程中對調(diào)度算法的實(shí)時(shí)性要求很高。因此，對煉鋼連鑄生產(chǎn)調(diào)度問題的研究具有重要的理論意義和實(shí)用價(jià)值。

在鋼鐵產(chǎn)業(yè)的實(shí)際生產(chǎn)調(diào)度過程中，如何進(jìn)行高效優(yōu)化的排產(chǎn)一直以來都備受關(guān)注。首先，一個(gè)調(diào)度的優(yōu)劣直接影響到生產(chǎn)過程的能耗和碳排放；其次，工廠煉鋼往往按一定周期來進(jìn)行計(jì)劃調(diào)度，一個(gè)周期內(nèi)有許多個(gè)澆次的任務(wù)，不同澆次的爐次和工藝存在一定的差異，調(diào)度問題不僅要對一個(gè)澆次的爐次進(jìn)行調(diào)度，還要對一個(gè)周期內(nèi)所有澆次進(jìn)行調(diào)度。實(shí)際生產(chǎn)過程中，許多煉鋼廠的煉鋼連鑄生產(chǎn)運(yùn)行都是調(diào)度員憑經(jīng)驗(yàn)安排，調(diào)度方案還存在較大的優(yōu)化空間。

煉鋼問題的難點(diǎn)在于：煉鋼過程要求高溫環(huán)境，因此對于連鑄階段，在鋼水成型前，需要盡量縮短停留時(shí)間，在模型方面確定了有限的緩沖區(qū)限制；考慮到鑄坯質(zhì)量和節(jié)約能源等因素，現(xiàn)代的鋼水冷卻成型采用連續(xù)鑄鋼的方法，連鑄階段必須是連續(xù)進(jìn)行的，模型有連鑄即連續(xù)進(jìn)行的硬性要求；連鑄階段需要用到中間包，中間包長時(shí)間澆鑄容易穿包、造成事故，因此在連鑄階段后，考慮了澆鑄機(jī)更換中間包的中斷時(shí)間。

當(dāng)前，煉鋼連鑄調(diào)度問題的求解方法主要可分為最優(yōu)化方法和近似方法兩類。最優(yōu)化方法包括整數(shù)規(guī)劃、混合整數(shù)規(guī)劃和分支定界法等；近似方法包括基于計(jì)算機(jī)仿真算法、人工智能方法、啟發(fā)式算法和元啟發(fā)式算法等，這類方法能在有限時(shí)間獲得問題的近優(yōu)解。在近年來的研究中，Bellabdaoui和Teghem［1］建立了一個(gè)混合整數(shù)線性規(guī)劃模型，用于描述煉鋼工藝中的約束來求解煉鋼連鑄問題，并采用最優(yōu)化方法求解，然而最優(yōu)化方法較難在有效的時(shí)間內(nèi)獲得問題的最好解。Li Jie等［3］提出了基于事件和加工單元的混合整數(shù)規(guī)劃模型，采用滾動平面法求解模型。Pacciarelli等［4］基于可選圖的方案來描述每一個(gè)與調(diào)度問題相關(guān)的約束，結(jié)合集束搜索作為啟發(fā)式策略求解模型。Liu Wei等［5］提出一種批次劃分的啟發(fā)式調(diào)度規(guī)則來求解煉鋼調(diào)度模型。龐新富等［9］對煉鋼—連鑄混合job－shop重調(diào)度問題進(jìn)行了分析，建立了0－1整數(shù)模型，采取并行逆推的啟發(fā)式方法指派設(shè)備完成調(diào)度。

最優(yōu)化方法和近似方法在求解煉鋼連鑄問題方面各有優(yōu)缺點(diǎn)，將最優(yōu)化方法和近似方法有機(jī)組合，優(yōu)勢互補(bǔ)，能在可行時(shí)間范圍內(nèi)獲得問題的較優(yōu)解，近年來越來越受到研究者的關(guān)注。潘全科等［2］提出用混合整數(shù)規(guī)劃模型來描述爐次和機(jī)器的時(shí)間關(guān)系，通過啟發(fā)式的方法和兩個(gè)改進(jìn)步驟來對解進(jìn)行優(yōu)化，并使用人工蜂群算法調(diào)整爐次置換順序。Atighehchian等［6］也將冶煉精煉和連鑄分為兩階段，采用蟻群算法和非線性優(yōu)化求解模型。

人工蜂群算法（Artificial Bee Colony algorithm，ABC）［11－14］是近年提出的一種新型智能群體算法，在求解組合優(yōu)化問題中具有比遺傳算法、粒子群優(yōu)化算法更高的效率。本文將人工蜂群算法應(yīng)用到煉鋼連鑄問題中，針對某煉鋼廠的實(shí)際生產(chǎn)工藝過程，給出最大完工時(shí)間下界的計(jì)算公式，提出一種人工蜂群算法和線性規(guī)劃相結(jié)合的算法解決此類煉鋼連鑄調(diào)度優(yōu)化問題，并通過具體煉鋼連鑄調(diào)度實(shí)例與其他算法進(jìn)行比較，驗(yàn)證了模型和算法的可行性與有效性。

1 煉鋼連鑄調(diào)度問題

1．1 煉鋼連鑄工藝過程描述

某鋼廠煉鋼連鑄實(shí)際生產(chǎn)過程的四個(gè)關(guān)鍵步驟如下：①冶煉過程（Electric Arc Furnace，EAF），該過程主要將鐵塊等原材料進(jìn)行熔解；②吹入氣體精煉過程（Argon Oxygen Decarburization，AOD），在前一過程中生成的鋼水包中加入鎳鎘等金屬可提高產(chǎn)品的質(zhì)量，這一過程中還有除碳等其他作用；③鋼水包處理過程（Ladle Furnace，LF），這一過程主要為了保溫和一些其他操作，如果不進(jìn)行LF過程，隨后的連鑄定型過程將無法實(shí)現(xiàn)，這一過程最多能容納2個(gè)鋼水包同時(shí)進(jìn)行；④連鑄過程（Continuous Caster，CC），這個(gè)工程中需要對之前加工得到的半成品進(jìn)行定型，以適合各種不同用途，同一批次的不同鋼水包必須得到連續(xù)加工，這是因?yàn)樵谶B鑄過程中需要用到一個(gè)中間包，假如同一批次的鋼水包不是連續(xù)定型的，則中間包會退化穿包、引發(fā)事故。因此，在一個(gè)批次連鑄之后需要有一個(gè)更換中間包的過程，需要消耗一定的時(shí)間，這段時(shí)間中連鑄過程的處理裝置無法使用，本文模型也對這一過程預(yù)留了時(shí)間。

1．2 煉鋼連鑄數(shù)學(xué)規(guī)劃模型

本文采用的模型考慮到以下情形：①進(jìn)緩沖區(qū)數(shù)量約束，在冶煉過程（EAF）和吹入氣體精煉過程（AOD）中有3個(gè)緩沖區(qū)，同時(shí)連鑄過程（CC）工序之前有1個(gè)緩沖區(qū)；②緩沖區(qū)時(shí)間約束，前3個(gè)緩沖區(qū)可無限等待，最后一個(gè)緩沖區(qū)滯留時(shí)間有限，否則影響鋼胚質(zhì)量；③連鑄之后更換中間包的時(shí)間。結(jié)合冶煉、精煉和連鑄，整個(gè)過程如圖1～圖3所示。

現(xiàn)有的煉鋼模型（如文獻(xiàn)［9－10］等），沒有采用或者采用加權(quán)懲罰來衡量連鑄前的等待時(shí)間，將連鑄前的停留視為軟約束，允許長時(shí)間的等待，硬約束只有連鑄工序，模型緩沖區(qū)的長度和數(shù)量沒有限制。本文的模型考慮了緩沖區(qū)的作用，將緩沖區(qū)視為加工時(shí)間有限制的普通工序，限制了緩沖區(qū)的數(shù)量和澆鑄前緩沖區(qū)的最長等待時(shí)間，通過這種約束不但確保了連鑄工序的連續(xù)要求，而且保證了連鑄前的緩沖時(shí)間嚴(yán)格控制在要求內(nèi)，用一個(gè)確定時(shí)間范圍來限制可等待時(shí)間，使鑄造前的溫度更加穩(wěn)定，降低需要重新加熱或發(fā)生穿包事故的可能性，使調(diào)度結(jié)果更符合實(shí)際生產(chǎn)。

模型中1，2，3號緩沖區(qū)以及LF1和LF2的停留時(shí)間大于等于0；規(guī)定緩沖區(qū)4的加工時(shí)間大于等于0且小于一個(gè)固定值，緩沖區(qū)4的條件是連澆連鑄的另一個(gè)硬約束，在鋼水包處理后的一定時(shí)間內(nèi)必須進(jìn)行澆鑄。普通鋼包工序的開始時(shí)間受限于以下兩方面：①同一鋼水包下一道工序的開始時(shí)間；②鋼水包前道工序的完成時(shí)間。非緩沖區(qū)類工序的完成時(shí)間等于開始時(shí)間＋工序操作時(shí)間；緩沖區(qū)類工序的完成時(shí)間等于開始時(shí)間＋緩沖時(shí)間。對于特殊的4號緩沖區(qū)，完成時(shí)間要求小于等于開始時(shí)間與某特定值之和。根據(jù)以上思路，本文建立以下問題數(shù)學(xué)規(guī)劃模型，以計(jì)算一個(gè)澆次的完整操作時(shí)間。各個(gè)工序（包括緩沖區(qū)對應(yīng)的工序）依次對應(yīng)編號為：EAF編號1，緩沖區(qū)B1編號2，緩沖區(qū)2編號3，緩沖區(qū)3編號4，AOD編號5，LF1編號6，LF2編號7，緩沖區(qū)4編號8，CC過程編號9，特殊的約束要求中下標(biāo)也直接表示工序。

一個(gè)爐次的一個(gè)工序的加工過程為一個(gè)操作。記i，j為相鄰爐次同一個(gè)工序的操作，k為操作i對應(yīng)爐次緊后工序的操作，ti為操作i的開始時(shí)間。數(shù)學(xué)模型表示如下：其中：式（1）表示在同一工序上，由于加工機(jī)器的限制條件，相鄰的鋼水包之間開始時(shí)間的約束條件；式（2）表示同一工件相鄰的兩道工序間的開始時(shí)間必須等于前一道工序的加工時(shí)間；式（3）表示特殊的緩沖區(qū)B4需要滿足的必要條件；式（4）表示任意緩沖區(qū)的停留時(shí)間必須是一個(gè)大于等于0的數(shù)值，等于0表示當(dāng)前半成品未使用此緩沖區(qū)；式（5）表示在連鑄階段兩個(gè)相鄰的鋼水包必須連續(xù)澆鑄。式（1）～式（5）用于計(jì)算單個(gè)澆次的加工時(shí)間細(xì)節(jié)，每項(xiàng)工序的最早開工時(shí)間由此動態(tài)算出。

對于不同澆次任務(wù)間的時(shí)間約束，建立以下模型。其中：i，j為相鄰的任務(wù)編號；k為不同工序的代號，k＝1～9；tik為開始任務(wù)i工序k第一個(gè)鋼水包的開始加工時(shí)間；ti0k表示開始任務(wù)i工序k最后一個(gè)鋼水包的開始加工時(shí)間；s（i）表示第i個(gè)澆次的爐次數(shù)量；pik表示當(dāng)前任務(wù)在第k道工序上所花的時(shí)間；pk0表示一個(gè)工件在第k道工序所需的完工時(shí)間，數(shù)據(jù)由條件給出；z表示任務(wù)數(shù)量。則有：

式（6）～式（11）動態(tài)計(jì)算出澆次間的時(shí)間約束，前一任務(wù)每個(gè)工序的完工時(shí)間限制后一任務(wù)相同工序的開始時(shí)間。只有保證不同時(shí)占用一臺機(jī)器，求出的解才是可行解。其中：式（6）表示相鄰任務(wù)間每項(xiàng)工序的時(shí)間約束；式（7）表示最后連鑄工序需要加上重新建立中間包的時(shí)間；式（8）表示對一個(gè)單獨(dú)任務(wù)的某項(xiàng)工序，總加工時(shí)間大于或等于爐次數(shù)乘以給定的加工時(shí)間；式（9）表示兩個(gè)相鄰任務(wù)間的約束；式（10）表示對于起始的任務(wù)，每項(xiàng)工序的開始時(shí)間都可以為0；式（11）表示起始任務(wù)的第一項(xiàng)工序開工時(shí)間為0，作為所有計(jì)算的初始條件。后續(xù)任務(wù)的工序開始時(shí)間都是相互約束的。

1．3 完工時(shí)間下界計(jì)算

對于上文的調(diào)度模型，本節(jié)給出模型完工時(shí)間下界值的計(jì)算和證明。

其中：式（12）和式（13）分別用于計(jì)算單個(gè)任務(wù)的最早完工時(shí)間（single earliest completion time）和所有任務(wù)的最早完工時(shí)間（total earliest completion time）（其中：k表示任務(wù)編號，i表示鋼水包編號，j表示工序編號）；式（14）用于計(jì)算第k個(gè)任務(wù)中的空閑時(shí)間；式（15）和式（16）都是用于粗略計(jì)算總?cè)蝿?wù)的下界時(shí)間值（lower bound）。

下面證明下界時(shí)間的計(jì)算公式。

設(shè)i和j為相鄰的澆次，j為i的后續(xù)澆次，k為澆次i的爐次數(shù)，pieaf為澆次i的冶煉過程（EAF）工序加工時(shí)間，ti1，start和ti1，complete為澆次i冶煉工序的開始時(shí)間和完成時(shí)間。

一個(gè)爐次的一個(gè)工序的加工過程為一個(gè)操作。記i，j記為相鄰爐次同一個(gè)工序的操作，k為操作i對應(yīng)爐次緊后工序的操作，ti為操作i的開始時(shí)間。數(shù)學(xué)模型表示如下：

表明澆次j的第一個(gè)爐次開始冶煉的時(shí)間至少晚于其緊前澆次i最后一個(gè)爐次冶煉的完成時(shí)間。累加所有澆次，可得

表明全部澆次在第一個(gè)工序上的完工時(shí)間和開始時(shí)間，表明工序時(shí)間之間的約束關(guān)系。

考慮最后一個(gè)澆次第一個(gè)爐次的冶煉開始時(shí)間和最后一個(gè)爐次冶煉的完成時(shí)間，可得

由式（19）和式（20），可得最后的 Makespan的一個(gè)下界值。因?yàn)槊恳粋€(gè)澆次都有可能最后一個(gè)處理，所以要對澆次編號進(jìn)行窮舉

將式（21）計(jì)算得到的最小值代入式（20），可進(jìn)一步縮小范圍。

式（16）的推導(dǎo)類似，只是把冶煉時(shí)間的約束改為連鑄時(shí)間的約束來進(jìn)行討論。

假設(shè)所有加工過程都可連續(xù)進(jìn)行，根據(jù)每個(gè)工序?qū)C(jī)器的獨(dú)占性，確保關(guān)鍵工序上無等待時(shí)間，所有4個(gè)緩沖區(qū)為0以及2個(gè)鋼水包處理過程（LF）中的時(shí)間不停留，所有的不等號能取到等于，得到最優(yōu)值。從后文的實(shí)例計(jì)算可以看出：式（16）求得的值更大，可知大批量連續(xù)煉鋼過程中，連鑄過程（CC）后面的Setup時(shí)間在很大程度上決定了總完工時(shí)間。

2 離散人工蜂群算法求解煉鋼連鑄問題

2．1 人工蜂群算法

人工蜂群算法是由Karaboga提出并用于求解數(shù)值優(yōu)化方面［12－13］的算法，提出之初，對很多基準(zhǔn)函數(shù)的測試中都體現(xiàn)出不錯的性能，而后又被用于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練、信號處理、通信應(yīng)用、腦部磁共振圖像分類［14，16］等各個(gè)領(lǐng)域。近年來，人工蜂群算法也被用于求解車間調(diào)度等離散問題，如lot streaming的流水車間調(diào)度問題［11］和資源受限的調(diào)度問題，并取得了不錯的效果［15］。

在采用人工蜂群求解各類問題時(shí)，其迭代過程中一般進(jìn)行5類操作，分別是雇傭蜂階段、評價(jià)蜜源、觀察蜂階段、記錄好的蜜源和探測蜂階段。每次迭代都是模擬蜂群的一次采蜜行為，如圖4所示。

2．2 離散人工蜂群算法求解煉鋼連鑄問題

采用離散人工蜂群算法來求解煉鋼調(diào)度問題的優(yōu)勢在于，它比人工按經(jīng)驗(yàn)或混合整數(shù)規(guī)劃法搜索的效率更高，加大了解空間的搜索范圍，能更快地求解出較優(yōu)解。

在采用離散人工蜂群算法求解調(diào)度問題的研究中，潘全科等［11］在研究大批量混合流水車間調(diào)度問題時(shí)，提出離散人工蜂群算法來求解，并提出用改進(jìn)的輪盤賭法來保留解及4種進(jìn)化的方式，而且在文獻(xiàn)［2］中也提出采用離散人工蜂群算法求解煉鋼連鑄問題。相比而言，潘全科等的模型考慮了運(yùn)輸時(shí)間和滯留時(shí)間，但沒有針對滯留時(shí)間（sojourn time）設(shè)計(jì)相應(yīng)的緩沖區(qū)。本文模型考慮到專有的緩沖區(qū)用于爐次的滯留，設(shè)計(jì)的算法更重視鄰域搜索，在雇傭蜂和觀察蜂階段，都會對當(dāng)前解進(jìn)行多次多種方式的修改，只有當(dāng)若干次探索無法優(yōu)化時(shí)才會進(jìn)入更新種群的步驟，進(jìn)而突破局部最優(yōu)的困境。

假定size為總的任務(wù)批次數(shù)量，n為雇傭蜂數(shù)量，對應(yīng)解的數(shù)量大小等于觀察蜂的數(shù)量。首先讀取所有批次的信息，包括每個(gè)連鑄任務(wù)每個(gè)階段工序所需要的時(shí)間和澆次、爐次等信息。

步驟1 生成n個(gè)由0～size－1的數(shù)字隨機(jī)排列的串，作為初始解，對應(yīng)任務(wù)的處理順序。

步驟2 對每個(gè)解的詳細(xì)信息如每道工序的開始完工時(shí)間進(jìn)行一次計(jì)算，這是因?yàn)榍耙粋€(gè)批次每一道工序的完工時(shí)間都關(guān)系到后一批次的開始時(shí)間。

步驟3 計(jì)算每個(gè)解的完工時(shí)間，設(shè)計(jì)適應(yīng)度函數(shù)并求解出每個(gè)解的累積概率，為觀察蜂的選擇做準(zhǔn)備。

步驟4 雇傭蜂過程，對每個(gè)解進(jìn)行鄰域搜索。

步驟5 如果發(fā)現(xiàn)更好的解，則替換當(dāng)前解，同時(shí)置搜索計(jì)數(shù)為零，否則搜索計(jì)數(shù)加1。

步驟6 觀察蜂過程，有觀察蜂對所有解進(jìn)行選擇，采取輪盤賭選擇法，用累積概率評價(jià)被選中的解并對其進(jìn)行鄰域搜索。該步驟是對相對好的解的加速搜索過程。

步驟7 保留歷史最優(yōu)解。

步驟8 探測蜂過程，對所有解的搜索計(jì)數(shù)進(jìn)行分析，如果有搜索計(jì)數(shù)的次數(shù)大于指定的上限，則重新初始化一個(gè)解來代替它。

適應(yīng)度函數(shù)設(shè)定為fitness＝M－tcompletion的形式，如式（21）所示，其中M 等于若干次隨機(jī)調(diào)度的平均值乘以放大系數(shù)k，以保證適應(yīng)度結(jié)果非負(fù)，可將k取值為2n，3n，5n等進(jìn)行分別測試。

解的改進(jìn)過程由三部分構(gòu)成：①針對所有解進(jìn)行優(yōu)化，即在雇傭蜂階段對解進(jìn)行鄰域搜索；②在觀察蜂階段采用輪盤賭選擇法，按解的適應(yīng)度的概率選擇解，同時(shí)也會進(jìn)行鄰域搜索，多次鄰域搜索的設(shè)計(jì)是對較優(yōu)解進(jìn)行加速搜索，以較快地得到每個(gè)局部的最好解；③在探測蜂階段跳出局部，進(jìn)行全局搜索。

鄰域搜索過程采取交換操作，即逆序操作和插入操作交互進(jìn)行，對每一種搜索方式設(shè)置一個(gè)計(jì)數(shù)值t，按某種搜索方式?jīng)]有獲得更優(yōu)質(zhì)解時(shí)，計(jì)數(shù)值t加1，當(dāng)t達(dá)到某個(gè)值時(shí)，則改變搜索方式，一旦新的搜索過程中獲得優(yōu)質(zhì)解，則將所有搜索方式的未改進(jìn)計(jì)數(shù)重新置為0，對新解進(jìn)行鄰域搜索，如此往復(fù)。

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

3．1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采用C語言編程，程序運(yùn)行環(huán)境為CPU 2．27GHz，內(nèi)存2GB。為驗(yàn)證所提算法的有效性，對某煉鋼廠大批量澆次問題，使用提出的離散人工蜂群算法優(yōu)化調(diào)度算法，求解2個(gè)大批次連鑄任務(wù)實(shí)例。實(shí)例1的數(shù)據(jù)來自文獻(xiàn)［4］，本算法能較容易地獲得已知的最優(yōu)解。實(shí)例2中的數(shù)據(jù)依據(jù)實(shí)際生產(chǎn)過程獲得，實(shí)例爐次和連鑄工序時(shí)間變化較大，加工時(shí)間不受單一因素影響，求解困難較大。實(shí)例1和實(shí)例2的完工時(shí)間下界通過2．3節(jié)公式計(jì)算，通過公式：RE＝100×（UBsolve－LB）/LB 計(jì)算每個(gè)實(shí)例的相對誤差（Relative Error，RE）。其中：LB表示下界，UBsolve表示使用算法得到的最佳適應(yīng)度。計(jì)算每組實(shí)例的RE，以評估和比較本文算法與其他算法的性能。

離散人工蜂群算法參數(shù)設(shè)置如下：設(shè)種群數(shù)量為80，每一代進(jìn)化時(shí)的鄰域搜索次數(shù)為20次，若超過10代還沒有改進(jìn)則停止搜索。參數(shù)的選擇考慮到加大鄰域搜索的效果，設(shè)置了較多的搜索次數(shù)和改進(jìn)次數(shù)。

表1 實(shí)例1數(shù)據(jù)

表2 實(shí)例2數(shù)據(jù)

3．2 實(shí)驗(yàn)結(jié)果比較與分析

3．2．1 下界時(shí)間計(jì)算

實(shí)例1的原始解是9 328．0，由式（15）求得下界為8 272．0，由式（16）式求得下界為9 138．0，取較大值，即實(shí)例1下界為9 138．0。實(shí)例2由式（15）求得下界為9 525．0，由式（16）求得下界為9 718．0，取較大值，即實(shí)例2下界為9 718．0。

對實(shí)例1和實(shí)例2的計(jì)算中，式（15）的估算值都比式（16）要小，不同澆次的吹入氣體精煉過程（AOD）工序的時(shí)間差異對完工時(shí)間的影響被最后的Setup時(shí)間彌補(bǔ)。

3．2．2 測試結(jié)果比較與分析

本文提出的離散人工蜂群算法（Discrete Artifical Colong Algorithm，DABC）與Dario Pacciarelli和Marco Pranzo［4］提出的基于集束搜索的啟發(fā)式方法，即DM算法比較如表3所示。表3給出了具體實(shí)例的規(guī)模、下界、實(shí)際應(yīng)用計(jì)劃完工時(shí)間、DM算法與DABC算法獲得最好解以及相對偏差。從表3可看出，對于比較簡單的實(shí)例1，DM算法與DABC算法都能得到實(shí)例的最優(yōu)解，該最優(yōu)解調(diào)度計(jì)劃的完工時(shí)間結(jié)果遠(yuǎn)優(yōu)于實(shí)際應(yīng)用計(jì)劃的完工時(shí)間，不過DABC算法在初始化階段就獲得問題的最優(yōu)解。對于較復(fù)雜的實(shí)例2，DABC算法獲得最好解10 155和相對誤差4．5%，優(yōu)于DM算法的最好解10 326和相對誤差6．3%。

表3提出算法與其他算法比較

實(shí)際測試過程中，實(shí)例1很快就能取得最優(yōu)解，實(shí)例2經(jīng)過了幾十次迭代和鄰域搜索才取得比較理想的優(yōu)化效果，這是由于調(diào)度限制因素，使連鑄階段的加工時(shí)間差距較大，不同澆次的爐次數(shù)相差大，澆次間的Setup時(shí)間不能彌補(bǔ)不合理調(diào)度的時(shí)間損失，問題難度較大。雖然DM算法能得到實(shí)例1的最優(yōu)解，但是對于實(shí)例2，由于爐次數(shù)以及各工藝過程處理時(shí)間的差異較大，DM算法的搜索效果不佳。可以看出，針對結(jié)構(gòu)復(fù)雜的大批量任務(wù)，本文提出的離散人工蜂群算法能獲得更好的結(jié)果。

離散人工蜂群算法得到實(shí)例1最優(yōu)解的任務(wù)處理順序?yàn)椋海?7，10，18，21，9，26，2，28，29，30，3，6，16，22，25，15，19，27，14，5，24，31，8，11，1，4，12，23，7，20，32，13，34，33｝，總完工時(shí)間為9 138。獲得實(shí)例2最好解的任務(wù)處理順序?yàn)椋海?4，24，14，9，8，6，32，25，15，1，16，11，13，33，2，29，20，23，27，2817，31，5，19，12，18，30，3，26，7，21，22，4，10｝，總完工時(shí)間為10 040。

最后對大批次實(shí)例進(jìn)行測試，測試實(shí)例的爐次數(shù)在1～7次，澆次、冶煉、精煉、澆鑄和緩沖時(shí)間也是按照工廠數(shù)據(jù)進(jìn)行隨機(jī)生成，測試結(jié)果如表4所示。

表4 隨機(jī)測試結(jié)果

可以看出，離散人工蜂群算法對于隨機(jī)生成的大批次效果比較明顯。由于每個(gè)澆次各工序測試數(shù)據(jù)的差異，爐次數(shù)也取的比較大，得到的調(diào)度完工時(shí)間都沒有獲得理論的下界值，但是都能夠有效調(diào)整優(yōu)化調(diào)度方案。最好的優(yōu)化達(dá)到2．8%，最差的優(yōu)化為8．2%，由于每個(gè)澆次和爐次數(shù)與不同工序的處理時(shí)間的差異，實(shí)際調(diào)度情況的優(yōu)化效果也有一定的差異。

4 結(jié)束語

本文針對實(shí)際大批次煉鋼連鑄問題建立線性約束模型，給出完工時(shí)間的下界計(jì)算公式。該模型考慮了緩沖區(qū)的數(shù)量和等待時(shí)間受限，能求解每個(gè)爐次的加工時(shí)間、完工時(shí)間、工序間選擇的緩沖器和緩沖時(shí)間。在調(diào)度方案的調(diào)整方面，提出采用離散人工蜂群算法進(jìn)行優(yōu)化，并介紹了該算法的原理及其搜索機(jī)理；針對建立的數(shù)學(xué)模型和問題，設(shè)計(jì)了相應(yīng)的編碼、鄰域搜索策略、評價(jià)函數(shù)以及離散人工蜂群算法的求解步驟。

根據(jù)某工廠的實(shí)際數(shù)據(jù)和生產(chǎn)情況可能的數(shù)據(jù)，以及計(jì)算的完工時(shí)間下界，將提出的算法與其他算法進(jìn)行了比較，驗(yàn)證了提出算法求解煉鋼連鑄調(diào)度問題的正確性和有效性。下一步的研究目標(biāo)是將本文算法擴(kuò)展到大批量動態(tài)煉鋼工廠的調(diào)度問題中，探索更高效的算法，以解決更大規(guī)模、更加復(fù)雜的煉鋼連鑄優(yōu)化問題。

［1］ BELLABDAOUI A，TEGHEM J．A mixed－integer linear programming model for the continuous casting planning［J］．International Journal of Production Economics，2006，104（2）：260－270．

［2］ PAN Quanke，WANG Ling，MAO Kun，et al．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．

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

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

［5］ LIU Wei，SUN Liangliang．Steel－making and continuous/ingot casting scheduling of mixed charging plan based on batch splitting policy［J］．International Journal of Iron and Steel Rresearch，2012，19（2）：17－21．

［6］ ATIGHEHCHIAN A，BIJARI M，TARKESH H．A novel hybrid algorithm for scheduling steel－making continuous casting production［J］．Computers＆Operations Research，2009，36（8）：2450－2461．

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

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

［9］ PANG Xinfu，YU Shengping，LUO Xiaochuan，et al．Hybrid job shop rescheduling method and its application for steel－making casting［J］．Systems Engineering—Theory ＆ Practice，2012，32（4）：826－838（in Chinese）．［龐新富，俞勝平，羅小川，等．混合Jobshop煉鋼—連鑄重調(diào)度方法及其應(yīng)用［J］．系統(tǒng)工程理論與實(shí)踐，2012，32（4）：826－838．］

［10］ LI Tieke，SU Zhixiong．Two－stage GA algorithm 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．］

［11］ PAN Quanke，F(xiàn)ATIH TASGETIREN M，SUGANTHAN P N，et al．A discrete artificial bee colony algorithm for the lotstreaming flowshop scheduling problem［J］．Information Sciences，2011，181（12）：2455－2468．

［12］ KARABOGA D．An idea based on honey bee swarm for numerical optimization［EB/OL］．［2012－03－03］．http：//mf．erciyers．edu．tr/abc/pub/trob＿2005．pdf．

［13］ KARABOGA D，BASTURK B．A powerful and efficient algorithm for numerical function optimization：artificial bee colony（ABC）algorithm［J］．Journal of Global Optimization，2007，39（3）：459－471．

［14］ KARABOGA D，AKAY B，OZTURK C．Artificial bee colony（ABC）optimization algorithm for training feed－forward neural networks［J］．Lecutre Notes in Computer Science，2007，4617：318－329．

［15］ SUN Xiaoya．Artificial bee colony algorithm for resourceconstrained project schedulingproblem［J］．Technology and Method，2011，30（19）：70－75（in Chinese）．［孫曉雅．人工蜂群算法求解資源受限項(xiàng)目調(diào)度問題［J］．技術(shù)與方法，2011，30（19）：70－75．］

［16］ ZHANG Y，WU L，WANG S．Magnetic resonance brain image classification by an improved artificial bee colony algorithm［J］．Progress in Electromagnetics Research，2011，116（7）：65－79．

［17］ LIU Yanfeng，LIU Sanyang．A hybrid discrete artificial bee colony algorithm［J］．Applied Soft Computing，2011，1384：1－5．DOI：10．1109/ICCIE．2009．5223810．

［18］ DOU Jianping，SU Chun，LI Jun．Discrete particle swarm optimization algorithms for assembly line balancing problems of type 1［J］．Computer Integrated Manufacturing Systems，2012，18（5）：1021－1030（in Chinese）．［竇建平，蘇 春，李?。蠼獾谝活愌b配線平衡問題的離散粒子群優(yōu)化算法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2012，18（5）：1021－1030．］

［19］ TANG Qiuhua，CHEN Weiming，JIANG Guozhang，et al．Research on steel－making continuous－casting scheduling model base on JIT［J］．Journal of Wuhan University of Science and Technology：Natural Science Edition，2008，31（1）：78－82（in Chinese）．［唐秋華，陳偉明，蔣國璋，等．基于JIT的煉鋼連鑄生產(chǎn)調(diào)度模型研究［J］．武漢科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，31（1）：78－82．］