多目標中間包計劃模型及混合優化算法

馬天牧,羅小川?,柴天佑,2

(1.東北大學流程工業綜合自動化國家重點實驗室,遼寧沈陽110819; 2.東北大學自動化研究中心,遼寧沈陽110819)

多目標中間包計劃模型及混合優化算法

馬天牧1,羅小川1?,柴天佑1,2

(1.東北大學流程工業綜合自動化國家重點實驗室,遼寧沈陽110819; 2.東北大學自動化研究中心,遼寧沈陽110819)

中間包計劃是重要的煉鋼–連鑄批量計劃之一,其功能是在給定的爐次計劃中,根據煉鋼–連鑄生產能力及下游工序生產所需材料的數量,挑選出待生產的爐次并制定出合理的中間包使用數量及每個中間包內生產的爐次.在對中間包計劃問題描述的基礎上及現有文獻中未考慮中間包利用率及中間包內爐次寬度差異性,建立了多目標中間包計劃數學模型.為了求解模型將模型分解為兩個子模型,并針對兩個子模型設計了迭代局部搜索算法(iterated local search,ILS)及變鄰域搜索算法(variable neighborhood search,VNS)相結合的雙層混合算法,考慮到中間包利用率及多目標權重對解的影響,在算法中加入了可調整模型參數的方法,最后用實際生產數據對模型及算法進行驗證.

中間包計劃;多目標;迭代局部搜索;變鄰域搜索;混合算法

1 引 言

煉鋼–連鑄工序是整個鋼鐵生產過程的瓶頸工序,其特點是生產前設備準備時間長,生產過程中要求高溫連續,生產的產品必須能夠充分供應后續工序生產需求.因此合理有效制定其生產計劃可以充分提高設備利用率、減少設備因停機準備的時間,使前后工序協調生產.煉鋼–連鑄生產計劃的管理分為批量計劃和調度計劃,其中批量計劃的功能是確定每日或班組的生產任務,包括爐次計劃、中間包計劃、澆注計劃,調度計劃的功能是為生產任務確定設備及生產起止時間.本文主要討論中間包計劃.中間包計劃是在爐次計劃的基礎上,負責考慮在滿足本工序生產能力的同時,還要滿足其下游生產工序正常生產所需原料的供給,其作用重于爐次計劃.煉鋼–連鑄生產過程涉及的設備種類多、工藝路徑復雜,其調度計劃一直是國內外學者和工程技術人員研究的熱點,對調度計劃的研究從靜態調度發展到動態調度、重調度和鋼包調度[1?5].而對批量計劃研究較少[6],目前對中間包計劃研究較為深入的有文獻[7,8].文獻[7]提出了中間包批量計劃,并將其歸結為車輛路徑問題(vehicle routing problem,VRP),以最少中間包數、未組入中間包爐次懲罰、下游工序需求為目標.文獻[8]將中間包計劃歸結為能力受限的調度問題建立了多目標模型,其在目標中考慮了最少中間包數、下游工序需求,開發了新型的變鄰域搜索方法.但兩者沒有考慮中間包利用率變化及爐次寬度區間相似性，且都僅采用一組實例數據驗證.在工廠里中間包計劃主要是由計劃人員采用試湊的方法編制,計劃的質量取決于人的經驗,并且每次都需耗費大量的時間.

基于以上問題,本文以某大型鋼鐵企業實施制造執行系統(manufacturing execution system,MES)項目為背景,在描述該企業的中間包計劃問題基礎上,建立多目標的中間包批量計劃數學模型.為了求解模型,首先將模型分解為兩個子模型,然后設計了迭代局部搜索與變鄰域搜索相結合的雙層混合優化算法,由于中間包利用率是可變化的且對問題的解有影響,同時考慮到多目標轉換為單目標時權重對解也有影響,因此在算法中加入了動態改變中間包利用率及權重的方法,最后采用現場中多組數據進行驗證.

2 中間包計劃問題描述及數學模型

2.1 問題描述

在煉鋼–連鑄生產中,中間包是連鑄機上用來盛鋼水的容器.中間包具有一定的使用壽命,根據所盛鋼水的成本不同使用壽命不同,一般在4爐～6爐,且不論是否達到使用壽命都需要對其耐高溫層維護,每次維護的成本是很可觀的[7].使用同一中間包澆鑄的鋼水成份和相應板坯澆鑄寬度必須相同或相近.當出現鋼水成份或寬度調整(寬度每次調整幅度最大100 mm,最小50 mm)時，會分別出現叫做交接坯和梯形坯的兩類板坯.這兩類板坯在實際生產中都是需要減少或避免的。

在制定中間包計劃時,其輸入是爐次計劃和生產指標,爐次計劃給定了爐次的數量及每個爐次的屬性,這些屬性包括出鋼記號,爐次所生產板坯的最大寬度、最小寬度,爐次是否為精煉爐,可用于下游工序使用的板坯重量(可能包含一個工序或幾個工序的加工量)、所需要中間包的類型.生產指標中給定了下一個生產周期所要生產的總爐次數目標及上、下限,總精煉爐次數目標及上、下限,熱軋工序所需要的燙輥材目標重量及上大下限,熱軋工序下游各機組所需要加工板坯的目標重量及上、下限.中間包計劃的任務就是滿足生產約束的前提下使用最少的中間包數量在給定的爐次計劃中挑選爐次以達到生產指標中給定的目標或范圍.

2.2 數學模型

下面介紹本文使用的數學符號:爐次集合N={1,2,...,n},中間包集合M={1,2,...,m},下游生產工序集合F={1,2,...,f},i,j為爐次號,i∈N,j∈N.k為中間包號,k∈M.l為生產工序號,l∈F.爐次相關屬性如下:爐次的寬度區間為Ii=[w,w],爐次的出鋼記號為sgi,爐次未組入中間包的懲罰成本為bi,爐次寬度所對應的數值為vi,爐次i中所包含燙輥材的重量為hi,爐次i的精煉標志為ri,爐次i所使用的中間包類型號為tsgi,爐次i包含下游生產工序l所需要板坯重量為fil.中間包相關屬性如下:中間包k的使用壽命為Tk,中間包k的使用成本為sk,中間包壽命使用系數為β.生產約束相關符號:寬度調整的最大幅度為△whMax,寬度調整次數為△n.生產指標相關符號:生產指標中規定的目標爐次數、上限、下限為CHG、CHU、CHL,生產指標中規定的可生產的精煉爐次數目標、上限、下限為RHG、RHU、RHL,生產指標中規定的熱軋工序所需要的燙輥材(用來加熱熱軋軋輥的板坯)目標重量、上限、下限為HG、HU、HL,生產指標中規定的下游工序l所能生產的目標重量、上限、下限為、、.其它參數:爐次i與爐次j組入到同一中間包的懲罰系數為cij,根據以下三個式子計算得到,即

其中r1、r2、r3為常數,D為比較大的常數,式(3)中的vi是由爐次的寬度區間計算得到的,可以通過該數值來計算寬度區間的差異,vi的計算過程采用文獻[9]計算區間數排序向量的步驟:

步驟1基于S函數的相對優勢度公式(4)對區間數進行兩兩比較,將P(Ii?Ij)簡寫為pij,則所建立的相對優勢度矩陣為P=(pij)n×n.

引入如下決策變量

中間包計劃的數學模型為

其中目標函數式(5)第一項表示中間包使用成本,第二項表未組入中間包爐次懲罰成本,第三項表示中間包剩余使用壽命,第四項表示組入到同一中間包內爐次間差異.目標函數式(6)表示最小化組入中間包計劃的爐次數與生產指標規定的目標爐次數的差.目標函數式(7)表示最小化組入中間包計劃的精煉爐次數與生產指標規定的目標精煉爐次數的差.目標函數式(8)表示最小化組入中間包的燙輥材重量與生產指標規定的目標燙輥材重量的差.目標函數式(9)表示最小化組入中間包的各下游機所需加工板坯重量與生產指標規定的各下游機組所需加工板坯目標重量的差.約束式(10)確保爐次最多只能組入到一個中間包內.約束式(11)確保組入到中間包內的爐次必須滿足中間包的使用壽命.約束式(12)～(15)是生產指標約束.約束式(16)、(17)分別為寬度調整幅度、次數約束.約束式(18)確保組入到同一梓里包內的爐次的中間包類型必須相同.式(19)、(20)是變量定義.

中間包計劃模型實質是經典裝箱的擴展.忽略目標式(6)～(9),及目標函數式(5)中的第二、三、四項時,及約束式(12)～(18)時,模型就成為變成本的裝箱問題;在此基礎上加入式(5)中的第二項,則模型是帶有拒絕成本的裝箱問題.而這兩種裝箱問題的求解在文獻中都被證明是NP-hard,于是經典裝箱問題是中間包計劃模型的一個特例,且輸入的爐次數一般在100爐～300爐之間,因此在實際應用中需要開發有效的啟發式算法以快速求解.

3 可動態調整參數的雙層ILSVND混合算法

3.1 模型分解

觀察模型,可以看到式(5)含義是用最少的中間包生產給定的爐次,若將中間包看作箱、爐次看作物品,那么該問題可以歸結為裝箱問題;而式(6)～(9)及約束(12)～(15)是規定組入中間包的爐次必達到的目標和約束.約束(12)～(15)描述的是下游工序機組的能力,結合目標(6)～(9),將該子問題看作是背包問題.這樣看來,中間包計劃問題包含了裝箱和背包兩種問題在里面.由此可以想到兩種策略達到上述目的.第一種策略是先考慮背包再裝箱,即首先根據約束(12)～(15)先選擇爐次,然后將爐次組成中間包,最后以爐次為單位進行局部優化.第二種策略是先考慮裝箱主考慮背包,即先將爐次組成中間包,然后根據約束選擇中間包,最后分別以中間包和爐次為單位進行局部優化.但第一種策略存在的問題是,由于缺少對“箱子”的約束而難以保證根據能力約束選擇出的爐次所組成的中間包數的數量是最少的.因此選擇第二種策略.根據第二種策略,將模型分解為兩個模型,第一個模型的目的是將爐次組成中間包,將其叫做組中間包模型,用M1表示該模型;第二個模型的目的是選擇中間包和爐次,將其叫做選中間包模型,用M2表示該模型.則這兩個模型可以表示如下

M1:

M2:

3.2 ILSVND混合優化算法

本文采用ILS與VND算法相結合的混合算法對中間包計劃模型求解.ILS和VNS兩種啟發式算法提供了簡潔而有力的局部搜索能力.兩種算法在組合優化、調度[10]、車輛路徑[11]、選址[12]等實際問題中得到了應用.ILS算法首先構造初始解,然后采用迭代機制通過內部的局部搜索方法(local search)和攝動方法(perturbation)構建一系列解,最后通過某些準則輸出歷史最好解.其中最重要的兩個步驟是局部搜索和攝動,攝動步驟就是用來做局部搜索無法做到的一些對解的改動.VND(variable neighborhood descent)是VNS算法的一個擴展.該算法起始于一個初始解和鄰域結構集合.在每步迭代中,算法尋找每個鄰域結構中最小目標函數值的解,并與原來的解比較以選擇鄰域結構.最后輸出最好的解[13,14].

前一節,將整個中間包計劃模型分解為兩個子模型.兩個子模型中都含有參數,其中第一個子模型有三種參數:中間包使用成本、中間包剩余容量單位懲罰成本、中間包利用率三個參數,第二個子模型中的參數是加權系數.通常情況下,這些參數都是在算法求解模型之前根據經驗確定的,在算法計算過程中這些參數不變.然而對于中間包計劃模型,這樣做存在兩個問題:1)當第一個子模型的參數確定后得到的較好的解,不能夠保證第二個子模型得到較好的解.2)第二個子模型的目的是在較充分使用中間包壽命的前提下,所選擇的中間包及爐次盡量與生產指標中給定的目標值相近,而固定的權重值不能反映算法求解過程中得到的解與生產指標差異的大小.

為了解決以上兩個問題,設計了如圖1所示的具有動態調整模型參數的混合算法框架.在圖1中,r表示生產指標給定值,y表示算法求解后得到的生產指標值.將兩者進行比較得到差值e,利用這個差值及更新目標權重操作修改第二子模型中的權重值λ(包括λch、λrh、λh、λl).更新中間包利用率操作的目的是在算法求解過程中調整第一個子模型中的中間包利用率參數β.下面先介紹算法中的主要步驟：生成初始解、鄰域操作、調整權重系數、調整中間包利用率，最后給出整個算法的步驟.

算法1中兩個初始解操作都采用啟發式算法.第一層ILSVND算法的初始解,首先按爐次的最小寬度降序排序,當爐次最小寬度相同時,按其最大寬度降序排序,對排好序的爐次集合利用求解裝箱算法的最佳適應算法(best ft,BF)規則將爐次組成中間包,得到的初始解記為x0.第二層ILSVND算法的初始解采用貪婪算法.具有步驟為,對中間包按中間包內爐次數降序排序,根據約束(13)挑選精煉爐次,滿足約束后再根據約束(12)挑選爐次,直到滿足約束為,得到的解記為s0.

圖1 具有參數動態調整的雙層ILSVND混合算法框架Fig.1 Algorithm framework of double layers ILSVND with adjusting parameters dynamically

3.2.1 生成初始解

算法1中兩個初始解操作都采用啟發式算法.第一層ILSVND算法的初始解,首先按爐次的最小寬度降序排序,當爐次最小寬度相同時,按其最大寬度降序排序,對排好序的爐次集合利用求解裝箱算法的最佳適應算法(best ft,BF)規則將爐次組成中間包,得到的初始解記為x0.第二層ILSVND算法的初始解采用貪婪算法.具有步驟為,對中間包按中間包內爐次數降序排序,根據約束(13)挑選精煉爐次,滿足約束后再根據約束(12)挑選爐次,直到滿足約束為,得到的解記為s0.

3.2.2 鄰域操作

在使用VND算法中,設計了如下幾種鄰域操作,其中N1～N4針對第一層ILSVND算法,N5～N8針對第二層ILSVND算法.

N1–交換中間包爐次.在中間包數不變的前提下,該鄰域操作通過交換已組入中間包的爐次來試圖改善目標函數(5)中同一中間包內爐次間差異.首先在當前解中任意選擇兩個中間包,并在每個中間包內任意選擇一個爐次,如果在滿足停止條件前,這種交換能夠滿足約束并改善目標函數,則接受該交換.

N2–插入爐次.在中間包數不變的前提下,該鄰域操作通過將未組入中間包的爐次插入到中間包中來改善目標函數(5)中中間包使用壽命、減少未組中間包的爐次及中間包內爐次間差異.首先在當前解中選擇一個中間包及未組中間包的爐次,將該爐次插入到選擇的中間包內,若在滿足停止條件前該操作能夠滿足約束及改善目標函數,則將爐次插入到中間包內.

N3–移除爐次.在中間包數不變的前提下,該鄰域操作通過移除爐次來改善目標函數(5)中中間包內爐次間差異.首先在當前解中任意選擇一個中間包,將該中間包內的爐次分別移除,若在滿足停止條件前,該操作能夠改善目標函數的話,則接受該操作.

N4–交換中間包爐次與未組中間包爐次.在中間包數不變的前提下,該鄰域操作試圖將通過交換已組入中間包的爐次與未組入中間包的爐次來改善目標函數(5)中的未組中間包爐次懲罰成本及中間包內爐次間差異.首先在當前解中任意選擇一個中間包,將該中間包內的爐次分別與未組中間包的爐次交換,若在滿足停止條件前,這種交換能夠改善目標函數,則接受該操作.

N5–交換已選中的中間包與未選中的中間包內爐次.在生成第二個子模型的初始解后,整個解包含三部分:選中的中間包、未選中的中間包、未組中間包的爐次.該操作針對目標函數(21),在爐次數不變的前提下,交換選中的中間包與未選中的中間包內爐次.首先任意選擇一個已選中的中間包,在任意選擇一個未選中的中間包,逐個交換兩個中間包的爐次,若在滿足停止條件前,這種交換操作能夠改善目標函數(21),則接受該交換操作.

N6–交換選中的中間包爐次與未組中間包爐次.該操作針對目標函數(21),在爐次數不變的前提下,將選中的中間的爐次與未組中間包的爐次進行交換,若在滿足停止條件前,該操作能夠改善目標函數,則接受該操作.

N7–插入爐次.該操作針對目標函數(21),通過將未組中間包的爐次或未選中中間包內爐次插入到選中的中間包內來改善目標函數.在當前解中選擇還有剩余容量的中間包,將未組中間包的爐次插入到該中間包內,若在滿足停止條件前,這樣的插入操作能夠改善目標函數,則接受該操作.

N8–移除爐次.與N7相反,該操作針對目標函數(21),通過移除選中的中間包內的爐次來改善目標為數.在當前解中任意選擇一個中間包,分別移除該中間包的爐次,若在滿足停止條件前,該操作能夠改善目標函數,則接受移除操作.

3.2.3 調整權重系數

算法中的更新目標權重操作用來對各目標權重系數進行調整,權重系數的調整如下

其中λ和λ′分別表示某一目標的權重系數的當前值及前值,σ表示一個給定的正數,e表示當前指標差異值,g表示指標的目標值,g′表示當前算法得到的實際值.

3.2.4 調整中間包利用率

算法中的更新中間包利用率操作用來對子模型M1中的中間包利用率系數進行調整.一般來說中間包成本及剩余容量的成本在一定時期內是固定不變的,即子式(5)中的sk和pk,中間包使用壽命的利用率是可變的.β對模型的影響表現在中間包空間的利用上.例如當β=0.5時,表示當中間包的使用壽命達到一半時就認為對該中間包使用壽命的利用是充分的,這種情況下就增加了中間包的數量.當β=1時,就要求中間包使用壽命必須全部利用上,不允許有剩余使用空間,這種情況下就減少了中間包的數量.而中間包數量的多與少,對子模型M2是有影響的.當中間包數少時,可能選擇不出滿足指標的爐次數,而當中間包數多的時候,中間包剩余的使用壽命又可能會太多.因此為改善這種情況采用如下策略:在某一固定的β下,通過求解模型M1及M2得到一個解,當該解在調整權重后仍沒有改進時,通過式(51)改變β值,β′為當前循環周期內中間包利用率的值,當β′+0.1>1時取β=β′?0.1,當β′?0.1<0.6時,取β=β′+0.1,且規定中間包的利用率必須在一半以上,即β>0.6.

3.2.5 攝動

在第一層VND算法中,所有的鄰域操作都是在中間包數目不變的前提下進行的.中間包數變化時,其影響到的爐次是鄰域結構所不能描述的,但其對解確實有影響.因此將這種因中間包數變化對解的影響作為攝動操作.中間包數的變化是雙向的,既可以增加其數量,又可以減少其數量.把這兩個方向的變化都作為第一層算法的攝動操作.對于第二層算法,將隨機選擇選中的中間包內爐次與未選中中間內爐次及未組中間包爐次交換作為攝動操作.

下面給出整個算法的步驟,其中步驟1～步驟6是第一層ILSVND混合算法,步驟7～步驟14是第二層ILSVND混合算法.對于新解接受標準,本算法中采用接受較好解的方法,非支配排序負責對多個解進行非支配排序.

步驟1生成初始解x0;

步驟2對x0進行變鄰域搜索得到x?; /*即用變鄰搜索搜索算法替換原算法中的局部搜索*/

步驟3對x?進行攝動操作得到解x’;

步驟4對解x’進行變鄰域操作得到解x?’; /*即用變鄰搜索搜索算法替換原算法中的局部搜索*/

步驟5根據接受標準對x?、x?’進行是否接受的判斷并得到解x?;

步驟6若未達到循環迭代次數最大值,則轉步驟7,否則轉步驟3;

步驟7根據x?生產初始解s0;

步驟8對解s0進行變鄰域搜索得到解s?; /*即用變鄰搜索搜索算法替換原算法中的局部搜索*/

步驟9對解s?進行攝動操作得到解s’;

步驟10對解s’進行變鄰域操作得到解s?’; /*即用變鄰搜索搜索算法替換原算法中的局部搜索*/

步驟11根據接受標準對解s?,s?’進行是否接受的判斷并得到解s?;

步驟12若達到循環迭代次數最大值,則轉步驟13,否則轉步驟9;

步驟13更新權重參數,轉步驟9,否則轉步驟;

步驟14若達到循環迭代次數最大值,轉步驟15,否則轉步驟9;

步驟15更新中間包利用率參數;

步驟16若未到循環迭代次數最大值,更新權重參數,轉步驟17,否則轉步驟7;

步驟17若未達到循環迭代次數最大值,更新權重參數,轉步驟1,否則轉步驟18;

步驟18對解進行非支配排序;

步驟19輸出解s?.

4 算例驗證

表2中給出了ILSVND算法、標準ILS算法及人工編制的結果對比,其中β是模型中的中間包利用率系數,“定權重”表示固定多目標權重方法,“變權重”表示本文所提出的變化目標權重方法.從表中可以看出:1)各個實例出現的最好解所對應的β值是不同的,例如實例1在β=1,0.8,0.6出現比較好的解,這說明如果像常規求解模型時固定模型參數所得到的結果沒有變化參數時的結果好.2)在相同β值下,變目標權重方法得到的結果大部分好于固定目標權重的方法,且變權重方法得到的解與目標值更加接近.3)同一組數據實例, ILSVND算法可以找到幾個較好的解供計劃員挑選.4)ILS算法同ILSVND算法對比,可以看出無論是變權重還是固定權下,ILS算法得到的結果都沒有ILSVND算法好.例如實例2中當β=0.6時,ILS算法得到的總爐次數結果超出生產指標上限5爐,此外該算法得到的大多數結果中都無法均衡的滿足生產指標中對燙輥材、各流向的要求.5)與人工計劃結果對比,人工計劃編制的中間包數普遍比模型得出的結果要多,中間包剩余壽命卻比模型得到的結果多,在生產中使用中間包的個數越少說明生產成本越少,中間包剩余使用壽命越少說明中間包利用率越高.

表1 實例數據信息Table 1 Information of problem instances

觀察實例2得到的結果,沒有完全符合企業給定的目標,例工序037、057等給定的目標值是0,而實際結果卻不是0.為此作者對輸入的爐次數據進行了分析,發現實例3所對應的爐次中,工序037所需要材料與工序038所需要材料大多數是在同一爐次中,而企業對工序038的目標是生產400 t,這說明要想滿足工序038所需要的量,那么必然會有工序037的量在結果中.相同的情況也出現在工序204、工序21B中,這兩個工序加工的材料與工序23N均出現在同一爐次中.由此可以看出,爐次計劃編制時若考慮將同一工序所需要的材料放在同一爐次中有利于中間包計劃的制定.

表2 實驗結果Table 2 Experimental result

續表2Table 2 Continue

表3 中間包內爐次差異結果對比Table 3 The results of comparing the differences between the charges in tundish

由于模型中的二次項是用來優化中間包內爐次間差異的,因此在表3中給出了實例1中對模型中有二次項及去掉二次項的結果對比.表中成份調整指中間包內爐次出鋼記號個數,寬度數表示中間包內爐次可取的寬度數,跳躍次數表示中間包是否進行了寬度調整.從結果中看出,有二次項時中間包內的成份調整次數比模型中無二次項時少2次,而寬度選擇的個數多了3個.這說明考慮爐次間差異可以降低中間包內成份的調整次數和增加寬度選擇個數,這些都是有利于連鑄機連續生產的.

5 結束語

本文針對實際工程中遇到的中間包計劃問題,建立了多目標數據模型,第一個目標中綜合考慮中間包數、未組入中間包爐次懲罰、中間包利用率及中間包爐次間關系,其它目標則考慮生產能力及煉鋼–連鑄下游生產需求量.為了求解模型將問題分解為兩個子模型,考慮到中間包利用率及多目標權重對解都有影響,在設計迭代局部搜索算法與變鄰域搜索算法結合的混合算法中加入了變參數調整功能,最后采用現場實際數據對模型和算法的有效性進行了驗證.在實際的驗證中發現了爐次計劃由于未將具有相同生產方向的材料放入一個爐次中而對中間包計劃產生影響,因此下一步需要深入研究這兩個計劃之間的協調,同時也要研究中間包計劃對澆鑄計劃是否有影響.

[1]Li J,Xiao X,Tang Q,et al.Production scheduling of a large-scale steelmaking continuous casting process via unit-specifc eventbased continuous-time models:Short-term and medium-term scheduling[J].Industrial&Engineering Chemistry Research,2012, 51(21):7300–7319.

[2]龐新富,俞勝平,張志宇,等.煉鋼–連鑄生產優化重調度方法[J].系統工程學報,2010,25(1):98–103.

Pang Xinfu,Yu Shengping,Zhang Zhiyu,et al.Optima rescheduling for steelmaking-continuous casting[J].Journal of Systems Engineering,2010,25(1):98–103.(in Chinese)

[3]俞勝平,柴天佑,鄭秉霖.煉鋼連鑄混合智能優化調度方法及應用[J].系統工程學報,2010,25(3):379–386.

Yu Shengping,Chai Tianyou,Zheng Binglin.Hybrid intelligent optimal scheduling method for steelmaking and continuous casting and its application[J].Journal of Systems Engineering,2010,25(3):379–386.(in Chinese)

[4]王秀英,柴天佑,鄭秉霖.煉鋼–連鑄調度模型參數優化設定方法[J].系統工程學報,2011,26(04):531–537.

Wang Xiuying,Chai Tianyou,Zheng Binglin.Parameter optimization setting and continuous casting scheduling model[J].Journal of Systems Engineering,2011,26(4):531–537.(in Chinese)

[5]譚圓圓,魏 震,王 森,等.基于VRPTW-AT模型的鋼包優化調度方法[J].系統工程學報,2013,28(1):94–100.

Tan Yuanyuan,Wei Zhen,Wang Sen,et al.Optimization algorithm for ladle scheduling based on the VRPTW-AT model[J].Journal of Systems Engineering,2013,28(1):94–100.(in Chinese)

[6]馬天牧,羅小川,柴天佑.基考慮轉爐容量和寬度的爐次計劃混合優化方法[J].系統工程學報,2013,28(5):694–701.

Ma Tianmu,Luo Xiaochuan,Chai Tianyou.Hybrid optimization for charge planning considering the leftover of charge and width[J]. Journal of Systems Engineering,2013,28(5):694–701.(in Chinese)

[7]Tang L X,Wang G S.Decision support system for the batching problems of steelmaking and continuous-casting production[J]. Omega:International Journal of Management Science,2008,36(6):976–991.

[8]Dong H Y,Huang M,Wang X W.Improved variable neighbourhood search for integrated tundish planning in primary steelmaking processes[J].International Journal of Production Research,2012,50(20):5747–5761.

[9]謝 海.基于改進的相對優勢度的區間數排序[J].科學技術與工程,2007,8(22):5983–5987.

Xie Hai.Improved relative superiority method for ranking interval numbers[J].Science Technology and Engineering,2007, 8(22):5983–5987.(in Chinese)

[10]Della C,Garaix T,Grosso A.Iterated local search and very large neighborhoods for the parallel-machines total tardiness problem[J]. Computers&Operations Research,2012,39(6):1213–1217.

[11]Laurent B,Hao J K.Iterated local search for the multiple depot vehicle scheduling problem[J].Computers&Industrial Engineering, 2009,57(1):277–286.

[12]Lamb J D.Variable neighbourhood structures for cycle location problems[J].European Journal of Operational Research,2012, 223(1):15–26.

[13]Jarboui B,Derbel H,HanafS,et al.Variable neighborhood search for location routing[J].Computers&Operations Research,2013, 40(1):47–57.

[14]Xiao Y,Kaku I,Zhao Q.A variable neighborhood search based approach for uncapacitated multilevel lot-sizing problems[J].Computers&Industrial Engineering,2011,60(2):218–227.

Multi-objective tundish planning model and hybrid optimization algorithm

Ma Tianmu1,Luo Xiaochuan1?,Chai Tianyou1,2
(1.State Key Laboratory of Synthetical Automation for Process Industries,Northeastern University,Shenyang 110819, China; 2.Research Center of Automation,Northeastern University,Shenyang 110819,China)

Tundishplanningisoneofthemostfundamentalbatchplanningproblemsinsteelmakingcontinuous casting.It determines how many tundishes are used to produce charges regarding the capacity of steelmaking and the quantity required by the downstream.Based on the description of the tundish planning problem and the shortcoming of existing tundish planning methods in the literature,a multi-objective mathematical model is built.The model was divided into two sub-models for solving,and a two-layer hybrid algorithm is presented by combining the iterated local search with variable neighborhood search.Considering the utilization of tundishes and the weights of multiple objectives,two methods for adjusting the parameters of the algorithm were introduced.Finally,real-world data are used to test the model and algorithm.The results show the effectiveness of the model and algorithm.

tundish planning;multi-objective;iterated local search;variable neighborhood search;hybrid algorithm

*通訊作者

TP273

A

1000?5781(2015)04?0451?15

10.13383/j.cnki.jse.2015.04.003

2013?04?08;

2014?04?03.

國家自然科學基金資助項目(71021061;60974091;61174187;61104174);國家973重點基金研究發展計劃資助項目(2009CB320601);高校學科創新引智計劃資助項目(B08015).

馬天牧(1977—),遼寧阜新人,男,博士生,研究方向:流程工業計劃調度,優化算法,Email:mtm309@163.com;

羅小川(1974—),四川西充人,男,博士,教授,博士生導師,研究方向:復雜工業過程運行優化與控制,Email:luoxch@mail.neu.edu.cn;

柴天佑(1947—),甘肅蘭州人,男,博士,教授,中國工程院院士,研究方向:流程工業綜合自動化,Email:tych@mail.neu.edu.cn.