面向煉鋼–連鑄調(diào)度過程的兩階段優(yōu)化模型與算法

王秀英 馮惠 任志考 周艷平

面向煉鋼–連鑄調(diào)度過程的兩階段優(yōu)化模型與算法

王秀英1馮惠1任志考1周艷平1

以某鋼廠多臺轉(zhuǎn)爐及多臺精煉爐對多臺連鑄機的復(fù)雜生產(chǎn)線為研究對象,針對其調(diào)度過程涉及多設(shè)備、多目標(biāo)、多約束等調(diào)度要素,且離散和連續(xù)變量混雜,采用常規(guī)建模方法難以滿足現(xiàn)場對調(diào)度的精度及排產(chǎn)速度的需求問題,提出一種新型的兩階段優(yōu)化建模方法.首先,證明了爐次從煉鋼到連鑄總等待時間最小的調(diào)度目標(biāo)與該爐次在轉(zhuǎn)爐開始作業(yè)時間最大是等價的事實,并以離散型的設(shè)備變量為決策變量,以轉(zhuǎn)爐開始作業(yè)時間最大為動態(tài)規(guī)劃最優(yōu)指標(biāo),建立設(shè)備指派多階段動態(tài)規(guī)劃基本方程和設(shè)備指派優(yōu)化模型;然后,以爐次在設(shè)備開始作業(yè)時間的連續(xù)型變量為決策變量,并將準(zhǔn)時開澆的非線性調(diào)度指標(biāo)轉(zhuǎn)化成與之等價的線性優(yōu)化目標(biāo),以在同一臺連鑄機上澆鑄的爐次之間斷澆的時間間隔最小、鋼包在設(shè)備之間的冗余等待時間最小、提前與滯后理想開澆時間的時間間隔最小為目標(biāo),建立線性規(guī)劃沖突解消模型.工業(yè)實驗表明所提出兩階段優(yōu)化建模方法在求解速度與求解精度均滿足現(xiàn)場要求.

煉鋼–連鑄,生產(chǎn)調(diào)度,優(yōu)化建模策略,設(shè)備指派模型,沖突解消模型

現(xiàn)代制造企業(yè)規(guī)模龐大、過程復(fù)雜等特征給制造過程的調(diào)度決策帶來了極大的挑戰(zhàn)[1].鋼鐵企業(yè)是最大的制造業(yè)之一,與其他制造業(yè)所不同的是鋼鐵企業(yè)生產(chǎn)過程是在高溫、高能耗下進行的,工序之間的物流要求銜接緊密,在各工序的設(shè)備上要準(zhǔn)時加工,以此來減少鋼水的溫降,降低能耗.這決定了鋼鐵行業(yè)比其他制造業(yè)的調(diào)度精度要求更高,調(diào)度速度要求快,調(diào)度難度會更大.

計算機技術(shù)的飛速發(fā)展給鋼鐵企業(yè)生產(chǎn)管理水平的提升帶來了新的機遇.國內(nèi)外大型鋼鐵企業(yè)于20世紀(jì)90年初將計算機技術(shù)與人工調(diào)度經(jīng)驗相結(jié)合建立調(diào)度管理系統(tǒng)[2?4],以此來提高調(diào)度的精度和生產(chǎn)效率.但所建立的調(diào)度系統(tǒng)是否好用、實用,關(guān)鍵看嵌入調(diào)度系統(tǒng)中的調(diào)度模型和方法是否符合鋼廠工況實際.由于各個鋼廠生產(chǎn)的產(chǎn)品不同,設(shè)備條件和工藝條件等也不完全相同,所建立的模型和采用方法也不同.所以,針對每個鋼廠的具體生產(chǎn)設(shè)備條件及工藝過程,建立合理的調(diào)度模型及尋找有效的調(diào)度方法和優(yōu)化技術(shù)是提高鋼鐵企業(yè)生產(chǎn)效率、降低生產(chǎn)成本的重要途徑[5].

國外大部分鋼廠都是針對自己鋼廠生產(chǎn)設(shè)備條件和工藝特點建立了單目標(biāo)或多目標(biāo)調(diào)度模型[4,6].文獻[6]以一個澆次總完成時間最小、每個爐次在工序之間的等待時間及作業(yè)完成時間總和最小為目標(biāo)建立了混合規(guī)劃模型,通過求解得到每個澆次的調(diào)度時間表.然后,在同一臺連鑄機上,按照澆次與澆次之間的時間間隔為60分鐘對各澆次進行排序,從而得到所有澆次疊加后的生產(chǎn)調(diào)度表.由于文獻[6]所述的所有澆次都在一臺連鑄機上澆鑄且非連鑄設(shè)備的作業(yè)時間均小于連鑄作業(yè)時間,每個澆次又有60分鐘的時間間隔,所以,在每個設(shè)備上無需考慮爐次間的設(shè)備沖突問題.生產(chǎn)工藝路徑相對簡單,所提出的模型難以應(yīng)用到多臺連鑄機、多臺轉(zhuǎn)爐和精煉爐、多重精煉的復(fù)雜生產(chǎn)工藝情況.

近幾年國內(nèi)外學(xué)者們也開始對多臺轉(zhuǎn)爐、精煉爐對多臺連鑄機,多重精煉方式的調(diào)度問題進行了研究,并取得了一些成果[7?16].這些成果多數(shù)是先建立分段模型或混合整數(shù)規(guī)劃模型,再采用經(jīng)典優(yōu)化方法(拉格朗日[7]、差分方法[8])、啟發(fā)式方法[9?11]或智能優(yōu)化方法(遺傳算法[12]、蟻群[13?14]、果蠅[15]、蜂群[16]等)對模型進行求解,得到相應(yīng)的調(diào)度結(jié)果.經(jīng)典優(yōu)化方法通常在求解精度上能達到現(xiàn)場滿意的效果,但當(dāng)規(guī)模超過45個爐次時,求解的速度難以滿足現(xiàn)場要求.啟發(fā)式方法能滿足求解速度要求,但不能保證解的最優(yōu)性.智能優(yōu)化方法初始種群都是隨機生成的,參數(shù)設(shè)置多數(shù)憑經(jīng)驗給出,沒有理論依據(jù),導(dǎo)致調(diào)度解的魯棒性較差.所以,研究符合現(xiàn)場實際,在時間和解的精度上均能滿足現(xiàn)場要求的實用調(diào)度方法具有重要的現(xiàn)實意義.

文獻[17]通過對國內(nèi)某大型鋼廠多臺轉(zhuǎn)爐、多臺精煉爐對多臺連鑄機的復(fù)雜生產(chǎn)過程的分析,建立了既含有設(shè)備變量(離散型變量)又含有時間變量(連續(xù)型變量),而且時間變量依賴于設(shè)備變量混合整數(shù)規(guī)劃模型,分析了模型難以求解的原因.本文在文獻[17]的基礎(chǔ)上,提出了新的兩階段優(yōu)化建模策略,解決了模型難以求解的問題,并在求解速度及求解精度上均滿足現(xiàn)場的要求.

1 煉鋼–連鑄生產(chǎn)過程描述[18]

圖1是某大型鋼廠煉鋼–連鑄生產(chǎn)過程所使用的設(shè)備和生產(chǎn)工藝過程.首先,將高爐中的鐵水注入鐵水包且送到煉鋼廠,并倒入轉(zhuǎn)爐設(shè)備中進行吹煉,吹煉的過程是把高溫條件下的鐵水進一步冶煉為含碳量更低的鋼水.然后,將轉(zhuǎn)爐中的鋼水倒入準(zhǔn)備好的鋼包中,由指定的臺車和行車將裝有鋼水的鋼包送到相應(yīng)的精煉設(shè)備上進行精煉.精煉是將轉(zhuǎn)爐冶煉的普通鋼水繼續(xù)進行脫碳、去硫和去除雜質(zhì)等處理,使普通鋼水變成優(yōu)質(zhì)鋼水,以確保連鑄機澆鑄出合格的板坯.根據(jù)鋼種的不同,有的鋼水包需要經(jīng)過一重精煉、兩重精煉或三重精煉處理過程.所謂一重精煉是指鋼水包只經(jīng)過一次精煉處理,即只走一個精煉設(shè)備(例如:1#鋼包走3#RH一個精煉設(shè)備);二重精煉是指鋼水包需要經(jīng)過兩次精煉處理,即需要走兩個精煉設(shè)備(例如:2#鋼包走2#RH和KIP兩個精煉設(shè)備);同理,三重精煉是鋼水包需要經(jīng)過三個精煉設(shè)備處理(3#鋼包走1#RH、2#CAS和LF三個精煉設(shè)備).精煉處理結(jié)束后,再由指定的臺車和行車將鋼水包吊運到指定的連鑄機前,并倒入對應(yīng)的中間包中.中間包的鋼水不斷進入結(jié)晶器中,通過結(jié)晶振動冷卻后,從連鑄機拉出板坯.板坯經(jīng)軋機(直軋/冷軋)軋成各種鋼材產(chǎn)品以供銷售.這是一個多臺轉(zhuǎn)爐、多臺精煉爐對多臺連鑄機,具有不同精煉重數(shù)的煉鋼–連鑄生產(chǎn)工藝過程.

圖1 煉鋼–連鑄生產(chǎn)工藝過程Fig.1 Production process of steelmaking-continuous casing

2 調(diào)度計劃的兩階段優(yōu)化建模策略

該大型鋼廠煉鋼–連鑄生產(chǎn)調(diào)度計劃的含義是以澆次計劃為基礎(chǔ),在爐次的生產(chǎn)工藝路徑,爐次在轉(zhuǎn)爐、精煉爐上的加工時間、運輸時間及各澆次開澆時間已知的條件下,確定各澆次中的爐次在哪臺轉(zhuǎn)爐、哪臺精煉爐上加工,并確定出各爐次在轉(zhuǎn)爐、精煉爐及連鑄機上加工的開始時間和結(jié)束時間,形成煉鋼–連鑄生產(chǎn)作業(yè)時間表(稱為調(diào)度計劃),并確保澆次內(nèi)的爐次連續(xù)澆鑄,爐次在連鑄前等待時間不能超過規(guī)定的時間,同一個設(shè)備兩個相鄰爐次不能產(chǎn)生作業(yè)沖突等目標(biāo)[18].

2.1 變量及符號說明

i澆次序號,i=1,2,3,···,N;

Ni第i個澆次中的爐次數(shù);

j爐次序號,j=1,2,···,Ni;

Lij第i個澆次的第j個爐次;

?ij爐次Lij從轉(zhuǎn)爐到連鑄工序的加工設(shè)備總數(shù);澆次計劃中的精煉方式確定后, ?ij的取值就確定了;

θ爐次Lij從轉(zhuǎn)爐到連鑄加工的順序號, θ=1,2,···,?ij;

g表示設(shè)備類,g=1,2,3,···,G,如g=1表示轉(zhuǎn)爐設(shè)備;g=2表示第一類精煉設(shè)備類,g=G表示連鑄設(shè)備類;

Ti澆次i的理想開澆時間,由現(xiàn)場給定;

Mg表示第g類設(shè)備中含有的并行機數(shù);

kg設(shè)備變量,表示g類設(shè)備的第k個設(shè)備序號;kg=1,2,3,···,Mg;

Tij(kg(θ)) 爐次Lij的第θ個操作在第g類設(shè)備的第kg(θ)個設(shè)備上的加工時間;當(dāng)θ不同時,爐次Lij的操作設(shè)備類型g也不同,所以,g是θ的函數(shù),即g=g(θ), kg=kg(θ);對于連鑄設(shè)備,不同爐次在連鑄機的處理時間是不盡相同的.所以,處理時間Tij(kg(θ))是設(shè)備變量kg(θ)的函數(shù);

Tij(kg(θ), 爐次Lij從第θ個操作設(shè)備kg(θ)到第

kg(θ+1)) θ+1個操作設(shè)備kg(θ+1)之間的運輸時間.由于爐次Lij的第θ和θ+1個操作設(shè)備不同,其運輸時間也不盡相同,所以運輸時間Tij(kg(θ),kg(θ+1))是爐次上下操作設(shè)備的函數(shù);

yij(kg(θ)) 設(shè)備變量kg(θ)的函數(shù),當(dāng)yij(kg(θ))=1,表示爐次Lij的第θ個操作在g類設(shè)備上的第kg(θ)個設(shè)備上加工;否則, yij(kg(θ))=0;

xij(kg(θ)) 稱為時間變量.爐次Lij的第θ個操作在第g類設(shè)備的第kg(θ)個機器上加工的開始時間.

1)性能指標(biāo)

a)澆次準(zhǔn)時開澆,即澆次中的第一個爐次偏離理想開澆時間盡可能小.

b)澆次內(nèi)的爐次連鑄澆鑄,即同一個連鑄機上相鄰爐次斷澆的時間最小.

c)爐次在不同設(shè)備之間的冗余等待時間盡可能的小.

2)約束條件

a)爐次操作順序的約束,即爐次必須按其生產(chǎn)工藝路徑進行加工.

b)同一設(shè)備不同爐次不能出現(xiàn)作業(yè)沖突約束.

c)爐次在連鑄前最大等待時間不能超過企業(yè)規(guī)定的范圍.

d)爐次在同類設(shè)備處理的唯一性約束.

e)按照現(xiàn)場給定的開澆時間準(zhǔn)時開澆.

2.2 兩階段優(yōu)化建模

2.2.1 基于動態(tài)規(guī)劃的設(shè)備指派建模

1)設(shè)備指派建模分析

一個爐次從轉(zhuǎn)爐煉鋼到形成鑄坯需要經(jīng)過煉鋼工序、多重精煉工序和連鑄工序的生產(chǎn)過程.由于每道工序都可能存在并行機的問題,根據(jù)已知條件,除連鑄階段外,需要在具有并行機的工序上為爐次選取一個具體的加工設(shè)備.這是一個多階段決策問題,動態(tài)規(guī)劃是解決多階段決策的最好方法.所以,本文基于動態(tài)規(guī)劃方法建立設(shè)備指派模型.

使用動態(tài)規(guī)劃方法的關(guān)鍵是根據(jù)實際問題建立多階段決策的基本方程,為每個階段做出決策.由于與爐次設(shè)備變量相關(guān)的調(diào)度性能指標(biāo)為爐次從煉鋼到連鑄之間整個冗余時間最小.為建立動態(tài)規(guī)劃的基本方程,需要將上述調(diào)度性能指標(biāo)進行轉(zhuǎn)化.

令wij表示任意一爐次Lij在其所有操作之間冗余時間之和,其最小值記為min wij.爐次在轉(zhuǎn)爐開始加工時間最大,記為max{xij(k1)|k1=1,2, 3}.對于任意一個澆次中的任意一個爐次Lij,假設(shè)它從轉(zhuǎn)爐到連鑄工序所經(jīng)過的設(shè)備數(shù)為?ij,則Lij相鄰兩個操作θ與θ+1(θ=1,2,3,···,?ij?1)設(shè)備間冗余時間為

任意一個爐次Lij在其所有操作設(shè)備間冗余等待時間之和為

由于在連鑄工位上有θ=?ij,g(?ij)=6;而在轉(zhuǎn)爐工位上有θ=1,g(θ)=g(1)=1,則上式為

即一個爐次從煉鋼到連鑄總等待時間最小與該爐次在轉(zhuǎn)爐開始作業(yè)時間最大是等價的.

2)設(shè)備指派動態(tài)規(guī)劃的基本方程

令爐次在轉(zhuǎn)爐的開始作業(yè)時間為xij(k1).根據(jù)爐次的生產(chǎn)工藝方式可知任意一個爐次的操作順序θ=1,2,3,···,?ij,依據(jù)動態(tài)規(guī)劃各階段狀態(tài)轉(zhuǎn)移方程可得:

從第一操作到第二操作狀態(tài)轉(zhuǎn)移方程為

即

從第二操作到第三操作狀態(tài)轉(zhuǎn)移方程為

由此可得到從第θ個操作到第θ+1個操作狀態(tài)轉(zhuǎn)移方程為

由于為爐次Lij指派設(shè)備時還需要考慮它在同設(shè)備上與已安排爐次Li'j'可能沖突的時間段,記為f(xij(kg(θ)),xi'j'(kg(θ'))).于是,從第θ個操作到第θ+1個操作狀態(tài)轉(zhuǎn)移方程應(yīng)定義為

其中

以各爐次Lij在連鑄機上的開澆時間xij(k6)作為基本方程的初始條件,而xij(k6)是理想開澆時間Ti和爐次的澆鑄時間Tij(k6)之和,于是有任意個爐次Lij從轉(zhuǎn)爐到連鑄各階段(各操作)基本方程為

3)基于動態(tài)規(guī)劃的設(shè)備指派模型

根據(jù)上面的分析,現(xiàn)以設(shè)備變量kg(θ)為決策變量,以爐次在轉(zhuǎn)爐開始作業(yè)時間最大max{xij(k1)|k1=1,2,3}為最優(yōu)指標(biāo)函數(shù),記為Fij(k1,k2,···,k?ij).以爐次在同類設(shè)備處理的唯一性為約束建立如下設(shè)備指派優(yōu)化模型.

a)優(yōu)化目標(biāo):

式中,xij(k1)可由狀態(tài)轉(zhuǎn)移方程(9)從連鑄工序遞推得到.

b)約束條件:

式中

2.2.2 沖突解消模型

設(shè)備指派模型的功能是依據(jù)爐次Lij的加工順序θ=1,2,3,···,?ij和動態(tài)規(guī)劃基本方程(9)為爐次Lij確定出具體加工設(shè)備,記為但由于設(shè)備指派模型僅考慮了爐次Lij在所加工的設(shè)備之間的冗余等待時間最小的性能指標(biāo)和選取設(shè)備唯一性約束,沒有考慮調(diào)度的其他性能指標(biāo)和約束,導(dǎo)致不同爐次在同一個設(shè)備上可能出現(xiàn)作業(yè)時間沖突現(xiàn)象.

沖突解消模型的功能是在Lij已確定了加工設(shè)備的基礎(chǔ)上,重新確定爐次在其所加工設(shè)備上的開始作業(yè)時間和結(jié)束作業(yè)時間,以滿足調(diào)度的各項指標(biāo)和約束.

1)決策變量的選取

2)性能指標(biāo)和約束條件

從文獻[17]所建立模型的過程看,性能指標(biāo)“澆次準(zhǔn)時開澆”是一個非線性(含有絕對值)的目標(biāo)函數(shù).為提高求解速度,首先將非線性目標(biāo)轉(zhuǎn)換成兩個線性目標(biāo),并給出兩個變量的定義:

定義1.提前理想開澆時間的偏差量為

定義2.滯后理想開澆時間的偏差量為

結(jié)論1.準(zhǔn)時開澆的目標(biāo)函數(shù)等價于提前與滯后理想開澆時間偏差量之和.

證明.由于

注1.結(jié)論1說明準(zhǔn)時開澆的性能指標(biāo)等價于澆次提前于理想開澆時間與滯后于理想開澆時間兩個指標(biāo)之和.在實際生產(chǎn)中這兩個指標(biāo)的重要程度是不一樣的[19],因此,將準(zhǔn)時開澆看成兩個指標(biāo)更符合實際.

3)基于線性規(guī)劃的沖突解消模型

通過上述分析可知,建立沖突解消模型需要考慮如下4種性能指標(biāo):

a)澆次提前于理想開澆時間最小;

b)澆次滯后于理想開澆時間最小;

c)澆次內(nèi)的爐次要連續(xù)澆鑄;

d)澆次內(nèi)各爐次在各操作設(shè)備上的冗余等待時間盡量小.

假設(shè)上述同類指標(biāo)賦予相同的權(quán)重,則采用加權(quán)方法將多目標(biāo)轉(zhuǎn)化成單目標(biāo)線性規(guī)劃模型為

式(16)表示澆次內(nèi)的爐次連續(xù)澆鑄,爐次在設(shè)備間的冗余等待時間盡可能的小,提前于理想開澆時間和滯后理想開澆時間的時間間隔盡可能小的4個指標(biāo)加權(quán)之和.其中,C1為連鑄斷澆懲罰系數(shù); C2為爐次等待時間的懲罰系數(shù);C3為前于理想開澆時刻的懲罰系數(shù);C4為遲于理想開澆時刻的懲罰系數(shù).式(17)對于同一爐次必須在前一個設(shè)備加工完成后方可在下一個設(shè)備上加工.式(18)同一設(shè)備上相鄰兩個爐次只有在前一爐次加工結(jié)束后方可進行下一爐次的加工.式(19)表示爐次在連鑄前最大等待時間不能超過給定的閾值.式(20)表示準(zhǔn)時開澆約束;式(21)表示決策變量非負(fù)性約束.

3 兩階段優(yōu)化模型的求解步驟

3.1 第一階段求解設(shè)備指派模型

1)求出各爐次在連鑄機的澆鑄時間(分鐘),采用如下公式計算:

a)當(dāng)該爐次為澆次的第一個爐,澆鑄時間為

式中,Wt1為第一爐鋼水的總重量(噸);TH1為澆鑄鋼水輸出板坯的平均厚度(毫米);為澆鑄鋼水輸出板坯的平均左、右寬度(毫米);Ls為連鑄機的標(biāo)準(zhǔn)拉速(米/分鐘).

b)當(dāng)該爐次不是澆次第一個爐,澆鑄時間為

式中,Wti為第i爐鋼水的總重量(噸);THi為澆鑄第i爐鋼水輸出板坯的平均厚度(毫米);為澆鑄第i爐鋼水輸出板坯的平均左、右寬度(毫米);為澆鑄第(i?1)爐鋼水輸出板坯的平均左、右寬度(毫米);Ls為連鑄機的標(biāo)準(zhǔn)拉速(米/分鐘).

2)按照動態(tài)規(guī)劃模型為每個爐次指派加工的設(shè)備:

a)計算每個爐次在連鑄上的開澆時間xij(k6);

b)利用基本方程即式(9)遞推每個爐次在每個階段的開始作業(yè)時間xij(kg(θ));

c)利用最優(yōu)指標(biāo)函數(shù)即式(10)求出爐次Lij的最優(yōu)指標(biāo)函數(shù)值Fij(k1,k2,···,?ij);

e)對每個爐次重復(fù)步驟c)～e),直到所有的爐次全部安排完為止.

3.2 第二階段求解沖突解消模型

1)利用已開發(fā)的求解線性規(guī)劃軟件包(稱為LP)對沖突解消模型進行求解,但在使用前需要做一個程序轉(zhuǎn)換接口,即將設(shè)備指派模型的結(jié)果轉(zhuǎn)化成第二個階段用LP程序求解的輸入條件,然后調(diào)用LP即可.也可以用Lingo等軟件進行求解.

2)將求出的解(x1,x2,···,xn)轉(zhuǎn)化成對應(yīng)設(shè)備的作業(yè)開始時間,在利用設(shè)備處理時間,就可以得到在該設(shè)備上的結(jié)束時間,從而形成調(diào)度時刻表.

4 工業(yè)實驗

4.1 實驗數(shù)據(jù)

表1是3個澆次10個爐次計劃的現(xiàn)場實際數(shù)據(jù).其中開澆時間分別為:第一個澆次7:17;第二澆次7:10;第三個澆次7:25,其他信息見表1.

表1 三個澆次10個爐次計劃的初始數(shù)據(jù)Table 1 Initial data of three cast including ten charges

4.2 實驗結(jié)果

表2是采用本文所建立的動態(tài)規(guī)劃模型為表1中的10個爐次確定出的具體加工設(shè)備,對應(yīng)的處理時間和運輸時間由現(xiàn)場給出,見表2.

表2 基于動態(tài)規(guī)劃的設(shè)備指派結(jié)果Table 2 Equipment assignment base on dynamic programming

表3 基于動態(tài)規(guī)劃的10個爐次粗調(diào)度時刻表Table 3 Ten charges rough schedule base on dynamic programming

由動態(tài)規(guī)劃模型計算出10個爐次在各設(shè)備上的作業(yè)時間見表3.由于表3不易看出哪個爐次在那個設(shè)備上與哪個爐次有沖突,所以將表3用甘特圖表示,見圖2.從圖2可以清楚地看出,第三個澆次中的爐次9與爐次10在1#LD設(shè)備上存在設(shè)備沖突,在3#RH也存在沖突.利用第二階段建立的沖突解消模型求解后,得到無沖突的作業(yè)時間表和對應(yīng)的甘特圖分別見表4和圖3.其中沖突解消模型中的懲罰系數(shù)由文獻[19]的方法確定,懲罰系數(shù)分別為:C1=20,C2=10,C3=30,C4=15.

圖2 基于動態(tài)規(guī)劃10個爐次的粗調(diào)度甘特圖Fig.2 Gantt chart of ten charges rough scheduling based on dynamic programming

表4 10個爐次機器沖突解消后的調(diào)度表Table 4 Ten charges schedule table after conflicts eliminated

5 結(jié)論

本文研究了面向國內(nèi)某大型鋼廠煉鋼–連鑄生產(chǎn)調(diào)度過程的兩階段優(yōu)化建模及求解策略.首先,根據(jù)該廠的設(shè)備條件和調(diào)度需求定義了符合調(diào)度過程的符號、調(diào)度目標(biāo)和工藝約束條件,并給出了建模及求解的詳細(xì)過程.解決了對于具有并行機的多設(shè)備、工藝復(fù)雜,采用常規(guī)建模及求解方法難以滿足現(xiàn)場對調(diào)度快速響應(yīng)及求解精度的問題.本文提出的兩階段優(yōu)化建模方法不僅在解的精度及速度能滿足現(xiàn)場的需要,而且當(dāng)用戶想采用一種新的算法求設(shè)備指派模型時,無需對整個調(diào)度算法的程序進行修改,只需用新的設(shè)備指派程序替換舊的設(shè)備指派程序即可.從而減少程序開發(fā)人員的重復(fù)勞動,易于增加調(diào)度問題求解算法的多樣性和靈活性.

圖3 10個爐次沖突解消后的調(diào)度甘特圖Fig.3 Scheduling Gantt chart after ten charges machine conflicts eliminated

1 Wu Qi-Di,Qiao Fei,Li Li,Wu Ying.Data-based scheduling for complex manufacturing processes.Acta Automatica Sinica,2009,35(6):807?813 (吳啟迪,喬非,李莉,吳瑩.基于數(shù)據(jù)的復(fù)雜制造過程調(diào)度.自動化學(xué)報,2009,35(6):807?813)

2 Wang Xiu-Ying,Chai Tian-You,Zheng Bing-Lin.Intelligent scheduling software&its application in steelmaking and continuous casting.Computer Integrated Manufacturing Systems,2006,12(8):1220?1226 (王秀英,柴天佑,鄭秉霖.煉鋼–連鑄智能調(diào)度軟件的開發(fā)及應(yīng)用.計算機集成制造系統(tǒng),2006,12(8):1220?1226)

3 Missbauer H,Hauber W,Stadler W.A scheduling system for the steelmaking-continuous casting process.A case study from the steel-making industry.International Journal of Production Research,2009,47(15):4147?4172

4 PacciarelliD,PranzoM.Production schedulingin a steelmaking-continuouscasting plant.Computersand Chemical Engineering,2004,28(12):2823?2835

5 Huang Min,Fu Ya-Ping,Wang Hong-Feng,Zhu Bing-Hu, Wang Xing-Wei.Job-shop scheduling model and algorithm with machine deterioration.Acta Automatica Sinica,2015, 41(3):551?558 (黃敏,付亞平,王洪峰,朱兵虎,王興偉.設(shè)備帶有惡化特性的作業(yè)車間調(diào)度模型與算法.自動化學(xué)報,2015,41(3):551?558)

6 Bellabdaoui A,Teghem J.A mixed-integer linear programming model for the continuous casting planning.International Journal of Production Economics,2006,104(2): 260?270

7 Mao K,Pan Q K,Pang X F,Chai T Y.A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process.European Journal of Operational Research,2014,236(1):51?60

8 Tang L X,Zhao Y,Liu J Y.An improved differential evolution algorithm for practical dynamic scheduling in steelmaking-continuous casting production.IEEE Transactions on Evolutionary Computation,2014,18(2):209?225

9 Sbihi A,Bellabdaoui A,Teghem J.Solving a mixed integer linear program with times setup for the steel-continuous casting planning and scheduling problem.International Journal of Production Research,2014,52(24):7276?7296

10 Yu Sheng-Ping,Chai Tian-You.Rescheduling method for starting time delay in steelmaking and continuous casting production processes.Acta Automatica Sinica,2016,42(3): 358?374 (俞勝平,柴天佑.開工時間延遲下的煉鋼–連鑄生產(chǎn)重調(diào)度方法.自動化學(xué)報,2016,42(3):358?374)

11 Tan Y Y,Liu S X.Models and optimisation approaches for scheduling steelmaking-refining-continuous casting production under variable electricity price.International Journal of Production Research,2014,52(4):1032?1049

12 Li Tie-Ke,Su Zhi-Xiong.Two-stage genetic algorithm for SM-CC production scheduling.Chinese Journal of Management Science,2009,17(5):68?74 (李鐵克,蘇志雄.煉鋼連鑄生產(chǎn)調(diào)度問題的兩階段遺傳算法.中國管理科學(xué),2009,17(5):68?74)

13 Atighehchian A,Bijari M,Tarkesh H.A novel hybrid algorithm for scheduling steel-making continuous casting production.Computers&Operations Research,2009,36(8): 2450?2461

14 Pan L,Yu S P,Zheng B L,Chai T Y.Cast batch planning for steelmaking and continuous casting based on ant colony algorithm.In:Proceedings of the 2010 International Symposium on Computational Intelligence and Design.Hangzhou, China:IEEE,2010.244?247

15 Li J Q,Pan Q K,Mao K,Suganthan P N.Solving the steelmaking casting problem using an effective fruit fly optimisation algorithm.Knowledge-Based Systems,2014,72: 28?36

16 Pan Q K.An effective co-evolutionary artificial bee colony algorithm for steelmaking-continuous casting scheduling. European Journal of Operational Research,2016,250(3): 702?714

17 Wang X Y,Jiang X J,Wang H H.Optimal modeling and analysis of steelmaking and continuous casting production scheduling.In:Proceedings of the 11th World Congress on Intelligent Control and Automation.Shenyang,China: IEEE,2014.5057?5062

18 Wang Xiu-Ying.Hybrid Optimization Scheduling Method of Steelmaking and Continuous Casting and its Application [Ph.D.dissertation],Northeastern University,China,2012 (王秀英.煉鋼–連鑄混合優(yōu)化調(diào)度方法及應(yīng)用[博士學(xué)位論文],東北大學(xué),中國,2012)

19 Wang Xiu-Ying,Chai Tian-You,Zheng Bing-Lin.Parameter optimization setting of steel making and continuous casting scheduling model.Journal of Systems Science and Systems Engineering,2011,26(4):531?537 (王秀英,柴天佑,鄭秉霖.煉鋼–連鑄調(diào)度模型參數(shù)優(yōu)化設(shè)定方法.系統(tǒng)工程學(xué)報,2011,26(4):531?537

王秀英 青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院教授.2012年獲得東北大學(xué)博士學(xué)位.主要研究方向為生產(chǎn)計劃與調(diào)度理論和方法,智能優(yōu)化算法.本文通信作者.

E-mail:bywxy@126.com

(WANGXiu-Ying Professor at the School of Information Science and Technology,Qingdao University of Science and Technology.She received her Ph.D.degree from Northeastern University in 2012.Her research interest covers theory and method of production planning and scheduling,and intelligent optimization algorithms.Corresponding author of this paper.)

馮 惠 青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院碩士研究生.主要研究方向為智能優(yōu)化算法,生產(chǎn)計劃與生產(chǎn)調(diào)度.

E-mail:huifeng0411@163.com

(FENG HuiMaster student at the School of Information Science and Engineering,Qingdao University of Science and Technology.Her research interest covers intelligent optimization algorithm,production planning and scheduling.)

任志考 青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院副教授.主要研究方向為智能優(yōu)化算法,無線網(wǎng)絡(luò)技術(shù),機器人通信,云服務(wù)技術(shù).E-mail:rzk_888@163.com

(REN Zhi-Kao Associated professor at the School of Information Science and Technology,Qingdao University of Science and Technology.His research interest covers intelligent optimization algorithms,wireless network technology, robot communication and cloud-service technology.)

周艷平 青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院副教授.分別于2003年和2013年在青島科技大學(xué)和華東理工大學(xué)獲得碩士和博士學(xué)位.主要研究方向為智能優(yōu)化算法,生產(chǎn)計劃與生產(chǎn)調(diào)度.

E-mail:zypweb@163.com

(ZHOU Yan-Ping Associated professor at the School of Information Science and Technology,Qingdao University of Science and Technology.He received his master degree from Qingdao University of Science and Technology in 2003,and Ph.D.degree from East China University of Science and Technology in 2013.His research interest covers intelligent optimization algorithm, production planning and scheduling.)

Two-stage Optimal Modeling and Algorithm of Production Scheduling for Steelmaking and Continuous Casting

WANG Xiu-Ying1FENG Hui1REN Zhi-Kao1ZHOU Yan-Ping1

Steelmaking and continuous casting production scheduling is a multi-equipment assignment,multi-objective, multi-constraint,discrete and continuous variables hybrid optimization problem.Traditional modeling and solving methods are usually adopted to solve it,but they cannot meet the requirement in terms of high scheduling accuracy and fast problem solving speed.A new two-stage optimal modeling algorithm is proposed in this paper.In stage one,we show that minimizing the waiting time from steelmaking to continuous casting is equivalent to maximizing the converter operating time at first.Then we built a multiple-stage dynamic programming equation and optimization model using discrete variables,with the goal of maximizing the converter operating time.In stage two,we establish a linear programming conflict elimination model using continuous variables by converting a non-linear performance index into two equavalent linear optimization indexes including lead time,lag time between pratical casting and planned casting,and combining the other two indexes including time gap between furnaces on same caster and waiting duration for steel ladle among converters,refining furnaces and casters.On-site industry application validates that the proposed method can solve the scheduling problem with high speed and accuracy.

Steelmaking and continuous casting,production scheduling,optimal modeling strategy,equipment assignment model,conflict solving model

王秀英,馮惠,任志考,周艷平.面向煉鋼–連鑄調(diào)度過程的兩階段優(yōu)化模型與算法.自動化學(xué)報,2016,42(11): 1702?1710

Wang Xiu-Ying,Feng Hui,Ren Zhi-Kao,Zhou Yan-Ping.Two-stage optimal modeling and algorithm of production scheduling for steelmaking and continuous casting.Acta Automatica Sinica,2016,42(11):1702?1710

2016-01-06 錄用日期2016-06-22

Manuscript received January 6,2016;accepted June 22,2016

國家自然科學(xué)基金 (61104004), 山東省自然科學(xué)基金(ZR2014FL019),山東省高等學(xué)校科技計劃項目(J14LN31)資助

Supported by National Natural Science Foundation of China (61104004),Natural Science Foundation of Shandong Province (ZR2014FL019),Higher Educational Science and Technology Program of Shandong Province(J14LN31)

本文責(zé)任編委趙千川

Recommended by Associate Editor ZHAO Qian-Chuan

1.青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院青島266000

1.College of Information Science and Technology,Qingdao University of Science and Technology,Qingdao 266000

DOI 10.16383/j.aas.2016.c160005