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

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

多目標中間包計劃模型及混合優(yōu)化算法

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

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

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

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

1 引 言

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

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

2 中間包計劃問題描述及數(shù)學模型

2.1 問題描述

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

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

2.2 數(shù)學模型

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

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

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

引入如下決策變量

中間包計劃的數(shù)學模型為

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

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

3 可動態(tài)調(diào)整參數(shù)的雙層ILSVND混合算法

3.1 模型分解

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

M1:

M2:

3.2 ILSVND混合優(yōu)化算法

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

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

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

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

圖1 具有參數(shù)動態(tài)調(diào)整的雙層ILSVND混合算法框架Fig.1 Algorithm framework of double layers ILSVND with adjusting parameters dynamically

3.2.1 生成初始解

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

3.2.2 鄰域操作

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

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

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

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

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

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

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

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

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

3.2.3 調(diào)整權重系數(shù)

算法中的更新目標權重操作用來對各目標權重系數(shù)進行調(diào)整,權重系數(shù)的調(diào)整如下

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

3.2.4 調(diào)整中間包利用率

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

3.2.5 攝動

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

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

步驟1生成初始解x0;

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

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

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

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

步驟6若未達到循環(huán)迭代次數(shù)最大值,則轉(zhuǎn)步驟7,否則轉(zhuǎn)步驟3;

步驟7根據(jù)x?生產(chǎn)初始解s0;

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

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

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

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

步驟12若達到循環(huán)迭代次數(shù)最大值,則轉(zhuǎn)步驟13,否則轉(zhuǎn)步驟9;

步驟13更新權重參數(shù),轉(zhuǎn)步驟9,否則轉(zhuǎn)步驟;

步驟14若達到循環(huán)迭代次數(shù)最大值,轉(zhuǎn)步驟15,否則轉(zhuǎn)步驟9;

步驟15更新中間包利用率參數(shù);

步驟16若未到循環(huán)迭代次數(shù)最大值,更新權重參數(shù),轉(zhuǎn)步驟17,否則轉(zhuǎn)步驟7;

步驟17若未達到循環(huán)迭代次數(shù)最大值,更新權重參數(shù),轉(zhuǎn)步驟1,否則轉(zhuǎn)步驟18;

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

步驟19輸出解s?.

4 算例驗證

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

表1 實例數(shù)據(jù)信息Table 1 Information of problem instances

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

表2 實驗結(jié)果Table 2 Experimental result

續(xù)表2Table 2 Continue

表3 中間包內(nèi)爐次差異結(jié)果對比Table 3 The results of comparing the differences between the charges in tundish

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

5 結(jié)束語

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

[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]龐新富,俞勝平,張志宇,等.煉鋼–連鑄生產(chǎn)優(yōu)化重調(diào)度方法[J].系統(tǒng)工程學報,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]俞勝平,柴天佑,鄭秉霖.煉鋼連鑄混合智能優(yōu)化調(diào)度方法及應用[J].系統(tǒng)工程學報,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]王秀英,柴天佑,鄭秉霖.煉鋼–連鑄調(diào)度模型參數(shù)優(yōu)化設定方法[J].系統(tǒng)工程學報,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模型的鋼包優(yōu)化調(diào)度方法[J].系統(tǒng)工程學報,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]馬天牧,羅小川,柴天佑.基考慮轉(zhuǎn)爐容量和寬度的爐次計劃混合優(yōu)化方法[J].系統(tǒng)工程學報,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]謝 海.基于改進的相對優(yōu)勢度的區(qū)間數(shù)排序[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重點基金研究發(fā)展計劃資助項目(2009CB320601);高校學科創(chuàng)新引智計劃資助項目(B08015).

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

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

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