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

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

(1.東北大學(xué)流程工業(yè)綜合自動(dòng)化國家重點(diǎn)實(shí)驗(yàn)室,遼寧沈陽110819; 2.東北大學(xué)自動(dòng)化研究中心,遼寧沈陽110819)

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

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

(1.東北大學(xué)流程工業(yè)綜合自動(dòng)化國家重點(diǎn)實(shí)驗(yàn)室,遼寧沈陽110819; 2.東北大學(xué)自動(dòng)化研究中心,遼寧沈陽110819)

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

中間包計(jì)劃;多目標(biāo);迭代局部搜索;變鄰域搜索;混合算法

1 引 言

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

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

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

2.1 問題描述

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

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

2.2 數(shù)學(xué)模型

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

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

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

引入如下決策變量

中間包計(jì)劃的數(shù)學(xué)模型為

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

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

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

3.1 模型分解

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

M1:

M2:

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

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

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

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

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

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

3.2.1 生成初始解

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

3.2.2 鄰域操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.5 攝動(dòng)

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

下面給出整個(gè)算法的步驟,其中步驟1～步驟6是第一層ILSVND混合算法,步驟7～步驟14是第二層ILSVND混合算法.對于新解接受標(biāo)準(zhǔn),本算法中采用接受較好解的方法,非支配排序負(fù)責(zé)對多個(gè)解進(jìn)行非支配排序.

步驟1生成初始解x0;

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

步驟3對x?進(jìn)行攝動(dòng)操作得到解x’;

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

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

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

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

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

步驟9對解s?進(jìn)行攝動(dòng)操作得到解s’;

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

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

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

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

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

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

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

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

步驟18對解進(jìn)行非支配排序;

步驟19輸出解s?.

4 算例驗(yàn)證

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

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

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

表2 實(shí)驗(yàn)結(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

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

5 結(jié)束語

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

[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)工程學(xué)報(bào),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)度方法及應(yīng)用[J].系統(tǒng)工程學(xué)報(bào),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)化設(shè)定方法[J].系統(tǒng)工程學(xué)報(bào),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)工程學(xué)報(bào),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)爐容量和寬度的爐次計(jì)劃混合優(yōu)化方法[J].系統(tǒng)工程學(xué)報(bào),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ìn)的相對優(yōu)勢度的區(qū)間數(shù)排序[J].科學(xué)技術(shù)與工程,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.

國家自然科學(xué)基金資助項(xiàng)目(71021061;60974091;61174187;61104174);國家973重點(diǎn)基金研究發(fā)展計(jì)劃資助項(xiàng)目(2009CB320601);高校學(xué)科創(chuàng)新引智計(jì)劃資助項(xiàng)目(B08015).

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

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

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