崔 瑜，毛學(xué)志，劉思嚴(yán)，牛 然

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

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

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

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

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

1 模型描述

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

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

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

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

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

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

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

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

設(shè)隨機(jī)變量S1(t)表示t(t≥0)時(shí)刻Ⅰ組服務(wù)臺(tái)所處的狀態(tài)，其中S1(t)=0與S1(t)=1分別表示低速和高速狀態(tài)，隨機(jī)變量S2(t)表示t時(shí)刻Ⅱ組服務(wù)臺(tái)所處的狀態(tài)，其中S2(t)=0與S2(t)=1分別表示運(yùn)行狀態(tài)與休眠狀態(tài)。設(shè)隨機(jī)變量N1(t)=i(i∈{0,1,…,n})表示t時(shí)刻Ⅰ組的顧客數(shù)量，隨機(jī)變量N2(t)=j(j∈{0,1,…,m})表示t時(shí)刻Ⅱ組的顧客數(shù)量。那么，{(S1(t),N1(t),S2(t),N2(t)),t≥0}是一個(gè)擬生滅過(guò)程(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為一個(gè)(n+1)(n+1)階方陣，且

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

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

Au=

Am為一個(gè)m×m階方陣，且

Am=

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

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

Bk為一個(gè)K×K階矩陣，且

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

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

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

CK-1為一個(gè)K×K階矩陣，且

Cu(u=K,K+1,…,m-1)為一個(gè)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ù)時(shí)間馬爾科夫鏈的穩(wěn)態(tài)平衡方程以及歸一化條件，穩(wěn)態(tài)概率分布Π與矩陣Q滿足方程組如下：

(2)

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

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

(3)

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

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

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

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

(5)

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

(6)

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

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

(7)

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

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

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

(8)

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

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

S=S1+S2-S3

(9)

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

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

表1 數(shù)值實(shí)驗(yàn)參數(shù)

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

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

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

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

圖2 顧客平均逗留時(shí)間的變化趨勢(shì)

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

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

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

5 結(jié)論與討論

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

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