一類N-策略M/G/1排隊系統隊長分布

劉曉燕，孫璽菁，劉 丹

（海軍航空工程學院系統科學與數學研究所，山東煙臺264001）

自從YADIN 和NAOR[1]引入了N-策略以來，具有N-策略控制機制的排隊系統理論已取得了豐碩的成果[2-9]。排隊系統隊長的穩態概率分布在系統容量設計中有著重要的應用價值，而直接來求隊長的穩態分布是非常困難的。基于此，本文研究帶啟動/關閉時間的N-策略M/G/1排隊系統，提出了一種簡便有效的算法來推導穩態隊長概率分布的解析結果。

1 模型描述

本文研究的帶啟動/關閉時間的N-策略M/G/1 排隊系統模型描述如下：

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

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

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

4）如果有顧客在“關閉準備時間”D內到達，那么，服務臺立即停止關閉準備且不需要重新啟動，立即為顧客服務，直到系統再次變空而重新做關閉準備；

5）顧客到達過程、服務臺服務過程、“關閉準備時間”及“啟動準備時間”是彼此獨立的；

6）在t=0時刻，如果系統是空的，則到達的第一個顧客立即被服務。即只有在服務臺繁忙一段時間后系統才實行帶啟動/關閉時間的N-策略休假機制，所得平穩結果與此假設無關。

2 M/G/1排隊系統隊長的基本公式

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

式（2）中：

g(λ)=當j≤0時，規定表示忙期中系統穩態隊長分布，ρ=λE[G]為交通強度。M/G/1排隊系統隊長的概率母函數為

3 模型分析

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

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

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

由已知隨機分解結果[3]，忙期初始時，系統隊長分布的概率母函數為

式中，U?(λ-λz)表示“啟動準備時間”內到達的顧客數的概率母函數。

由MEDHI和TEMPLETON推導出的結論[4]，帶啟動/關閉時間的N-策略M/G/1 排隊系統中隊長分布的概率母函數的隨機分解式仍然存在：式（5）中為閑期內期望到達的顧客數。

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

由概率母函數定義，系統附加隊長概率分布為：

基于此，當i＜N時，有：

當i≥N時，有：

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

接下來，再研究系統隊長分布。顯然，由鏈式法則，系統中有0名顧客（n=0）的概率為

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

式（14）中，p0k由式（1）、（2）給出。令，再次利用鏈式法則的推導過程，若n-k＜N，有

將式（15）代入式（14）并結合式（2），可得系統隊長分布：

當n≥N時，我們討論以下情形。

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

由式（15）及式（17）并結合式（2），可得系統隊長分布：

系統隊長分布表達式由式（13）、（16）及（18）給出，這些公式可以用于計算平穩狀態下隊長的概率分布。

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

4 數值實驗

下面借助數值計算技術進一步考察穩態隊長分布的表達式。假設服務時間服從負指數分布且E[G]=1/μ，啟動時間服從3 階Erlang 分布且E[U]=3/β，關閉時間服從4 階Erlang分布且E[D]=4/γ，當λ=1、μ=2、γ=2、N=5時，結果如表1所示。

表1 隊長分布

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

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

[2] 唐應輝.延遲N-策略M/G/1 排隊系統隊長的瞬態和穩態分布[J]. 系統工程理論與實踐，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] 唐應輝，劉燕.N-策略M/G/1 排隊系統隊長分布表達式[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] 馮建英，吳云江.帶關閉期的隨機N-策略的M/G/1排隊系統[J].工程數學學報，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] 羅海軍，朱翼雋.帶有負顧客的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] 唐應輝，蒲會，余玅妙.帶啟動時間的N-策略M/G/1 排隊系統的隊長[J].系統工程理論與實踐，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-策略批到達多重休假排隊[J].數學的實踐與認識，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）