一類N-策略M/G/1排隊系統(tǒng)隊長分布

劉曉燕，孫璽菁，劉 丹

（海軍航空工程學(xué)院系統(tǒng)科學(xué)與數(shù)學(xué)研究所，山東煙臺264001）

自從YADIN 和NAOR[1]引入了N-策略以來，具有N-策略控制機(jī)制的排隊系統(tǒng)理論已取得了豐碩的成果[2-9]。排隊系統(tǒng)隊長的穩(wěn)態(tài)概率分布在系統(tǒng)容量設(shè)計中有著重要的應(yīng)用價值，而直接來求隊長的穩(wěn)態(tài)分布是非常困難的?；诖耍疚难芯繋?關(guān)閉時間的N-策略M/G/1排隊系統(tǒng)，提出了一種簡便有效的算法來推導(dǎo)穩(wěn)態(tài)隊長概率分布的解析結(jié)果。

1 模型描述

本文研究的帶啟動/關(guān)閉時間的N-策略M/G/1 排隊系統(tǒng)模型描述如下：

1）顧客到達(dá)形成參數(shù)為λ的Poisson 流，且根據(jù)到達(dá)順序排成一隊列并實行先到先服務(wù)機(jī)制，服務(wù)臺一次只能服務(wù)一個顧客；

2）系統(tǒng)只有一個服務(wù)臺，服務(wù)時間（記作G）是獨立同分布的隨機(jī)變量且具有一般分布函數(shù)G(t)(t≥0)；

3）系統(tǒng)實行帶啟動/關(guān)閉時間的N-策略休假機(jī)制：每當(dāng)系統(tǒng)變空時，服務(wù)臺不是立即關(guān)閉，而是進(jìn)行一段隨機(jī)時間D的“關(guān)閉準(zhǔn)備時間”后再關(guān)閉；如果沒有顧客在“關(guān)閉準(zhǔn)備時間”內(nèi)到達(dá)，服務(wù)員就馬上進(jìn)行休假，直到系統(tǒng)中累計有N個顧客時又開始啟動服務(wù)臺進(jìn)行服務(wù)，且服務(wù)臺要進(jìn)行一段隨機(jī)時間U的“啟動準(zhǔn)備時間”才能開始工作，直至系統(tǒng)再次變空；

4）如果有顧客在“關(guān)閉準(zhǔn)備時間”D內(nèi)到達(dá)，那么，服務(wù)臺立即停止關(guān)閉準(zhǔn)備且不需要重新啟動，立即為顧客服務(wù)，直到系統(tǒng)再次變空而重新做關(guān)閉準(zhǔn)備；

5）顧客到達(dá)過程、服務(wù)臺服務(wù)過程、“關(guān)閉準(zhǔn)備時間”及“啟動準(zhǔn)備時間”是彼此獨立的；

6）在t=0時刻，如果系統(tǒng)是空的，則到達(dá)的第一個顧客立即被服務(wù)。即只有在服務(wù)臺繁忙一段時間后系統(tǒng)才實行帶啟動/關(guān)閉時間的N-策略休假機(jī)制，所得平穩(wěn)結(jié)果與此假設(shè)無關(guān)。

2 M/G/1排隊系統(tǒng)隊長的基本公式

在對本文模型進(jìn)行分析前，先引入經(jīng)典M/G/1 排隊系統(tǒng)的部分相關(guān)結(jié)果。首先，定義一些基本概念。忙期：從服務(wù)員開始為顧客服務(wù)的時刻起，直到系統(tǒng)再次變空為止這一段時間；閑期：從系統(tǒng)變空的時刻起，直到服務(wù)員再次開始為顧客服務(wù)為止這一段時間。令(j=0,1,2,…)表示平穩(wěn)狀態(tài)下隊長的概率分布，則[2]：

式（2）中：

g(λ)=當(dāng)j≤0時，規(guī)定表示忙期中系統(tǒng)穩(wěn)態(tài)隊長分布，ρ=λE[G]為交通強(qiáng)度。M/G/1排隊系統(tǒng)隊長的概率母函數(shù)為

3 模型分析

1）系統(tǒng)隊長的概率母函數(shù)。本文所研究的模型可看做是第2部分中經(jīng)典M/G/1排隊系統(tǒng)的一種推廣形式，模型中忙期的開始方式可歸納成以下情形。

情形1：在服務(wù)臺“關(guān)閉準(zhǔn)備時間”內(nèi)沒有顧客到達(dá)，其概率為D?(λ)。在這種情形下，服務(wù)員就馬上進(jìn)行休假，直到系統(tǒng)中累計有N個顧客時，又開始啟動服務(wù)臺進(jìn)行服務(wù)。忙期初始時，系統(tǒng)隊長的概率母函數(shù)為zNU?(λ-λz)，其中U?(s)是U的LS變換。

情形2：在服務(wù)臺“關(guān)閉準(zhǔn)備時間”內(nèi)有顧客到達(dá)，其概率為1-D?(λ)。在這種情形下，服務(wù)臺立即停止關(guān)閉準(zhǔn)備且不需要重新啟動，立即為顧客服務(wù)，此時開始的忙期初始時刻系統(tǒng)中只有1名顧客。

由已知隨機(jī)分解結(jié)果[3]，忙期初始時，系統(tǒng)隊長分布的概率母函數(shù)為

式中，U?(λ-λz)表示“啟動準(zhǔn)備時間”內(nèi)到達(dá)的顧客數(shù)的概率母函數(shù)。

由MEDHI和TEMPLETON推導(dǎo)出的結(jié)論[4]，帶啟動/關(guān)閉時間的N-策略M/G/1 排隊系統(tǒng)中隊長分布的概率母函數(shù)的隨機(jī)分解式仍然存在：式（5）中為閑期內(nèi)期望到達(dá)的顧客數(shù)。

2）系統(tǒng)隊長分布。首先，由系統(tǒng)附加隊長的概率母函數(shù)得到系統(tǒng)附加隊長分布。通過式（5）可以看出穩(wěn)態(tài)隊長分布可以看作是2 個隨機(jī)變量之和，其一是一般M/G/1排隊系統(tǒng)隊長，其二是由帶啟動/關(guān)閉時間的N-策略休假機(jī)制所引起的附加隊長分布。系統(tǒng)附加隊長的概率母函數(shù)為

由概率母函數(shù)定義，系統(tǒng)附加隊長概率分布為：

基于此，當(dāng)i＜N時，有：

當(dāng)i≥N時，有：

將式（8）及式（9）代入至式（7）中，可得系統(tǒng)附加隊長分布：

接下來，再研究系統(tǒng)隊長分布。顯然，由鏈?zhǔn)椒▌t，系統(tǒng)中有0名顧客（n=0）的概率為

當(dāng)n=1,2,…,N-1時，由Leibniz 公式，通過式（5）可得系統(tǒng)中有n名顧客的概率為

式（14）中，p0k由式（1）、（2）給出。令，再次利用鏈?zhǔn)椒▌t的推導(dǎo)過程，若n-k＜N，有

將式（15）代入式（14）并結(jié)合式（2），可得系統(tǒng)隊長分布：

當(dāng)n≥N時，我們討論以下情形。

若n-k≥N，即k≤n-N，有：

由式（15）及式（17）并結(jié)合式（2），可得系統(tǒng)隊長分布：

系統(tǒng)隊長分布表達(dá)式由式（13）、（16）及（18）給出，這些公式可以用于計算平穩(wěn)狀態(tài)下隊長的概率分布。

注：若本文所研究的系統(tǒng)中“啟動準(zhǔn)備時間”為0，即E[U]=0、U(0,λ)=1、U(k,λ)=1，此時系統(tǒng)簡化為具有延遲關(guān)閉時間的N-策略M/G/1排隊系統(tǒng)，簡化結(jié)論與文獻(xiàn)[2]中的結(jié)論一致，而本文所用方法較文獻(xiàn)[2]中全概率分解法簡便很多。

4 數(shù)值實驗

下面借助數(shù)值計算技術(shù)進(jìn)一步考察穩(wěn)態(tài)隊長分布的表達(dá)式。假設(shè)服務(wù)時間服從負(fù)指數(shù)分布且E[G]=1/μ，啟動時間服從3 階Erlang 分布且E[U]=3/β，關(guān)閉時間服從4 階Erlang分布且E[D]=4/γ，當(dāng)λ=1、μ=2、γ=2、N=5時，結(jié)果如表1所示。

表1 隊長分布

通過表1 可以看出，隨著β的增大，在其他參數(shù)固定的情況下，①系統(tǒng)變空的概率隨之增大；②系統(tǒng)隊長為n(n=1,2,…,N)的概率隨之增大；③系統(tǒng)隊長為n(n=N+1,N+2,…)的概率隨之減小。平均隊長（EL）隨著β的增大而減小。值得注意的是，實際中的排隊系統(tǒng)容量往往是有限的，工程設(shè)計中需要綜合考慮平均隊長和穩(wěn)態(tài)隊長分布，而僅僅以平均隊長作為依據(jù)，可能導(dǎo)致系統(tǒng)容量設(shè)計偏小。

[1] YADIN M，NAOR P.Queueing systems with a removable service station[J]. Operational Research Quarterly，1963，14（4）：393-405.

[2] 唐應(yīng)輝.延遲N-策略M/G/1 排隊系統(tǒng)隊長的瞬態(tài)和穩(wěn)態(tài)分布[J]. 系統(tǒng)工程理論與實踐，2007，27（11）：132-136.

TANG YINGHUI. The transient and equilibrium distributions of the queue-length for M/G/1 queue with delayed N-Policy[J]. Systems Engineering-Theory & Practice，2007，27（11）：132-136.（in Chinese）

[3] FUHRMANN S W，COOPER R B.Stochastic decompositions in the M/G/1 queue with generalized vacations[J].Operations Research，1985，33（5）：1117-1129.

[4] MEDHI J，TEMPLETON J G C. A poisson input queue under N-policy and with a general start up time[J]. Computers and Operations Research，1992，19（1）：35-41.

[5] 唐應(yīng)輝，劉燕.N-策略M/G/1 排隊系統(tǒng)隊長分布表達(dá)式[J].運籌與管理，2006，15（3）：40-50.

TANG YINGHUI，LIU YAN. The expression of the queue length distribution for M/G/1/∞queue with N-policy[J]. Operations Research and Management Science，2006，15（3）：44-50.（in Chinese）

[6] 馮建英，吳云江.帶關(guān)閉期的隨機(jī)N-策略的M/G/1排隊系統(tǒng)[J].工程數(shù)學(xué)學(xué)報，2009，26（3）：90-98.

FENG JIANYING，WU YUNJIANG. The M/G/1 queue under vacation policies with closedown time and the random N-policy[J]. Chinese Journal of Engineering Mathematics，2009，26（3）：90-98.（in Chinese）

[7] 羅海軍，朱翼雋.帶有負(fù)顧客的N 策略工作休假M/M/1排隊[J].運籌與管理，2010，19（1）：104-109.LUO HAIJUN，ZHU YIJUAN.The M/M/1 working vacation queue with negative customers and N-policy[J]. Operations Research and Management Science，2010，19（1）：104-109.（in Chinese）

[8] 唐應(yīng)輝，蒲會，余玅妙.帶啟動時間的N-策略M/G/1 排隊系統(tǒng)的隊長[J].系統(tǒng)工程理論與實踐，2011，31（1）：131-137.

TANG YINGHUI，PU HUI，YU MIAOMIAO. Queue size of M/G/1 queueing system with N-policy and set-up times[J]. Systems Engineering-Theory & Practice，2011，31（1）：131-137.（in Chinese）

[9] 劉名武，馬永開.啟動延遲N-策略批到達(dá)多重休假排隊[J].數(shù)學(xué)的實踐與認(rèn)識，2011，41（13）：137-144.

LIU MINGWU，MA YONGKAI. Batch-arrival queue with multiple vacations and delayed setup times under Npolicy[J]. Mathematics in Practice and Theory，2011，41（13）：137-144.（in Chinese）