一類基于同步多重休眠的損失制分組排隊

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

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

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

針對排隊系統產生的能耗浪費問題，部分文獻引入休假排隊理論。

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

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

1 模型描述

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

圖1 損失制排隊系統流程

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

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

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

當顧客到達Ⅱ組時，Ⅱ組服務臺正處于休眠狀態，則顧客進入Ⅱ組服務臺處等候。當等候的顧客數達到閾值K(0

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

此外，約定到達時間間隔、服務時間是相互獨立的，排隊規則為先到先服務[12]。基于以上假設，得到一個M/M/m+n/m+n損失制分組排隊。

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

Ω=Ω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)}

設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 模型的穩態概率分布

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

設{(S1(t),N1(t),S2(t),N2(t)),t≥0}水平為j的穩態概率向量為π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

設{(S1(t),N1(t),S2(t),N2(t)),t≥0}的穩態概率分布為Π，則

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

結合連續時間馬爾科夫鏈的穩態平衡方程以及歸一化條件，穩態概率分布Π與矩陣Q滿足方程組如下：

(2)

3 系統的性能指標

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

(3)

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

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

設整個系統中顧客的平均逗留時間為E[W]，則

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

(5)

設Ⅰ組服務臺由高速狀態轉換為低速狀態后單位時間內所節省的能量為S1，且

(6)

其中，H1和H2分別表示單位時間內Ⅰ組服務臺處于高速狀態和低速狀態所消耗的能量。

設Ⅱ組服務臺由運行狀態轉換為休眠狀態后單位時間內所節省的能量為S2，且

(7)

其中，H3和H4分別表示單位時間內Ⅱ組服務臺處于運行狀態和休眠狀態所消耗的能量。

設Ⅱ組服務臺單位時間內被喚醒過程中所消耗的額外總能量為S3，且

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

(8)

其中，H5表示Ⅱ組服務臺單位時間內每次休眠結束被喚醒所消耗的能量。

設單位時間內整個系統節省的能量即系統節能率為S，則

S=S1+S2-S3

(9)

4 數值結果

為分析所提出的休眠機制對兩個性能指標的影響，筆者在MATLAB R2016a環境下進行數值實驗，并給出結果分析。數值實驗中系統參數假設見表1。

表1 數值實驗參數

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

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

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

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

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

圖3 系統節能率的變化趨勢

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

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

5 結論與討論

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

本次研究針對損失制排隊系統的節能問題提出一個優化方案。后續的研究重點則是基于算法對休眠閾值進行數值優化，同時考慮從經濟學角度出發，引入博弈思想，構造收益函數，提高系統的經濟效益。