崔 瑜，毛學志，劉思嚴，牛 然

(河北科技師范學院數(shù)學與信息科技學院，河北 秦皇島，066004)

損失制排隊是一類經(jīng)典的排隊模型，其在發(fā)展過程中不斷被豐富、優(yōu)化，并被廣泛應(yīng)用于不同的實際問題。樊亦鳴[1]給出了帶有柔性配置的損失制排隊的平穩(wěn)分布，并計算出顧客損失率，同時基于算法分析了相關(guān)參數(shù)對顧客損失率的影響。劉云杰[2]將損失制排隊應(yīng)用到多線程網(wǎng)絡(luò)服務(wù)軟件系統(tǒng)中，通過數(shù)據(jù)的采集，利用Maple軟件進行編程計算出該系統(tǒng)的性能指標。李軍等[3]基于損失制排隊系統(tǒng)效率指標計算方法，建立了站點最優(yōu)化車輛調(diào)配數(shù)(空樁數(shù))的計算模型，并計算出蘇州高新區(qū)金獅大廈站點在早晚高峰期應(yīng)調(diào)配的車輛數(shù)。針對排隊系統(tǒng)中的顧客流輸入具有較大的差異性，張傳龍[4]對顧客進行分類，將損失制與等待制排隊模型進行組合，其仿真實驗結(jié)果表明該策略提高了汽車檢測的有效吞吐量，同時有效地降低了系統(tǒng)運行成本。黃健[5]以完善院內(nèi)急救一體化制度，打通搶救流程的綠色通道為目的，設(shè)計了以損失制排隊作為第一階段的多階段串聯(lián)排隊系統(tǒng)，并建立了以總滯留可能性最小為目標的數(shù)學規(guī)劃模型，對各科室床位進行優(yōu)化配置，其結(jié)果對多階段床位資源的配置優(yōu)化具有重要意義。以上文獻對經(jīng)典的損失制排隊進行了發(fā)展，卻較少涉及節(jié)約系統(tǒng)能耗的研究。

針對排隊系統(tǒng)產(chǎn)生的能耗浪費問題，部分文獻引入休假排隊理論。

為了在移動寬帶城域網(wǎng)中獲得更好的節(jié)能效果，張麗媛等[6]建立了帶有休假延遲且休假長度指數(shù)變化的多重休假排隊模型，并給出了系統(tǒng)切換率、能量節(jié)省率和平均響應(yīng)時間等性能指標的解析表達式。曹建[7]針對區(qū)塊鏈技術(shù)提出了一種新的節(jié)能運行機制，將比特幣故障礦池運行模式建模為帶休眠喚醒策略和工作故障策略的排隊系統(tǒng)，并通過構(gòu)造能耗函數(shù)和節(jié)能率函數(shù)分析礦池能耗。馬占友等[8]以提高云系統(tǒng)的節(jié)能水平為目標，同時兼顧虛擬機狀態(tài)頻繁切換所造成的損失，將同步休眠和異步休眠相結(jié)合，提出一種基于M/M/c休假排隊理論的虛擬機調(diào)度策略。李君[9]使用空竭服務(wù)的休假排隊模型對異構(gòu)云計算中的任務(wù)調(diào)度進行建模，并提出一種任務(wù)調(diào)度算法，以降低云計算的系統(tǒng)能耗。徐剛[10]利用母函數(shù)方法，求出了帶有中途退出的M/M/1單重工作休假排隊系統(tǒng)忙期和工作休假期的相關(guān)性能指標，并給出兩個服務(wù)率對系統(tǒng)性能指標影響的數(shù)值結(jié)果分析。

受以上文獻啟發(fā)，有別于現(xiàn)有研究成果，筆者圍繞系統(tǒng)能耗節(jié)約問題對經(jīng)典的損失制排隊進行了優(yōu)化和改進。以保證系統(tǒng)響應(yīng)性能與節(jié)約系統(tǒng)能耗為目標，本次研究建立了一個基于同步多重休眠機制，帶有雙速率可調(diào)節(jié)的M/M/m+n/m+n損失制分組排隊。通過構(gòu)造馬爾科夫鏈和利用矩陣幾何解得出兩個系統(tǒng)性能指標：顧客的平均逗留時間和系統(tǒng)節(jié)能率?；贛atlab軟件通過數(shù)值實驗筆者還給出了休眠機制對兩個系統(tǒng)性能指標的影響分析。

1 模型描述

為緩解損失制系統(tǒng)產(chǎn)生的能耗浪費問題，實現(xiàn)綠色節(jié)能，本次研究將損失制系統(tǒng)中的所有服務(wù)臺分為兩組，并引入同步多重休眠機制[11]。顧客進入系統(tǒng)的流程見圖1。

圖1 損失制排隊系統(tǒng)流程

假定顧客到達為參數(shù)λ(λ>0)的泊松流，若Ⅰ組有空閑的服務(wù)臺可提供服務(wù)，則顧客立即進入Ⅰ組接受服務(wù)。假設(shè)Ⅰ組有n個同構(gòu)的服務(wù)臺，設(shè)L為調(diào)節(jié)服務(wù)臺服務(wù)速率的閾值，當Ⅰ組處于忙期的服務(wù)臺數(shù)量不足L時，每個正在接受服務(wù)的顧客所需服務(wù)時間均服從參數(shù)為μ0的負指數(shù)分布；而當處于忙期的服務(wù)臺數(shù)量達到L時，每個正在接受服務(wù)的顧客所需的服務(wù)時間均服從參數(shù)為μ1(μ1>μ0)的負指數(shù)分布。顧客接受完服務(wù)后立即離開系統(tǒng)。

當顧客到達系統(tǒng)時，若Ⅰ組所有服務(wù)臺均處于忙期，則顧客到達Ⅱ組。若Ⅱ組所有服務(wù)臺也均處于忙期，則顧客不會等待，立即離開系統(tǒng)。

當顧客到達Ⅱ組時，Ⅱ組至少有一個空閑的服務(wù)臺可提供服務(wù)，則顧客立即進入Ⅱ組接受服務(wù)。假設(shè)Ⅱ組有m個同構(gòu)的服務(wù)臺，每個正在接受服務(wù)的顧客所需服務(wù)時間服從參數(shù)為μ2的負指數(shù)分布。當Ⅱ組所有顧客接受完服務(wù)離開系統(tǒng)后，Ⅱ組所有服務(wù)臺將同步進入休眠狀態(tài)。

當顧客到達Ⅱ組時，Ⅱ組服務(wù)臺正處于休眠狀態(tài)，則顧客進入Ⅱ組服務(wù)臺處等候。當?shù)群虻念櫩蛿?shù)達到閾值K(0

當Ⅱ組服務(wù)臺處于忙期時，一旦Ⅰ組出現(xiàn)空閑服務(wù)臺且無新到達顧客，倘若系統(tǒng)中總的顧客數(shù)大于0且小于閾值L，則Ⅱ組中的顧客將全部被遷移到Ⅰ組接受服務(wù)，且服務(wù)率為μ0，同時Ⅱ組服務(wù)臺隨即進入同步休眠狀態(tài)；倘若系統(tǒng)中總的顧客數(shù)大于等于閾值L且小于等于n，則Ⅱ組中的顧客全部被遷移到Ⅰ組接受服務(wù)，但服務(wù)率為μ1。

此外，約定到達時間間隔、服務(wù)時間是相互獨立的，排隊規(guī)則為先到先服務(wù)[12]?；谝陨霞僭O(shè)，得到一個M/M/m+n/m+n損失制分組排隊。

設(shè)隨機變量S1(t)表示t(t≥0)時刻Ⅰ組服務(wù)臺所處的狀態(tài)，其中S1(t)=0與S1(t)=1分別表示低速和高速狀態(tài)，隨機變量S2(t)表示t時刻Ⅱ組服務(wù)臺所處的狀態(tài)，其中S2(t)=0與S2(t)=1分別表示運行狀態(tài)與休眠狀態(tài)。設(shè)隨機變量N1(t)=i(i∈{0,1,…,n})表示t時刻Ⅰ組的顧客數(shù)量，隨機變量N2(t)=j(j∈{0,1,…,m})表示t時刻Ⅱ組的顧客數(shù)量。那么，{(S1(t),N1(t),S2(t),N2(t)),t≥0}是一個擬生滅過程(QBD)[13]，設(shè)QBD的狀態(tài)空間為Ω，且

Ω=Ω0∪Ω1∪…∪Ωm

其中，

Ω0={(0,0;0,0),(0,1;0,0),…,(0,L-1;0,0),(1,L;0,0),…,(1,n;0,0)}

Ω1={(1，n;0,1),(1,n;1,1)}

? ?

ΩK-1={(1,n;0,K-1),(1,n;1,K-1),…,(1,n-K+2;1,K-1)}

ΩK={(1,n;1,K),(1,n-1;1,K),…,(1,n-K+1;1,K)}

? ?

Ωm={(1,n;1,m),(1,n-1;1,m),…,(1,n-m+1;1,m)}

設(shè)QBD的生成元[13]為矩陣Q，且

(1)

其中，A0為一個(n+1)(n+1)階方陣，且

Au(u=1,2,…,K-1)為一個(u+1)×(u+1)階方陣，且

而Au(u=K,K+1,…,m-1)為一個u×u階方陣，且

Au=

Am為一個m×m階方陣，且

Am=

B1為一個2×(n+1)階矩陣，且

Bu(u=2,3,…,K-1)為一個(u+1)×u階矩陣，且

Bk為一個K×K階矩陣，且

Bu(u=K+1,K+2,…,m)為一個u×(u-1)階矩陣，且

C0為一個(n+1)×2階矩陣，且

Cu(u=1,2,…,K-2)為一個(u+1)×(u+2)階矩陣，且

CK-1為一個K×K階矩陣，且

Cu(u=K,K+1,…,m-1)為一個u×(u+1)階矩陣，且

2 模型的穩(wěn)態(tài)概率分布

設(shè){(S1(t),N1(t),S2(t),N2(t)),t≥0}在任一狀態(tài)下的穩(wěn)態(tài)概率為πk,i;l,j，且

設(shè){(S1(t),N1(t),S2(t),N2(t)),t≥0}水平為j的穩(wěn)態(tài)概率向量為πj,j=0,1,…,m，且

π0=(π0,0;0,0,π0,1;0,0,…,π0,L-1;0,0,π1,L;0,0,…,π1,n;0,0)
π1=(π1,n;0,1,π1,n;1,1

? ?

πK-1=(π1,n;0,K-1,π1,n;1,K-1,…,π1,n-K+2;1,K-1)

πK=(π1,n;1,K,π1,n-1;1,K,…,π1,n-K+1;1,K? ?πm=(π1,n;1,m,π1,n-1;1,m,…,π1,n-m+1;1,m

設(shè){(S1(t),N1(t),S2(t),N2(t)),t≥0}的穩(wěn)態(tài)概率分布為Π，則

Π=(π0,π1,…,πm)

結(jié)合連續(xù)時間馬爾科夫鏈的穩(wěn)態(tài)平衡方程以及歸一化條件，穩(wěn)態(tài)概率分布Π與矩陣Q滿足方程組如下：

(2)

3 系統(tǒng)的性能指標

設(shè)Ⅰ組中顧客的平均逗留時間為E[W1]，且

(3)

設(shè)Ⅱ組中顧客的平均隊長為E[N]，且

設(shè)Ⅱ組中顧客的平均逗留時間為E[W2]，由Little公式[12]可得

設(shè)整個系統(tǒng)中顧客的平均逗留時間為E[W]，則

E[W]=E[W1]+E[W2]

(5)

設(shè)Ⅰ組服務(wù)臺由高速狀態(tài)轉(zhuǎn)換為低速狀態(tài)后單位時間內(nèi)所節(jié)省的能量為S1，且

(6)

其中，H1和H2分別表示單位時間內(nèi)Ⅰ組服務(wù)臺處于高速狀態(tài)和低速狀態(tài)所消耗的能量。

設(shè)Ⅱ組服務(wù)臺由運行狀態(tài)轉(zhuǎn)換為休眠狀態(tài)后單位時間內(nèi)所節(jié)省的能量為S2，且

(7)

其中，H3和H4分別表示單位時間內(nèi)Ⅱ組服務(wù)臺處于運行狀態(tài)和休眠狀態(tài)所消耗的能量。

設(shè)Ⅱ組服務(wù)臺單位時間內(nèi)被喚醒過程中所消耗的額外總能量為S3，且

S3=H5π1,n;0,K-1λ

(8)

其中，H5表示Ⅱ組服務(wù)臺單位時間內(nèi)每次休眠結(jié)束被喚醒所消耗的能量。

設(shè)單位時間內(nèi)整個系統(tǒng)節(jié)省的能量即系統(tǒng)節(jié)能率為S，則

S=S1+S2-S3

(9)

4 數(shù)值結(jié)果

為分析所提出的休眠機制對兩個性能指標的影響，筆者在MATLAB R2016a環(huán)境下進行數(shù)值實驗，并給出結(jié)果分析。數(shù)值實驗中系統(tǒng)參數(shù)假設(shè)見表1。

表1 數(shù)值實驗參數(shù)

實驗結(jié)果表明，顧客的平均逗留時間E[W]會隨著Ⅱ組休眠閾值K的增大呈現(xiàn)上升趨勢(圖2(a)，圖2(b)，圖2(c))。因為當Ⅱ組服務(wù)臺處于休眠狀態(tài)時，新到達的顧客需要在服務(wù)臺等待，休眠閾值K越大，顧客需要等待的時間就越長，從而系統(tǒng)中顧客的平均逗留時間E[W]就越大。而對于相同的休眠閾值K，E[W]會隨著Ⅱ組服務(wù)臺的服務(wù)率μ2的增大而減少。因為μ2越大，Ⅱ組服務(wù)臺服務(wù)速率越快，從而系統(tǒng)的整體服務(wù)效率越高，所以系統(tǒng)中顧客的平均逗留時間E[W]就越小。

當Ⅰ組服務(wù)臺的服務(wù)率μ1=0.7，Ⅱ組休眠閾值K=3，Ⅱ組服務(wù)臺的服務(wù)率μ2=1時，顧客的平均逗留時間E[W]與Ⅰ組閾值L的關(guān)系見圖2(a)與圖2(b)，E[W]會隨著的增大而增加。因為L越大，Ⅰ組服務(wù)臺低速運行的時間就越長，從而系統(tǒng)整體服務(wù)時間就越長，那么顧客的平均逗留時間E[W]就越大。

當Ⅰ組閾值L=4，Ⅱ組休眠閾值K=3，Ⅱ組服務(wù)臺的服務(wù)率μ2=1時，顧客的平均逗留時間E[W]與Ⅰ組服務(wù)臺的服務(wù)率μ1的關(guān)系見圖2(a)與圖2(c)，E[W]會隨著μ1的增加而減少。因為μ1越大，Ⅰ組服務(wù)臺的服務(wù)速率越快，從而系統(tǒng)的整體服務(wù)效率越高，相應(yīng)地，顧客的平均逗留時間E[W]就越小。

實驗結(jié)果亦表明，系統(tǒng)節(jié)能率S會隨著Ⅱ組休眠閾值K的增大呈現(xiàn)上升趨勢(圖3(a)，圖3(b)，圖3(c))。因為K越大，Ⅱ組服務(wù)臺處于休眠狀態(tài)的時間就越長，從而整個系統(tǒng)的能量消耗會降低，即系統(tǒng)節(jié)能率S會增大。而對于相同的休眠閾值K，S會隨著Ⅱ組服務(wù)臺的服務(wù)率μ2的增大而增加。因為μ2越大，Ⅱ組服務(wù)臺的服務(wù)速率越快，從而該組服務(wù)臺為所有顧客服務(wù)完進入休眠狀態(tài)的概率就越大，相應(yīng)地，系統(tǒng)節(jié)能率S會隨之增加。

圖2 顧客平均逗留時間的變化趨勢

圖3 系統(tǒng)節(jié)能率的變化趨勢

當Ⅰ組服務(wù)臺的服務(wù)率μ1=0.7，Ⅱ組休眠閾值K=3，Ⅱ組服務(wù)臺的服務(wù)率μ2=4時，系統(tǒng)節(jié)能率S與Ⅰ組閾值L的關(guān)系見圖3(a)與圖3(b)，S會隨著L的增大而增加。因為L越大，Ⅰ組服務(wù)臺低速運行的概率就越大，從而系統(tǒng)的能量消耗就比較少，所以系統(tǒng)節(jié)能率S會增加。

當Ⅰ組閾值L=4，Ⅱ組休眠閾值K=3，Ⅱ組服務(wù)臺的服務(wù)率μ2=4時，系統(tǒng)節(jié)能率S與Ⅰ組服務(wù)臺的服務(wù)率μ1的關(guān)系見圖3(a)與圖3(c)，S會隨著μ1的增大而增加。因為μ1越大，Ⅰ組服務(wù)臺的服務(wù)速率越快，即能夠使顧客盡快接受完服務(wù)離開系統(tǒng)，從而Ⅰ組服務(wù)臺由高速運行狀態(tài)轉(zhuǎn)為低速運行狀態(tài)的概率就越大，進而降低能量消耗，所以系統(tǒng)節(jié)能率S增加。

5 結(jié)論與討論

為了保障排隊系統(tǒng)響應(yīng)性能的同時盡可能減少系統(tǒng)能耗，緩解資源浪費問題，筆者將系統(tǒng)所有服務(wù)臺分為兩組，其中一組引入雙速率可調(diào)節(jié)機制，另外一組引入同步休眠機制。為了進一步節(jié)省系統(tǒng)能耗，本次研究還設(shè)置了兩組之間的任務(wù)可遷移策略。基于以上方案，筆者建立了一個M/M/m+n/m+n損失制混合分組排隊。通過構(gòu)造四維馬爾科夫鏈，利用矩陣幾何解方法推出系統(tǒng)的穩(wěn)態(tài)概率分布，進而得到顧客平均逗留時間和系統(tǒng)節(jié)能率兩個性能指標。最后通過數(shù)值實驗給出兩個指標的性能分析。

本次研究針對損失制排隊系統(tǒng)的節(jié)能問題提出一個優(yōu)化方案。后續(xù)的研究重點則是基于算法對休眠閾值進行數(shù)值優(yōu)化，同時考慮從經(jīng)濟學角度出發(fā)，引入博弈思想，構(gòu)造收益函數(shù)，提高系統(tǒng)的經(jīng)濟效益。