煉鋼-連鑄作業(yè)計(jì)劃可執(zhí)行性的研究

煉鋼-連鑄作業(yè)計(jì)劃可執(zhí)行性的研究

根據(jù)i-有一個(gè)爐序列，還有n個(gè)爐序列。j——工序編號(hào),共M道生產(chǎn)工序;k——工序j上工位的編號(hào),共Q(j)個(gè)工位;i′——工序j工位k上緊鄰爐次i的后一爐次;j′——爐次i加工工藝路徑上工序j的緊前工序;Ω——全部爐次集合,Ω={i|i∈[1,N]};Θ——最長(zhǎng)工序編號(hào)集合,Θ={j|j∈[1,M]};Θi——爐次i的加工工藝路徑,由加工經(jīng)過(guò)的工序編號(hào)組成,Θi?Θ;Πj——工序j上加工工位的集合,由Q(j)個(gè)工位的編號(hào)組成,Πj={k|k∈[1,Q(j)]};xi,j,k——爐次i在工序j工位k的開(kāi)始作業(yè)時(shí)間;ti,j,k——爐次i在工序j工位k上的作業(yè)時(shí)間;d(j,j′)——爐次在工序j與j′之間的運(yùn)輸時(shí)間;μi,j,k——爐次i在工序j工位k上作業(yè)前的允許等待時(shí)間;Tj,k——工序j工位k第一爐次的開(kāi)始作業(yè)時(shí)間;T′j,k——初始時(shí)刻工序j工位k的最早可用時(shí)間;Taver——用戶設(shè)定的允許最大平均物流時(shí)間;σi,j,k——工序j工位k上爐次i與緊鄰的后一爐次i′作業(yè)間的間隙時(shí)間;煉鋼生產(chǎn)系統(tǒng)是一個(gè)多維、非線性、動(dòng)態(tài)開(kāi)放的復(fù)雜系統(tǒng),其生產(chǎn)作業(yè)計(jì)劃的編制和優(yōu)化是一個(gè)大規(guī)模的組合優(yōu)化問(wèn)題,是NP完全問(wèn)題。煉鋼-連鑄生產(chǎn)是鋼鐵生產(chǎn)的關(guān)鍵工序,因此制訂科學(xué)合理的煉鋼-連鑄生產(chǎn)作業(yè)計(jì)劃顯得尤為重要。近年來(lái),該問(wèn)題得到廣泛研究,已取得明顯進(jìn)展。Masayuki等建立專家系統(tǒng)來(lái)編制煉鋼連鑄作業(yè)計(jì)劃,能減少鋼水作業(yè)前等待時(shí)間并提高計(jì)劃編制效率;Tang等建立煉鋼連鑄生產(chǎn)調(diào)度整數(shù)規(guī)劃模型并采用拉格朗日松弛法求解,能及時(shí)得到高質(zhì)量的作業(yè)計(jì)劃;張彩霞等采用啟發(fā)式搜索方法編制冶鑄軋一體化生產(chǎn)作業(yè)計(jì)劃,再用離散事件仿真方法對(duì)其進(jìn)行評(píng)價(jià),以輔助生產(chǎn)調(diào)度,為解決一體化生產(chǎn)計(jì)劃調(diào)度問(wèn)題提供了一條途徑;崔建雙等建立鋼鐵生產(chǎn)混合流水車(chē)間調(diào)度模型,利用工序和工件混合編碼的改良遺傳算法編制作業(yè)計(jì)劃,提高了作業(yè)排序的精度和效率。但大多數(shù)的煉鋼-連鑄作業(yè)計(jì)劃編制常被考慮成靜態(tài)問(wèn)題,難以體現(xiàn)生產(chǎn)中加工和運(yùn)輸作業(yè)時(shí)間不確定性等因素的影響,難以保證作業(yè)計(jì)劃有較高的可執(zhí)行性,只能作為生產(chǎn)的參考。因此,建立能表征生產(chǎn)作業(yè)時(shí)間不確定性,并能根據(jù)多變的動(dòng)態(tài)生產(chǎn)環(huán)境進(jìn)行作業(yè)計(jì)劃編制、調(diào)整和重計(jì)劃的模型是亟待解決的問(wèn)題。通過(guò)對(duì)煉鋼-連鑄生產(chǎn)過(guò)程特點(diǎn)和動(dòng)態(tài)生產(chǎn)環(huán)境的分析和問(wèn)題抽象,來(lái)建立煉鋼-連鑄作業(yè)計(jì)劃優(yōu)化模型。模型以減少爐次間的作業(yè)沖突時(shí)間和盡可能提前安排各連鑄機(jī)的開(kāi)澆時(shí)間為目標(biāo),以滿足連鑄機(jī)的連澆和工藝要求為約束條件,同時(shí)構(gòu)造了一種以鑄機(jī)開(kāi)澆時(shí)間和爐次在工序上的作業(yè)和運(yùn)輸時(shí)間進(jìn)行分段編碼的改良遺傳算法,并結(jié)合沿生產(chǎn)流程時(shí)間并行倒推算法進(jìn)行模型求解。最后,以某鋼廠的煉鋼-連鑄作業(yè)計(jì)劃制定實(shí)例來(lái)驗(yàn)證模型和算法的有效性。1連通性-精煉的生產(chǎn)計(jì)劃優(yōu)化模型1.1連鑄作業(yè)計(jì)劃編制煉鋼-連鑄生產(chǎn)過(guò)程具有離散和連續(xù)生產(chǎn)相結(jié)合、設(shè)備復(fù)雜、同時(shí)存在多種工藝約束等特征,而且生產(chǎn)環(huán)境具有多變性,主要表現(xiàn)在:①生產(chǎn)工藝路徑變化,如鋼廠生產(chǎn)工藝變革,增加或減少生產(chǎn)設(shè)備等;②不同鋼種的加工工藝路徑動(dòng)態(tài)選擇;③爐次加工和運(yùn)輸時(shí)間的不確定性。生產(chǎn)計(jì)劃的編制方式一般是先將合同按鋼種合并成爐次,再按連鑄品種規(guī)格要求等將爐次組成澆次,生成生產(chǎn)批量計(jì)劃;然后再將批量計(jì)劃安排到適宜的轉(zhuǎn)爐和連鑄機(jī)等設(shè)備上生產(chǎn),即進(jìn)行生產(chǎn)作業(yè)計(jì)劃編制。煉鋼-連鑄作業(yè)計(jì)劃編制問(wèn)題可歸結(jié)為多任務(wù)、多工序、多機(jī)器的混合車(chē)間作業(yè)排序問(wèn)題。煉鋼-連鑄作業(yè)計(jì)劃優(yōu)化模型,通常以作業(yè)偏離(指連鑄機(jī)斷澆、作業(yè)前等待、板坯提前或拖期交貨)預(yù)定生產(chǎn)目標(biāo)而產(chǎn)生的懲罰費(fèi)用為目標(biāo)函數(shù)。這種方法難以確定能否實(shí)現(xiàn)連澆這一關(guān)鍵目標(biāo);此外,模型求解時(shí)未考慮爐次加工和運(yùn)輸時(shí)間的不確定性,導(dǎo)致計(jì)劃較大偏離生產(chǎn)實(shí)際。因此,煉鋼-連鑄作業(yè)計(jì)劃編制問(wèn)題可描述為:在已知澆次計(jì)劃的基礎(chǔ)上,安排N個(gè)爐次到M道工序中的若干工位上加工,尋找作業(yè)計(jì)劃的優(yōu)化方案,即在保證連鑄機(jī)連澆和滿足生產(chǎn)工藝要求的約束條件下,合理確定出每臺(tái)連鑄機(jī)的開(kāi)始澆注時(shí)刻以及各爐次在各工序上的開(kāi)始和結(jié)束作業(yè)時(shí)間,并選擇適宜的加工工位,使?fàn)t次在工序間不出現(xiàn)等待或等待時(shí)間盡可能短,工位上爐次間無(wú)作業(yè)時(shí)間沖突,設(shè)備利用率均衡。1.2開(kāi)澆時(shí)間及約束煉鋼-連鑄作業(yè)計(jì)劃優(yōu)化模型是以最小化爐次間的作業(yè)沖突時(shí)間和盡可能早的安排鑄機(jī)開(kāi)澆時(shí)間為目標(biāo)函數(shù),以滿足連鑄機(jī)的連澆生產(chǎn)等工藝要求為約束條件來(lái)建立的。該目標(biāo)函數(shù)還被作為遺傳優(yōu)化算法的評(píng)價(jià)函數(shù),來(lái)優(yōu)化鑄機(jī)的開(kāi)澆時(shí)間和各爐次在工序上的作業(yè)和運(yùn)輸時(shí)間。作業(yè)計(jì)劃優(yōu)化模型的基本假設(shè)為:(1)生產(chǎn)批量計(jì)劃(澆次計(jì)劃和爐次計(jì)劃)已知;(2)澆次中各爐次在鑄機(jī)上的作業(yè)順序不變;(3)爐次在工序上的加工時(shí)間和工序間的運(yùn)輸時(shí)間的分布特征已知;(4)各工位的最早可用時(shí)刻已知。如果各連鑄機(jī)的開(kāi)澆時(shí)刻設(shè)置不合理,在保證連鑄機(jī)連澆而倒推得到的作業(yè)計(jì)劃中,同一工位上相鄰爐次間可能存在作業(yè)沖突。工序j工位k上爐次i與其緊鄰的后一爐次i′的作業(yè)沖突時(shí)間(以分鐘為計(jì)算單位)為:所有工位上爐次間總的沖突時(shí)間可表示為:各連鑄機(jī)必須在其最早可選開(kāi)澆時(shí)刻(完成已下達(dá)生產(chǎn)任務(wù)的結(jié)束時(shí)刻)與最晚可選開(kāi)澆時(shí)刻(此時(shí)刻開(kāi)澆恰好能按時(shí)完成預(yù)定生產(chǎn)任務(wù))間開(kāi)澆,為提高連鑄機(jī)的生產(chǎn)效率,應(yīng)盡可能縮短連鑄機(jī)的預(yù)定開(kāi)澆時(shí)刻與最早可選開(kāi)澆時(shí)刻間的差距。最大可提前開(kāi)澆的時(shí)間為:所建立的煉鋼-連鑄作業(yè)計(jì)劃優(yōu)化數(shù)學(xué)模型為:約束條件如下:目標(biāo)函數(shù)(3)表示工位上作業(yè)沖突時(shí)間和連鑄機(jī)最大可提前開(kāi)澆時(shí)間的加權(quán)和最小化,加權(quán)系數(shù)表示兩個(gè)目標(biāo)重要性,通常α1>α2,且相差一個(gè)數(shù)量級(jí)為宜;約束(4)為連鑄機(jī)連澆約束,是首先要滿足的約束條件;約束(5)表示爐次在每道工序最多被分配到其中一個(gè)工位上加工;約束(6)保證爐次加工前的等待時(shí)間在最大允許等待時(shí)間范圍內(nèi);約束(7)表示同一工位上,前一爐次處理結(jié)束后才能處理下一爐次;約束(8)表示爐次的平均物流時(shí)間在最大允許范圍內(nèi);約束(9)表示爐次在工位上的開(kāi)始作業(yè)時(shí)間晚于計(jì)劃編制時(shí)刻各工位的最早可用時(shí)間。2遺傳算法優(yōu)化目標(biāo)函數(shù)遺傳算法(GA)具有編碼和遺傳操作簡(jiǎn)單,優(yōu)化不受限制性條件的約束,隱含并行性和全局搜索能力等特點(diǎn),在作業(yè)計(jì)劃與調(diào)度優(yōu)化方面有廣泛應(yīng)用。為求解模型,建立由遺傳算法與沿生產(chǎn)流程時(shí)間并行倒推算法相結(jié)合的混合優(yōu)化算法。先由遺傳算法生成由各連鑄機(jī)的預(yù)定開(kāi)始澆注時(shí)刻,爐次在工序上的作業(yè)時(shí)間和工序間的運(yùn)輸時(shí)間等信息構(gòu)成的染色體,并按各鑄機(jī)的澆次生成澆次內(nèi)各爐次在鑄機(jī)上的開(kāi)始與結(jié)束作業(yè)時(shí)間,再采用時(shí)間并行倒推算法確定澆次中所有爐次在各工序上的開(kāi)始和結(jié)束作業(yè)時(shí)間,并選擇適宜的加工工位,形成完整的作業(yè)時(shí)刻表,然后通過(guò)遺傳算法的適應(yīng)度函數(shù)計(jì)算可對(duì)當(dāng)代中所有作業(yè)計(jì)劃方案進(jìn)行評(píng)價(jià)和篩選,得到優(yōu)化方案;再經(jīng)遺傳操作和不斷進(jìn)化,可最終得到滿足設(shè)定優(yōu)化效果的模型優(yōu)化解,即優(yōu)化的可執(zhí)行的煉鋼-連鑄作業(yè)計(jì)劃。此優(yōu)化模型和求解方法能滿足適應(yīng)動(dòng)態(tài)生產(chǎn)環(huán)境變化的需要。(1)面向?qū)ο蠼M態(tài)方式搭建的生產(chǎn)過(guò)程對(duì)象模型,從建模方法層面保證了模型適應(yīng)生產(chǎn)過(guò)程對(duì)象和工藝路徑變化的要求;(2)沿流程時(shí)間并行倒推算法的動(dòng)態(tài)工位選擇規(guī)則等從算法機(jī)制上可滿足生產(chǎn)中工藝路徑和設(shè)備動(dòng)態(tài)選擇的需要;(3)具有分布特征的加工時(shí)間和運(yùn)輸時(shí)間描述方法和遺傳優(yōu)化算法能體現(xiàn)加工和運(yùn)輸時(shí)間的不確定性。因此,所制定的生產(chǎn)作業(yè)計(jì)劃能更真實(shí)地反應(yīng)生產(chǎn)實(shí)際情況。本文著重描述遺傳算法對(duì)鑄機(jī)的開(kāi)澆時(shí)間、爐次在各工序上的作業(yè)時(shí)間和工序間運(yùn)輸時(shí)間的優(yōu)化,沿生產(chǎn)流程時(shí)間并行倒推算法另文描述。2.1u2004保持連鑄機(jī)正常開(kāi)澆時(shí)間和運(yùn)輸時(shí)間的數(shù)據(jù)根據(jù)染色體的編碼結(jié)構(gòu),編碼方法有一維編碼和多維編碼。本文構(gòu)建一種類似多維編碼的分段實(shí)數(shù)編碼方法來(lái)編碼染色體。染色體由各臺(tái)連鑄機(jī)的開(kāi)始澆注時(shí)間、爐次在各工序的作業(yè)時(shí)間和工序間的運(yùn)輸時(shí)間三部分組成,其數(shù)據(jù)結(jié)構(gòu)定義為:Chromosome(CastT(1×G)AsIntegerWorkT(N×M)AsIntegerTransT(N×M)AsInteger)其中,數(shù)組CastT()保存G臺(tái)連鑄機(jī)的預(yù)定開(kāi)澆時(shí)間;WorkT()和TransT()分別保存所有爐次在各工序上的作業(yè)時(shí)間和工序間的運(yùn)輸時(shí)間。根據(jù)各爐次在各工序的作業(yè)時(shí)間及工序間的運(yùn)輸時(shí)間的分布規(guī)律產(chǎn)生一定數(shù)目(假設(shè)為H個(gè))的加工時(shí)間和運(yùn)輸時(shí)間,分別保存在對(duì)應(yīng)的2維數(shù)組Ai(H×M)和Bi(H×M)中(i表示爐次號(hào)),其中WorkT(i,j)對(duì)應(yīng)的數(shù)值m表示爐次i在工序j上的作業(yè)時(shí)間位于數(shù)組Ai(H×M)的第m行第j列。2.2astt、transt基因段的形成每臺(tái)連鑄機(jī)在其最早和最晚可選開(kāi)澆時(shí)刻之間隨機(jī)產(chǎn)生1個(gè)開(kāi)澆時(shí)間,G個(gè)開(kāi)澆時(shí)間組成1條染色體中CastT()的基因段;再分別從按分布規(guī)律生成并保存各爐次在各工序的作業(yè)時(shí)間及工序間運(yùn)輸時(shí)間的數(shù)組Ai(H×M)和Bi(H×M)中選擇相應(yīng)的行序號(hào)組成WorkT()和TransT()基因段。合并3個(gè)基因段,形成1條完整的染色體。重復(fù)上述操作,直到個(gè)體數(shù)達(dá)到設(shè)定規(guī)模,完成種群初始化。2.3算法的收斂速度及算法適應(yīng)度函數(shù)是遺傳算法進(jìn)化搜索的依據(jù),直接影響算法的收斂速度以及能否找到最優(yōu)解。本文選取式(10)為適應(yīng)度函數(shù),其中Cmax是一個(gè)足夠大的正數(shù),z是模型中的目標(biāo)函數(shù)。2.4選擇、交叉和變異2.4.1輪盤(pán)球選擇行為采用精英選擇和輪盤(pán)賭相結(jié)合的混合選擇策略。先將父代個(gè)體按適應(yīng)值從大到小排序,適應(yīng)值最大的個(gè)體直接復(fù)制到子代中,其余個(gè)體由輪盤(pán)賭選擇策略從父種群中選擇,經(jīng)交叉、變異和基因修復(fù)后生成。2.4.2基因中間重組及交叉根據(jù)染色體分段編碼的特點(diǎn)對(duì)交叉操作進(jìn)行了特殊設(shè)計(jì)。構(gòu)造了一種基因分區(qū)交叉操作方法,對(duì)染色體的CastT()、WorkT()和TransT()分別進(jìn)行分區(qū)交叉。連鑄機(jī)的預(yù)定開(kāi)澆時(shí)間(CastT()),采用基因中間重組操作,計(jì)算式如下:α3、α4分別為[-0.25,1.25]間的隨機(jī)數(shù)。完成基因中間重組后,驗(yàn)證鑄機(jī)開(kāi)澆時(shí)間,如果其不在最早與最晚可選開(kāi)澆時(shí)刻間,采用染色體修復(fù)策略將其修復(fù)到此范圍內(nèi)。WorkT()和TransT()采用部分映射交叉。以澆次為操作單位,在爐次數(shù)大于2的澆次內(nèi)隨機(jī)選擇2個(gè)交叉位置,進(jìn)行部分映射交叉(圖1所示),而對(duì)于爐次數(shù)小于等于2的澆次,則互換2個(gè)體基因。以澆次為操作單位,對(duì)同一工序上的相同澆次內(nèi)爐次進(jìn)行部分映射交叉,保證了新基因的合法性,避免了繁瑣的基因修復(fù)操作,可大幅度提高遺傳算法的運(yùn)行效率。2.4.3變異傳統(tǒng)型基因連鑄機(jī)的開(kāi)澆時(shí)間采用擾動(dòng)式變異,即在原個(gè)體基因值的基礎(chǔ)上,加減一個(gè)擾動(dòng)變量,得到變異后的基因值。而爐次i在工序j的作業(yè)時(shí)間變異時(shí),在[1,H]間隨機(jī)產(chǎn)生一個(gè)整數(shù)l即為變異后的基因值,表示變異后的作業(yè)時(shí)間為數(shù)組Ai(H×M)中第l行第j列對(duì)應(yīng)的時(shí)間。2.5算法的實(shí)現(xiàn)模型求解優(yōu)化算法的求解流程如圖2所示。3開(kāi)澆優(yōu)化算法仿真以某鋼廠煉鋼車(chē)間轉(zhuǎn)爐至連鑄的生產(chǎn)工藝流程(圖3所示)及生產(chǎn)實(shí)績(jī)數(shù)據(jù)為應(yīng)用背景,對(duì)建立的模型和算法進(jìn)行測(cè)試。以某天8h的澆次計(jì)劃(7澆次,37爐次)、鋼種工藝路徑(不同鋼種的工藝路徑不同)、鋼種在工序上作業(yè)時(shí)間和工序間運(yùn)輸時(shí)間的分布規(guī)律等為輸入條件,算法中設(shè)置種群規(guī)模為30,交叉概率為0.9,變異概率為0.1,在CPU為賽揚(yáng)1.7G,內(nèi)存為256M的臺(tái)式機(jī)上進(jìn)行多次實(shí)驗(yàn),遺傳算法均能在進(jìn)化30代內(nèi)(60s內(nèi))收斂到優(yōu)化解,混合優(yōu)化算法均在90s內(nèi)得到優(yōu)化的生產(chǎn)作業(yè)計(jì)劃。圖4、圖5分別為優(yōu)化算法和實(shí)際生產(chǎn)得到的作業(yè)計(jì)劃甘特圖。鋼水出爐到開(kāi)始澆注過(guò)程中各爐次的作業(yè)時(shí)間比較如圖6所示。綜合圖4、5可以看出,優(yōu)化算法得到的各連鑄機(jī)的開(kāi)澆時(shí)刻合理,在實(shí)現(xiàn)完全連續(xù)澆注情況下,各爐次在工位上無(wú)作業(yè)時(shí)間沖突,設(shè)備利用率均衡;圖6顯示,由于現(xiàn)有系統(tǒng)沒(méi)有優(yōu)化作業(yè)計(jì)劃,導(dǎo)致生產(chǎn)中出鋼至開(kāi)始澆注過(guò)程的作業(yè)時(shí)間波動(dòng)較大,而優(yōu)化算法得到不經(jīng)過(guò)RH精煉的爐次的作業(yè)時(shí)間約為80min,經(jīng)過(guò)RH精煉的約為105min,且波動(dòng)幅度較小,這有利于組織生產(chǎn)。實(shí)例結(jié)果表明,模型和算法是有效的。4遺傳算法求解動(dòng)態(tài)生產(chǎn)環(huán)境變化的優(yōu)勢(shì)(1)在考慮連鑄機(jī)的連澆約束、煉鋼-連鑄生產(chǎn)工藝要求和作業(yè)時(shí)間不確定性的條件下,建立了以最小化工位作業(yè)沖突時(shí)間和盡可能早的安排連鑄機(jī)開(kāi)澆時(shí)間為目標(biāo)的煉鋼-連鑄生產(chǎn)作業(yè)計(jì)劃優(yōu)化模型。(2)根據(jù)煉鋼-連鑄生產(chǎn)作業(yè)計(jì)劃特點(diǎn),以及生產(chǎn)過(guò)程中存在的時(shí)間不確定性問(wèn)題,構(gòu)造了一種分段實(shí)