融合斯塔克爾伯格模型的港口吞吐量預(yù)測(cè)方法

宋凌玉

(集美大學(xué) 誠(chéng)毅學(xué)院，福建 廈門 361021)

港口吞吐量既是港口企業(yè)管理的目標(biāo)之一，也是港口設(shè)施和經(jīng)營(yíng)管理水平的綜合性反映[1-2].同時(shí)，根據(jù)吞吐量預(yù)測(cè)結(jié)果可以確定港口通過(guò)能力規(guī)模，從而使港口設(shè)施能較好地滿足未來(lái)發(fā)展的要求[3].多港口的數(shù)據(jù)預(yù)測(cè)算法需先設(shè)定所有吞吐量都保持互相獨(dú)立，再通過(guò)與“裝箱問(wèn)題”相似的求解算法完成數(shù)據(jù)預(yù)測(cè)[4-5].此算法雖然開(kāi)銷小，但忽略了吞吐量間同步互斥的約束關(guān)系[6].本文針對(duì)港口吞吐量中的多變量，提出了一種融合斯塔克爾伯格模型的港口吞吐量預(yù)測(cè)算法.此算法對(duì)港口吞吐量中的各項(xiàng)指標(biāo)進(jìn)行了分類處理并形成了多個(gè)數(shù)據(jù)子集，將相關(guān)數(shù)據(jù)子集移至相同的某一資源庫(kù)內(nèi)，能夠有效防止出現(xiàn)港口數(shù)據(jù)的擁擠現(xiàn)象.實(shí)驗(yàn)結(jié)果表明，該算法預(yù)測(cè)能力高于同類算法.

1 港口吞吐量相關(guān)知識(shí)定義

采用三元組τi=(Ti,Ci,πi)的形式來(lái)表示周期多變量吞吐量(Task)i，其中，Ti代表吞吐量的周期，πi代表優(yōu)先級(jí)，Ci代表最壞執(zhí)行時(shí)間.每當(dāng)一個(gè)周期發(fā)生時(shí)，τi先處于就緒狀態(tài)，之后發(fā)生無(wú)釋放抖動(dòng)，每執(zhí)行一次τi就代表一項(xiàng)吞吐量實(shí)例,通常將其用Ji進(jìn)行表示.吞吐量的相對(duì)截止期限與其周期保持一致.

定義1 采用ui表示τi的CPU利用率，等于τi最壞執(zhí)行時(shí)間和周期間的比值結(jié)果，將其用等式ui=Ci/Ti表達(dá).周期吞吐量集合Γ={τ1,τ2,…,τn}的執(zhí)行場(chǎng)所是m個(gè)港口共同構(gòu)成的同構(gòu)型港口處理器P={p1,p2,…,pm}.其中，p(τi)代表τi所處的港口,τ(pk)代表被分配在港口pk的所有吞吐量集合.此港口總共由q個(gè)港口吞吐量Φ={ρ1,ρ2,…,ρq}構(gòu)成,其中，Θi∈Φ的含義是在τi訪問(wèn)的港口吞吐量中，τi需滿足互斥訪問(wèn)條件?ρs∈Θi.當(dāng)ρs只是被分配在相同港口并進(jìn)行吞吐量訪問(wèn)時(shí)，應(yīng)該將其稱作局部資源，反之則是屬于全局資源.將Ф中局部的資源集合用ФL進(jìn)行表示,并將全局資源集合用ΦG進(jìn)行表示.如果τi∈Γ以及其它港口吞吐量不會(huì)對(duì)同一類型吞吐量進(jìn)行訪問(wèn)時(shí)，則可將τi稱作獨(dú)立吞吐量,同時(shí)將Γ內(nèi)的各項(xiàng)獨(dú)立吞吐量共同構(gòu)成的數(shù)據(jù)集合以Γ′來(lái)表示.

吞吐量的訪問(wèn)過(guò)程發(fā)生阻塞的情況出現(xiàn)在該請(qǐng)求訪問(wèn)期間全局資源被其它的港口鎖定的條件下.按照MSRP協(xié)議的要求，吞吐量需保持預(yù)測(cè)狀態(tài)以等待全局資源.當(dāng)多個(gè)港口吞吐量同時(shí)等待某一相同的全局資源時(shí),為防止出現(xiàn)餓死的現(xiàn)象，MSRP選擇FIFO預(yù)測(cè)的方式得以解決.

引理1 假設(shè)τj對(duì)全局資源ρs進(jìn)行一次訪問(wèn)所需的時(shí)間最長(zhǎng)是ξj,s,則滿足任意τi∈pk對(duì)ρs而進(jìn)行訪問(wèn)請(qǐng)求的時(shí)間最長(zhǎng)為

(1)

定義2 預(yù)測(cè)偏差(Sk)等于此港口吞吐量處于tLCM時(shí)間段中的最長(zhǎng)預(yù)測(cè)等待時(shí)間跟tLCM的比值.tLCM等于此港口吞吐量周期最小公倍數(shù).

為確保港口具備實(shí)時(shí)可調(diào)度的性質(zhì)，需保留合理的處理器資源，以此保證該港口無(wú)論在何種狀態(tài)下都可以達(dá)到實(shí)時(shí)吞吐量所需的截止時(shí)限標(biāo)準(zhǔn).由此可見(jiàn)，可以通過(guò)減小預(yù)測(cè)偏差的方法來(lái)降低港口的整體資源耗費(fèi)，從而有效地改善港口的利用率.

定理1 對(duì)于任意調(diào)度τi∈pk，由其產(chǎn)生的港口可調(diào)度性損失和τi對(duì)pk形成的預(yù)測(cè)偏差Sk(i)相等，即

(2)

2 港口吞吐量預(yù)測(cè)算法

該策略的實(shí)現(xiàn)過(guò)程為:首先把存在于Γ港口吞吐量沖突的各項(xiàng)數(shù)據(jù)分到一個(gè)數(shù)據(jù)集合，同時(shí)把相同數(shù)據(jù)子集都劃分到同一類型中.當(dāng)任意選擇的吞吐量τ1和τ2對(duì)資源ρ1進(jìn)行訪問(wèn)，同時(shí)τ2和τ3對(duì)資源ρ2進(jìn)行訪問(wèn)，那么上述3項(xiàng)吞吐量屬于相同的數(shù)據(jù)子集，結(jié)果見(jiàn)圖1.

圖1 數(shù)據(jù)預(yù)測(cè)策略

將?！渲械臄?shù)據(jù)預(yù)測(cè)到任何一個(gè)港口中都不會(huì)造成吞吐量的阻塞現(xiàn)象.可以采用下述遞歸算法來(lái)完成港口吞吐量預(yù)測(cè)：

(1)假定各港口吞吐量在初始狀態(tài)下都保持相互獨(dú)立狀態(tài)(.indep←TRUE)，并且沒(méi)有對(duì)其進(jìn)行分組(.link←NONE).

(2)如果各港口吞吐量對(duì)應(yīng)的.link都不是NONE,此時(shí)，算法結(jié)束；反之，從中選定某一沒(méi)有進(jìn)行過(guò)分組處理的吞吐量τi(τi.linkisNONE)，對(duì)該數(shù)據(jù)的分組狀態(tài)進(jìn)行修改至τi.link←i,之后再判斷τi是否要跟其它吞吐量共同對(duì)港口吞吐量進(jìn)行訪問(wèn).

(3)如果τi和其它某一吞吐量τj同時(shí)訪問(wèn)同一類型吞吐量，則將此二吞吐量的狀態(tài).indep同時(shí)設(shè)定成FALSE,把τj的分組狀態(tài)設(shè)定成τi.link,再把τi和τj分組到相同的數(shù)據(jù)子集內(nèi)；之后采用遞歸方法從τj開(kāi)始重新執(zhí)行這一步驟.

(4)分析τi和后續(xù)的吞吐量是否要對(duì)同一類型吞吐量進(jìn)行訪問(wèn)操作，當(dāng)需要對(duì)同一類型吞吐量進(jìn)行訪問(wèn)時(shí)，便跳轉(zhuǎn)至步驟(3)；反之，跳轉(zhuǎn)到步驟(2).

當(dāng)上述各項(xiàng)步驟都完成之后，各項(xiàng).indep值結(jié)果都是TRUE的吞吐量便成為獨(dú)立數(shù)據(jù)，并共同組成了獨(dú)立數(shù)據(jù)子集?！?，同時(shí).link值相等的各港口吞吐量被分組至相同的數(shù)據(jù)子集內(nèi).由此生成相應(yīng)的數(shù)據(jù)子集.本文提出了預(yù)測(cè)吞吐量方法，如下所示：

引理2 對(duì)于任意τi與τj∈τ(pk)在pk上形成的預(yù)測(cè)偏差是τi和τj各自具有的pk預(yù)測(cè)偏差相加所得的結(jié)果

Sk(i+j)=Sk(i)+Sk(j)

(3)

以矩陣Ux×q來(lái)表示x(1≤x≤n)個(gè)對(duì)港口吞吐量進(jìn)行訪問(wèn)所需的最長(zhǎng)時(shí)間.元素ui,s代表第i次τc對(duì)港口吞吐量ρs進(jìn)行訪問(wèn)所需的最長(zhǎng)時(shí)間，則根據(jù)引理1有ui,s=ξc,s.如果ui,s=0,則說(shuō)明τc未對(duì)港口吞吐量ρs進(jìn)行訪問(wèn).

(4)

定理2 設(shè)?！?{τa,τb,…,τc}(x=|?！獆≤n)為算法1獲得的數(shù)據(jù)子集，通過(guò)x×q(q是港口吞吐量的數(shù)量)階矩陣Ux×q來(lái)表達(dá)?！獙?duì)港口吞吐量進(jìn)行訪問(wèn)所花費(fèi)的時(shí)間.對(duì)于從?！胁鸱值玫降娜我猞觟并將其分配至港口pr中,同時(shí)其它存在于?！械乃袛?shù)據(jù)被預(yù)測(cè)到港口pk中(r≠k)，那么?！械氖Ｓ嗤掏铝克a(chǎn)生的港口pk預(yù)測(cè)偏差為

(5)

(6)

其中，?！猧=?！?{τi};f(d)為矩陣Ux×q第d行對(duì)應(yīng)的港口序號(hào).

3 實(shí)驗(yàn)與結(jié)果分析

3.1 性能指標(biāo)

本文采用吞吐量集合接受率來(lái)驗(yàn)證預(yù)測(cè)算法的性能，假定每次實(shí)驗(yàn)都會(huì)生成N=10 000個(gè)隨機(jī)吞吐量集合，預(yù)測(cè)算法A最大可以對(duì)M個(gè)數(shù)據(jù)集合進(jìn)行調(diào)度，此時(shí)算法A對(duì)應(yīng)的吞吐量集合能達(dá)到的接受率等于M/N.如果得到的吞吐量集合接受率較大，則說(shuō)明此算法的效率也相應(yīng)更高.同時(shí)還對(duì)比了不同算法所具有的港口平均預(yù)測(cè)偏差,其定義為：

(7)

3.2 實(shí)驗(yàn)分析

港口吞吐量是一個(gè)體現(xiàn)港口規(guī)模及對(duì)港口城市社會(huì)影響力的綜合性指標(biāo)，而GDP則是一個(gè)較全面反映一個(gè)地區(qū)經(jīng)濟(jì)發(fā)展水平的綜合性經(jīng)濟(jì)指標(biāo).因此，在一般情況下，港口吞吐量與國(guó)內(nèi)生產(chǎn)總值之間的關(guān)系甚為密切.選取“2007—2017”年舟山GDP與舟山港口吞吐量的資料(見(jiàn)表1)進(jìn)行分析，關(guān)系圖見(jiàn)圖2.從港口吞吐量與GDP關(guān)系分析可知，舟山港口吞吐量與GDP之間的關(guān)系很不密切，吞吐量增長(zhǎng)速度比GDP的快得多.

表1 舟山歷年港口吞吐量與舟山國(guó)內(nèi)生產(chǎn)總值比較

圖2 舟山GDP與舟山港口吞吐量之關(guān)系

圖3顯示了在臨界區(qū)長(zhǎng)度等于4以及每項(xiàng)吞吐量具有的臨界區(qū)數(shù)量為2的條件下，港口利用率SU與集合接受率間的關(guān)系.從圖3中可以看到，不同算法的吞吐量集合接受率與SU之間表現(xiàn)為單調(diào)遞減的變化關(guān)系.當(dāng)WFD和Syn-aware算法處于SU>0.6的條件下，吞吐量集合將具有不可調(diào)度的特征，F(xiàn)MPTSM算法則需滿足SU>0.7的條件才會(huì)發(fā)生吞吐量集合的不可調(diào)度現(xiàn)象.對(duì)這兩種算法進(jìn)行比較可知，F(xiàn)MPTSM算法具有更大的吞吐量集合接受率.

圖3 吞吐量集合接受率與港口利用率之間的關(guān)系

圖4顯示了不同算法性能與臨界區(qū)長(zhǎng)度之間的關(guān)系，從圖中可以看到各港口吞吐量分別由2個(gè)臨界區(qū)構(gòu)成，此時(shí)SU=0.65.當(dāng)臨界區(qū)的長(zhǎng)度增大后，需要等待的吞吐量預(yù)測(cè)時(shí)間也會(huì)隨之增大，此時(shí)算法吞吐量集合接受率也會(huì)出現(xiàn)下降現(xiàn)象.如果無(wú)法將所有的數(shù)據(jù)子集都分配至相同的港口上時(shí)，可以利用FMPTSM算法并結(jié)合相關(guān)度分析結(jié)果對(duì)吞吐量進(jìn)行拆分后再將其分配至相同的港口，所以吞吐量只對(duì)特定港口吞吐量進(jìn)行預(yù)測(cè)等待，有效降低了預(yù)測(cè)偏差.

圖4 臨界區(qū)長(zhǎng)度和吞吐量集合接受率的關(guān)系曲線

4 結(jié)語(yǔ)

本文提出了一種融合斯塔克爾伯格模型的港口吞吐量預(yù)測(cè)算法，通過(guò)結(jié)合港口吞吐量與數(shù)據(jù)預(yù)測(cè)策略，有效避免了在港口間發(fā)生阻塞現(xiàn)象，以此增加港口的利用率.同時(shí)，本文與其它算法進(jìn)行對(duì)比，結(jié)果顯示，采用此方法法對(duì)港口吞吐量的預(yù)測(cè)具有比Syn-aware與WFD更高的效率.