基于時(shí)間并行的重計(jì)劃編制方法

基于時(shí)間并行的重計(jì)劃編制方法

生產(chǎn)計(jì)劃是指根據(jù)盡可能滿足生產(chǎn)要求的條件，根據(jù)生產(chǎn)指示，組織生產(chǎn)任務(wù)，并配置相應(yīng)的資源（操作）。根據(jù)加工時(shí)間和加工順序，以獲得生產(chǎn)任務(wù)的執(zhí)行時(shí)間和成本優(yōu)化。生產(chǎn)調(diào)度實(shí)質(zhì)上是生產(chǎn)作業(yè)計(jì)劃(即調(diào)度方案)的執(zhí)行過程。煉鋼-連鑄生產(chǎn)對(duì)鋼水時(shí)間節(jié)奏的控制和溫度要求較高,但生產(chǎn)中存在的諸多不確定性因素將影響作業(yè)計(jì)劃的執(zhí)行,在調(diào)度過程中,必須通過重計(jì)劃編排來調(diào)整原調(diào)度方案。因此,重計(jì)劃的合理編制對(duì)實(shí)現(xiàn)煉鋼-連鑄生產(chǎn)連續(xù)、協(xié)調(diào)、穩(wěn)定運(yùn)行起著非常重要的作用。煉鋼-連鑄生產(chǎn)調(diào)度優(yōu)化問題已成為國內(nèi)外學(xué)者的研究熱點(diǎn),主要采用啟發(fā)式方法、遺傳算法以及蟻群優(yōu)化算法等進(jìn)行生產(chǎn)調(diào)度方案制定和優(yōu)化,國內(nèi)大多數(shù)鋼鐵企業(yè)已完成其硬件平臺(tái)建設(shè),針對(duì)特定鋼廠也建立了一些計(jì)劃與調(diào)度系統(tǒng)。然而,采用的技術(shù)手段和實(shí)現(xiàn)方式上仍存在不足,大多數(shù)的煉鋼-連鑄生產(chǎn)調(diào)度被考慮成靜態(tài)問題,難以體現(xiàn)生產(chǎn)中的隨機(jī)擾動(dòng)因素的影響。因此,相應(yīng)的計(jì)劃調(diào)度系統(tǒng)應(yīng)具有重計(jì)劃功能,當(dāng)環(huán)境和任務(wù)變化時(shí),可以采用適當(dāng)算法進(jìn)行重計(jì)劃編制。針對(duì)煉鋼-連鑄生產(chǎn)調(diào)度中存在的作業(yè)任務(wù)增減、設(shè)備故障、鋼水返送以及鋼種改判等常見生產(chǎn)擾動(dòng)因素,提出一種按擾動(dòng)時(shí)的作業(yè)計(jì)劃是否進(jìn)入流程開始執(zhí)行的分類,并相應(yīng)進(jìn)行重計(jì)劃制訂的方法,將爐次計(jì)劃劃分為作業(yè)爐次與未作業(yè)爐次,采用時(shí)間并行順推算法,以及基于遺傳算法與時(shí)間并行倒推的混合優(yōu)化算法分別對(duì)兩部分爐次計(jì)劃進(jìn)行重新編排和優(yōu)化,以得到煉鋼-連鑄生產(chǎn)調(diào)度在生產(chǎn)擾動(dòng)情況下的重計(jì)劃方案。最后,以某鋼廠的仿真實(shí)驗(yàn)來驗(yàn)證該方法的可行性和有效性。1連通性法的計(jì)算1.1初始調(diào)度方案失效期煉鋼生產(chǎn)是離散和連續(xù)相混合、設(shè)備復(fù)雜、非線性、多目標(biāo)、多約束、多資源相互協(xié)調(diào)的生產(chǎn)過程。生產(chǎn)過程的隨機(jī)擾動(dòng)因素多,可歸納為任務(wù)擾動(dòng)、設(shè)備擾動(dòng)、生產(chǎn)工藝擾動(dòng)和時(shí)間擾動(dòng)等4類,擾動(dòng)對(duì)生產(chǎn)的影響如表1所示。當(dāng)一個(gè)作業(yè)計(jì)劃調(diào)度方案生成后,調(diào)度員應(yīng)盡可能按初始調(diào)度方案進(jìn)行調(diào)度和組織生產(chǎn),但是,當(dāng)表1所示的隨機(jī)擾動(dòng)發(fā)生時(shí),煉鋼-連鑄初始調(diào)度方案失效,此時(shí)必須在初始調(diào)度方案的基礎(chǔ)上,根據(jù)擾動(dòng)時(shí)的生產(chǎn)實(shí)際狀況,在滿足生產(chǎn)約束和資源約束的前提下,對(duì)初始調(diào)度方案中沒有完成的煉鋼-連鑄生產(chǎn)爐次進(jìn)行計(jì)劃重排,更新初始調(diào)度后下發(fā)生產(chǎn)指令,確保生產(chǎn)持續(xù)進(jìn)行。因此,煉鋼-連鑄的重計(jì)劃編制問題可描述為:在已知原調(diào)度方案基礎(chǔ)上,根據(jù)實(shí)時(shí)調(diào)度信息、生產(chǎn)擾動(dòng)、當(dāng)前資源狀態(tài)以及生產(chǎn)約束,確定出原調(diào)度方案中沒有執(zhí)行的爐次在連鑄機(jī)上的開始和結(jié)束澆注時(shí)間,并為其在轉(zhuǎn)爐工序、精煉工序指派作業(yè)設(shè)備,且確定出在各設(shè)備上的起止作業(yè)時(shí)間,使?fàn)t次在工序間不出現(xiàn)等待或等待時(shí)間盡可能短,工位上爐次間無作業(yè)時(shí)間沖突,且設(shè)備利用率均衡。1.2不合格爐次生產(chǎn)時(shí)間和計(jì)劃時(shí)間仿真煉鋼-連鑄生產(chǎn)調(diào)度過程中,系統(tǒng)監(jiān)控分析原調(diào)度方案對(duì)應(yīng)的初始作業(yè)計(jì)劃、設(shè)備當(dāng)前運(yùn)行狀態(tài)、鋼種生產(chǎn)工藝準(zhǔn)則和生產(chǎn)的實(shí)時(shí)數(shù)據(jù),當(dāng)出現(xiàn)生產(chǎn)擾動(dòng)時(shí),進(jìn)行重計(jì)劃。重計(jì)劃編制的啟用條件為:1)增加或減少初始作業(yè)計(jì)劃中既定爐次或改變計(jì)劃任務(wù);2)設(shè)備故障停產(chǎn)維修、設(shè)備修復(fù)或新設(shè)備投入使用;3)冶煉鋼種質(zhì)量不合格時(shí)鋼種改判;鋼水溫度不合格時(shí)鋼水返送;4)爐次的實(shí)際生產(chǎn)時(shí)間與計(jì)劃時(shí)間之間的差值超出設(shè)定范圍。進(jìn)行重計(jì)劃編制時(shí),由于要保證計(jì)劃執(zhí)行過程的連續(xù)性,對(duì)已作業(yè)爐次應(yīng)優(yōu)先安排,確定其調(diào)度方案,然后再對(duì)未作業(yè)爐次進(jìn)行作業(yè)計(jì)劃重排。對(duì)進(jìn)入流程開始執(zhí)行的作業(yè)爐次,構(gòu)建一種時(shí)間并行順推算法進(jìn)行擾動(dòng)情況下的作業(yè)任務(wù)繼續(xù)執(zhí)行的調(diào)度方案的調(diào)整;而對(duì)未作業(yè)爐次計(jì)劃則采用基于遺傳算法與時(shí)間并行倒推算法的混合優(yōu)化算法進(jìn)行重計(jì)劃。整個(gè)煉鋼-連鑄重計(jì)劃編制方法的原理如圖1所示。煉鋼-連鑄重計(jì)劃編制方法中,基于遺傳算法的混合優(yōu)化算法可以表達(dá)作業(yè)計(jì)劃中的各爐次不同作業(yè)時(shí)間組合下的方案,并進(jìn)行方案的快速尋優(yōu),實(shí)現(xiàn)對(duì)未作業(yè)爐次計(jì)劃的重新編排,得到科學(xué)合理的可執(zhí)行生產(chǎn)作業(yè)計(jì)劃;筆者主要研究重計(jì)劃方法中的時(shí)間并行順推算法。2時(shí)間平行偏移方法2.1連澆工藝路徑下爐次均勻性的確定煉鋼-連鑄生產(chǎn)共有M道生產(chǎn)工序,其中第j道工序上有Q(j)個(gè)加工工位,設(shè)計(jì)時(shí)間并行順推算法對(duì)初始作業(yè)計(jì)劃中正在生產(chǎn)流程中作業(yè)的N個(gè)爐次進(jìn)行作業(yè)計(jì)劃重排,算法流程如下:步驟1擾動(dòng)識(shí)別與作業(yè)爐次分類,確定重計(jì)劃的作業(yè)爐次條件。1)讀取爐次實(shí)時(shí)調(diào)度信息、初始作業(yè)計(jì)劃、生產(chǎn)流程中底層工位對(duì)應(yīng)關(guān)系;2)判斷是否存在擾動(dòng),如果有,執(zhí)行步驟3),否則終止算法;3)根據(jù)實(shí)時(shí)調(diào)度信息和初始作業(yè)計(jì)劃,將作業(yè)爐次分為進(jìn)入流程的爐次計(jì)劃和未作業(yè)爐次計(jì)劃;4)令工序計(jì)數(shù)器j=1。步驟2讀取和保存進(jìn)入流程的爐次計(jì)劃中各爐次在各工序上的作業(yè)時(shí)間和工序間的運(yùn)輸時(shí)間的最小和最大值。1)讀取和保存進(jìn)入流程的爐次計(jì)劃中N個(gè)爐次到預(yù)編制任務(wù)集合Task中;2)由Task中各爐次加工工藝路徑,讀取各爐次在所經(jīng)過工序的作業(yè)時(shí)間和工序間的運(yùn)輸時(shí)間的最小值(tmini,jmini,j)和最大值(tmaxi,jmaxi,j),并分別保存在數(shù)組Twork(N×M×2)和Ttrans(N×M×2)中。步驟3將集合Task中爐次由“連澆原則”確定出在連鑄機(jī)上的開始和結(jié)束澆注時(shí)間,并倒推計(jì)算各爐次在擾動(dòng)出現(xiàn)后的各工序上的最早和最晚開始作業(yè)時(shí)間1)根據(jù)Task中各爐次與所在澆次內(nèi)的前一爐次連澆的原則,計(jì)算其在鑄機(jī)上的開始和結(jié)束澆注時(shí)間;2)以各爐次的開始澆注時(shí)間為起點(diǎn),選取爐次在工序間的平均運(yùn)輸時(shí)間并從Twork(N×M×2)中選擇作業(yè)時(shí)間的最小值和最大值,分別倒推計(jì)算出在各工序的最晚和最早開始加工時(shí)間xLi,jLi,j及xEi,jEi,j;步驟4將Task中工序j上作業(yè)的爐次加入當(dāng)前作業(yè)任務(wù)集合Γ中。步驟5計(jì)算Γ中各爐次到緊后工序j′上的開始和結(jié)束作業(yè)時(shí)間,由底層工位對(duì)應(yīng)關(guān)系確定各爐次的可選加工工位,并存儲(chǔ)到工序j′的預(yù)分配任務(wù)集合中。1)初始化爐次計(jì)數(shù)器i,令i=1;2)若Γ不為空,則繼續(xù)執(zhí)行以下步驟,否則,執(zhí)行步驟6;3)取Γ中爐次i,計(jì)算其在工藝路徑上工序j的緊后工序j′上的開始作業(yè)時(shí)間xi,j,由tmini,j+xi,j-xLi,jxLi,j-xEi,j(tmaxi,j-tmini,j)tmini,j+xi,j?xLi,jxLi,j?xEi,j(tmaxi,j?tmini,j)計(jì)算爐次在工位上的作業(yè)時(shí)間,并確定爐次結(jié)束作業(yè)時(shí)間;4)依據(jù)流程中底層工位對(duì)應(yīng)關(guān)系,由爐次i當(dāng)前作業(yè)工位的緊后工位匹配爐次的工藝路徑,確定其在緊后工序j′的可選工位集Ψi,j',并保存到工序j′的預(yù)分配爐次集合中;5)從Γ中刪除爐次i,令i=i+1,轉(zhuǎn)2)。步驟6將工序(j+1)上的所有爐次按預(yù)定規(guī)則分配到可選工位集Ψi,j+1中的適宜工位上加工。步驟7判斷工序(j+1)是否是工藝路徑的末道工序。若j+1<M,則令j=j+1,轉(zhuǎn)到步驟4,否則,轉(zhuǎn)下一步。步驟8檢測(cè)在連鑄機(jī)上是否實(shí)現(xiàn)連澆,若實(shí)現(xiàn)連澆,則轉(zhuǎn)到步驟10,否則轉(zhuǎn)到下一步。步驟9以“連澆”原則調(diào)整各爐次在相應(yīng)連鑄機(jī)上的開始和結(jié)束澆注時(shí)間。步驟10輸出編制的已進(jìn)入流程開始作業(yè)的爐次作業(yè)計(jì)劃方案。時(shí)間并行順推算法能根據(jù)當(dāng)前的實(shí)時(shí)生產(chǎn)調(diào)度信息中的擾動(dòng)情況,對(duì)已進(jìn)入流程開始作業(yè)的爐次快速進(jìn)行煉鋼-連鑄重計(jì)劃編制,以保證作業(yè)計(jì)劃能繼續(xù)被執(zhí)行。2.2爐次選擇加工爐次在時(shí)間并行順推算法中,如何考慮工位上主設(shè)備資源約束進(jìn)行設(shè)備分配是確保制定的重計(jì)劃方案合理性的關(guān)鍵。為反映現(xiàn)實(shí)生產(chǎn)中“先到先加工”和設(shè)備負(fù)荷均衡原則,以及緊湊生產(chǎn)的要求,在重計(jì)劃編制算法中,依次啟用以下規(guī)則將工序上的所有爐次分配到合適的工位上加工。1)先到先加工規(guī)則R1為減少爐次作業(yè)前等待時(shí)間,一般按先到達(dá)爐次先安排生產(chǎn)的原則來組織生產(chǎn)。重計(jì)劃算法中,規(guī)則R1體現(xiàn)在:同一工序上各爐次按開始作業(yè)時(shí)間從早到晚從工序上選擇加工工位,即R1={x1,j≤x2,j≤x3,j?≤xi,j}?i≤Ν,j≤Μ。(1)R1={x1,j≤x2,j≤x3,j?≤xi,j}?i≤N,j≤M。(1)2)設(shè)備沖突時(shí)間最小規(guī)則R2當(dāng)同一爐次i在工序j上的可選工位集Ψi,j中有多個(gè)可選工位時(shí),通過統(tǒng)計(jì)爐次在工位上的開始時(shí)間xi,j,k與各工位的最早可用時(shí)間Ti,j,k的沖突時(shí)間,選擇沖突最小的工位,即:R2=min{max{(Τi,j,k-xi,j,k),0}}?i≤Ν,j≤Μ,k≤Q(j)。(2)R2=min{max{(Ti,j,k?xi,j,k),0}}?i≤N,j≤M,k≤Q(j)。(2)3)設(shè)備利用率均衡規(guī)則R3當(dāng)按設(shè)備沖突時(shí)間最小規(guī)則確定出爐次i的可選作業(yè)工位有多個(gè)時(shí),通過計(jì)算此刻各工位上已經(jīng)分配的加工爐次數(shù)目qj,k(xi,j),選擇爐次數(shù)最小的工位來加工爐次,即R3=min{qj,k(xi,j)}?i≤Ν,j≤Μ,k≤Q(j))。(3)R3=min{qj,k(xi,j)}?i≤N,j≤M,k≤Q(j))。(3)4)隨機(jī)選擇規(guī)則R4當(dāng)按規(guī)則R3確定出爐次i的可選擇作業(yè)工位集Pi,j中有多個(gè)工位時(shí),從其中隨機(jī)選擇一個(gè)工位作來加工爐次i,即:R4=Rand(Ρi,j)?i≤Ν,j≤Μ。(4)R4=Rand(Pi,j)?i≤N,j≤M。(4)3初始作業(yè)計(jì)劃執(zhí)行情況按某鋼廠的生產(chǎn)條件,以某天8h如表2所示的生產(chǎn)批量計(jì)劃(8個(gè)澆次、54爐次)對(duì)應(yīng)的初始作業(yè)計(jì)劃為基礎(chǔ),在進(jìn)行煉鋼-連鑄生產(chǎn)調(diào)度過程中,通過設(shè)置設(shè)備故障等生產(chǎn)擾動(dòng),按提出的方法進(jìn)行重計(jì)劃編制。實(shí)驗(yàn)數(shù)據(jù)均來自于實(shí)際生產(chǎn),圖2為煉鋼-連鑄生產(chǎn)工藝流程及相關(guān)設(shè)備數(shù)目。圖3為煉鋼-連鑄生產(chǎn)調(diào)度過程中執(zhí)行的初始作業(yè)計(jì)劃,當(dāng)其執(zhí)行到1:15時(shí),6#轉(zhuǎn)爐出現(xiàn)故障,從1∶15到8∶00需進(jìn)行維修。系統(tǒng)在1:15接收到此生產(chǎn)擾動(dòng)后,立即啟動(dòng)重計(jì)劃編制模型,對(duì)正在作業(yè)爐次(如表3所示)和未作業(yè)爐次采用相應(yīng)的算法進(jìn)行作業(yè)計(jì)劃的重新編排,得到如圖4所示的重計(jì)劃方案。對(duì)比圖3、4可看出:1)編制的重計(jì)劃仍然保證了初始作業(yè)計(jì)劃方案中連鑄工序的連續(xù)澆注,同時(shí)也無作業(yè)時(shí)間沖突,爐次作業(yè)安排比較緊湊且設(shè)備負(fù)荷均衡;2)6#轉(zhuǎn)爐故障,打亂了正常情況下生產(chǎn)系統(tǒng)中1#、2#、3#轉(zhuǎn)爐出鋼的鋼水只供給1#和2#連鑄機(jī)澆注的規(guī)律,它們需冶煉供3#和4#連鑄機(jī)澆注的鋼水。實(shí)驗(yàn)結(jié)果表明,重計(jì)劃編制方法能很好地處理煉鋼-連鑄實(shí)際生產(chǎn)中常見的隨機(jī)擾動(dòng)事件,并能根據(jù)擾動(dòng)和實(shí)時(shí)調(diào)度信息進(jìn)行作業(yè)計(jì)劃的重新編制,算法是可行且有效的。4基于混合算法的爐次計(jì)劃重新編排1)根據(jù)煉鋼-連鑄生產(chǎn)調(diào)度及重計(jì)劃特點(diǎn),將重計(jì)劃編