面向脈沖需求的應(yīng)急資源調(diào)度方法

面向脈沖需求的應(yīng)急資源調(diào)度方法

眾所周知，時間緊張是應(yīng)急管理的一個最顯著特征。決策者應(yīng)在最短的時間內(nèi)完成應(yīng)急救援計劃的制定和資源計劃的決策。應(yīng)急活動總是伴隨著資源的消耗。根據(jù)agu等人的研究，通過脈沖播種方法，任何接收器都可以控制傳染病的傳播。確保每個脈沖的需要在感染前能夠滿足脈沖的需要，應(yīng)急活動不受應(yīng)急資源供應(yīng)不足的影響。為了應(yīng)對傳染病的疾病，通常很難通過一次性資源計劃來控制傳染病的傳播。因此，有效控制傳染病傳播一直是學(xué)術(shù)界研究的重點。Shulgin等通過分析SIR模型,也得出同樣的結(jié)論.文獻(xiàn)在研究傳染病擴(kuò)散問題時,都認(rèn)為應(yīng)用脈沖接種方法來控制傳染病的擴(kuò)散比采用一次性接種方法更有效,更有實際意義.Marc等應(yīng)用動態(tài)系統(tǒng)理論研究了具有脈沖接種的傳染病問題,研究表明脈沖接種可以使傳染病擴(kuò)散有效收斂.Meng等研究了一類新的具有潛伏期延遲和非線性擴(kuò)散的SEIRS脈沖接種模型,并給出了已有的應(yīng)急資源調(diào)度滿足這種脈沖需求的充要條件.Gao等分析了具有延遲脈沖接種的SIR模型,提出脈沖接種比例小于某臨界值時無法有效地控制疾病擴(kuò)散.Gakkhar等研究了具有非常規(guī)擴(kuò)散比率的SIRS脈沖接種模型,給出了脈沖接種全局穩(wěn)定的條件和超臨界分叉的閾值.因此,在傳染病災(zāi)害發(fā)生后,只要通過合理的資源調(diào)度,使得到達(dá)的應(yīng)急資源量在每次脈沖需求來臨前滿足需求即可有效地控制傳染病擴(kuò)散.目前,國內(nèi)學(xué)者有關(guān)應(yīng)急物流的研究更多地集中在一次性資源調(diào)度和基于連續(xù)消耗的資源調(diào)度方面,Tzeng等研究了具有脈沖特性的應(yīng)急資源調(diào)度問題,構(gòu)建了一個多目標(biāo)規(guī)劃模型,并將應(yīng)急脈沖需求的滿意度納入了應(yīng)急調(diào)度模型.Sheu針對關(guān)鍵救援期中響應(yīng)緊急物資需求的應(yīng)急物流協(xié)同調(diào)度問題,提出了一種混合模糊聚簇優(yōu)化方法.何健敏等針對應(yīng)急系統(tǒng)多點出救問題的特點,引入了連續(xù)可行方案的概念,并提出了以最早應(yīng)急開始時間為目標(biāo)的數(shù)學(xué)模型及相應(yīng)的求解算法,得出了一些具有啟發(fā)性的結(jié)論.本文在此基礎(chǔ)上,充分考慮生物恐怖襲擊或傳染病爆發(fā)等特殊應(yīng)急救援情況下,一次性的資源調(diào)度很難完全滿足實際的各種應(yīng)急需求,而基于連續(xù)消耗的資源調(diào)度又過于繁雜且成本太高的實際情況,提出面向脈沖需求的應(yīng)急資源調(diào)度問題.本文首先建立了具有脈沖需求的應(yīng)急資源調(diào)度模型,給出了相關(guān)理論研究分析.在滿足應(yīng)急資源脈沖需求的基礎(chǔ)上,著重考慮在資源調(diào)度研究過程中應(yīng)急時間最早、出救點數(shù)最少的情況并給出求解算法,同時從理論上進(jìn)行歸納證明.最后,應(yīng)用一個簡單的算例驗證模型的有效性.1tn把應(yīng)急資源量tn限定到資源應(yīng)急能力tn設(shè)已知應(yīng)急資源需求點為A,應(yīng)急資源需求的脈沖周期為T,每個脈沖周期的需求量為P1,P2,…,Pl,其中脈沖周期數(shù)為l,設(shè)A1,A2,…,An表示n個應(yīng)急資源供應(yīng)點(可行出救點),Ai的資源可用量為xi(xi>0),且n∑i=1xi>l∑j=1Ρj,從Ai將應(yīng)急資源送到A所需時間為ti(ti>0),不防設(shè)t1≤t2≤…≤tn,則任意方案φ可以表示為φ={(Ai1,x′i1,ti1),(Ai2,x′i2,ti2),…,(Aim,x′im,tim)}(1)式中,0<x′ik≤xik表示該點所供給的應(yīng)急資源量不超過其資源可用量;i1,i2,…,im(m≤n)為1,2,…,n的一個子排列,則存在C1n+C2n+…+Cnn=2n-1種可能.如果對?q<l,則稱在保證∑m∈{k|tik<qΤ}x′im>q∑j=1Ρj的情況下資源調(diào)度問題稱為脈沖消耗應(yīng)急問題.設(shè)N(φ)表示方案φ的出救點數(shù),Tmin(φ)表示最早應(yīng)急調(diào)度開始時間,Tmax(φ)表示最遲應(yīng)急調(diào)度開始時間,T(φ)=Tmax(φ)-Tmin(φ)為方案的應(yīng)急活動時間,其中Tmin(φ)=min{ti1,ti2,…,tim},Tmax(φ)=max{ti1,ti2,…,tim},即脈沖消耗首先要保證在每個脈沖來臨之前有足夠的資源可供消耗.2最早應(yīng)急調(diào)度方案定義1若調(diào)度方案φ={(Ai1,x′i1,ti1),(Ai2,x′i2,ti2),…,(Aim,x′im,tim)}可行,則對于?k≤l,有∑{m|tim<kΤ}x′im≥k∑j=1Ρj,反之亦成立.定義2若已有資源可以滿足調(diào)度需求,則存在一個可行的調(diào)度方案,反之亦成立.定理1若在已經(jīng)排好序的時間序列中插入周期的時間:t1≤t2≤…≤tc1<T≤tc1+1≤tc1+2≤…≤tc2<2T≤…≤tcl<lT成立,則已有資源滿足調(diào)度需求的充要條件為:對?k<l,有∑{i|i≤ck}xi≥k∑j=1Ρj(2)證明①充分性:對?k<l,有∑{i|i≤ck}xi≥k∑j=1Ρj,只需取方案φ={(A1,x1,t1),(A2,x2,t2),…,(Acl,xcl,tcl)}即可.②必要性:已有資源滿足調(diào)度需求,則存在一個可行的調(diào)度方案,令其為φ*={(As1,x′s1,ts1),(As2,x′s2,ts2),…,(Asm,x′sm,tsm)}(3)式中,0≤x′si≤xsi,i=1,2,…,m表示該點所供給的應(yīng)急資源量不超過其資源可用量,s1,s2,…,sm(m≤n)為1,2,…,n的一個子排列.由定義1知∑{m|tsm<kΤ}x′sm≥k∑j=1Ρj,又x′sm≤xsm,tsm≤tck<kT.則對?k<l,有∑{i|i≤ck}xi≥∑{m|tsm<kΤ}xsm≥∑{m|tsm<kΤ}x′sm≥k∑j=1Ρj,即有∑{i|i≤ck}xi≥k∑j=1Ρj.證畢.定理2若已有資源滿足資源調(diào)度需求,則最早應(yīng)急調(diào)度方案為φ={(A1,x1,t1),(A2,x2,t2),…,(Am-1,xm-1,tm-1),(Am,x′m,tm)}(4)式中,tm≤tcl,x1>0,x2>0,?,xm-1>0,x′m>0,x′m=l∑j=1Ρj-m-1∑i=1xi,并且有m∑i=1xi≥l∑j=1Ρj>m-1∑i=1xi.證明首先,由條件易知Tmin(φ)=t1,T(φ)=tm-t1,Tmax(φ)=tm.因為t1=min{t1,t2,…,tn},所以,此方案為最早應(yīng)急調(diào)度方案.其次,由于方案φ滿足需求,所以m∑i=1xi≥l∑j=1Ρj,令φ*為任意一個滿足調(diào)度需求的調(diào)度方案,因為x′m>0,所以存在l∑j=1Ρj>m-1∑i=1xi,即前面m-1個出救點無法滿足調(diào)度需求,任意滿足最早調(diào)度時間大于等于tm,即min{Tmax(φ*)}≥tm,所以φ為最早應(yīng)急調(diào)度方案,并且有m∑i=1xi≥l∑j=1Ρj>m-1∑i=1xi.證畢.從上面的證明中可以找到應(yīng)急時間最早的算法如下:算法1應(yīng)急時間最早的算法.①對已有的時間和周期進(jìn)行排序得到t1<t2<…<tc1<T≤tc1+1<tc1+2<…<tc2<2T≤…<tcl<lT②判斷?k<l,∑{i|i≤ck}xi≥k∑j=1Ρj是否成立,若等式成立,轉(zhuǎn)③;否則,調(diào)度失敗,退出.③計算m,使得m∑i=1xi≥l∑j=1Ρj>m-1∑i=1xi,則調(diào)度方案為φ=(A1,x1,t1),(A2,x2,t2),…,Am,l∑j=1Ρj-m-1∑i=1xi,tm)}(5)式(5)即為通過算法1所得到的應(yīng)急時間最早方案.同時Tmin(φ)=t1,Tmax(φ)=tm,T(φ)=tm-t1,N(φ)=m.在脈沖需求的資源調(diào)度中,已經(jīng)考慮了資源的時間性,即脈沖周期,只要調(diào)度的資源在一定時間內(nèi)能夠滿足需求,則說明調(diào)度成功.由定義1可知,在脈沖資源需求下,考慮出救點數(shù)最少比考慮應(yīng)急時間最早更有實際意義,因此,本文將進(jìn)一步研究出救點數(shù)最少的資源調(diào)度問題.算法2出救點數(shù)最少的算法.①對時間和周期進(jìn)行排序得到t1<t2<…<tc1<T≤tc1+1<tc1+2<…<tc2<2T≤…<tcl<lT②判斷?k<l,∑{i|i≤ck}xi≥k∑j=1Ρj是否成立,若等式成立,轉(zhuǎn)③;否則,調(diào)度失敗,退出.③令k=1,Ttotal=0,I=?.④求解ik:xik=maxxii∈{c|tc<kΤ,c?Ι}.⑤若Τtotal+xik≥∑j=1lΡj則得出救點數(shù)最少的方案為φ=(Ai1,xi1,ti1),(Ai2,xi2,ti2),…,Aik,∑j=1lΡj-∑c=1k-1xic,tik)}(6)出救點數(shù)為N(I)=k,否則令Ttotal=Ttotal+xik,I=I+{ik}轉(zhuǎn)⑥.⑥求m:若∑j=1mΡj>Τtotal≥∑j=1m-1Ρj,則令k=m,轉(zhuǎn)④.通過算法2得到的方案φ=(Ai1,xi1,ti1),(Ai2,xi2,ti2),…,Aik,∑j=1lΡj-∑c=1k-1xic,tik就是所需要的出救點數(shù)最少的方案,同時Tmin(φ)=ti1,Tmax(φ)=tik,T(φ)=tik-ti1,N(φ)=k.為了驗證算法2的有效性,本文將從理論上進(jìn)一步證明這個結(jié)論.定理3算法2得到的結(jié)果是出救點數(shù)最少的方案.證明令I(lǐng)i表示脈沖數(shù)為i條件下的出救點下標(biāo)代碼的集合,N(Ii)表示集合Ii中元素的個數(shù),N(Pi)表示滿足i次脈沖需求的最少出救點數(shù),下面用數(shù)學(xué)歸納法證明.假設(shè)只有一次脈沖,即只是一次性的需求,此時l=1,通過算法得到的出救點數(shù)為N(I1).首先由算法2中步驟④可知?x′∈{xii∈I1}和?x″∈{x1,x2,…,xj1},有x′>x″,又因為有∑i∈Ι1xi>Ρ1,所以N(P1)≤N(I1);同時要使得出救點數(shù)最少,必定在{Aii∈I1}中選取;其次通過算法2中步驟⑥還可得到?x∈{xii∈I1},有∑xi∈{xi|i∈Ι1}-{x}xi<Ρ1,在{xii∈I1}中去掉任何一個出救點都不可能滿足資源需求,即N(P1)>N(I1)-1,N(P1)≥N(I1),所以N(P1)=N(I1),而且通過算法2獲得的方案φ是出救點數(shù)最少的方案,為N(I1).假設(shè)有α次脈沖,即當(dāng)l=α?xí)r,上述結(jié)論成立,即當(dāng)出救點數(shù)為N(Iα)時,方案為φα=(Ai1,xi1,ti1),(Ai2,xi2,ti2),…,Aik,∑j=1αΡj-∑m=1Ν(φα)-1xim,tik)}(7)當(dāng)l=α+1時,對于前α次調(diào)度需求,根據(jù)算法2中步驟⑥可以得到滿足前α次調(diào)度的方案為φ′α={(Ai1,xi1,ti1),(Ai2,xi2,ti2),…,(Aik,xik,tik)}(8)當(dāng)∑m=1kxim≥∑j=1α+1Ρi,此時的調(diào)度方案為φα+1=(Ai1,xi1,ti1),(Ai2,xi2,ti2),…,Aik,∑j=1α+1Ρj-∑m=1Ν(φα+1)-1xim,tik)}(9)當(dāng)∑m=1kxim<∑j=1α+1Ρj時,由算法2進(jìn)一步得到Iα+1=Iα+I′,其中I′是通過算法得到的點的下標(biāo).由算法2知,?x′∈I′和?x″∈{x1,x2,…,xjα+1}-Iα+1,有x′>x″,要滿足多出來的需求必定在I′選擇出救點,即總的出救點在Iα+1中選擇,有N(Iα+1)≥N(Pα+1);其次,由算法2步驟⑥知:?x∈Iα+1,有∑xi∈{xi|i∈Ια+1}-{x}xi<∑j=1α+1Ρj,因此N(Pα+1)≥N(Iα+1),所以可以進(jìn)一步得到:N(Pα+1)=N(Iα+1),即N(Iα+1),當(dāng)l=α+1時結(jié)論也成立.綜上所述:算法2得到的結(jié)果是出救點數(shù)最少的方案.同時從證明過程和算法2易知:Tmin(φ)=ti1,Tmax(φ)=tik,T(φ)=tik-ti1,N(φ)=k.證畢.3預(yù)調(diào)方案證明假設(shè)應(yīng)急資源需求脈沖周期是2,需求脈沖次數(shù)是4,需求量分別為20,16,13,10,各應(yīng)急資源供應(yīng)點數(shù)據(jù)如表1所示.首先驗證式(2):15+10+5=30>2030+12+7=49>36=20+1649+10+12=71>49=36+1371+7+8=86>59=49+10所以,已有資源可以滿足資源調(diào)度的需求.通過算法1得到應(yīng)急時間最早調(diào)度方案為φ1={(A1,15,1),(A2,10,1),(A3,5,1),(A4,12,2),(A5,7,3),(A6,10,4)}式中,Tmin(φ1)=1,Tmax(φ1)=4,T(φ1)=4-1=3,N(φ1)=6.通過算法2得到出救點數(shù)最少的調(diào)度方案為φ2={(A1,15,1),(A2,10,1),(A4,12,2),(A7,12,5),(A6,10,4)}式中,Tmin(φ2)=1,Tmax(φ2)=5,T(φ2)=5-1=4,N(φ2)=5.通過上述簡單的算例驗證了本文提出的2