甘 娜 黃裕鋒 陸曉梅

（廣東工程職業(yè)技術(shù)學院信息工程學院 廣州 510520）

1 引言

排隊系統(tǒng)在實際生活中非常普遍，如何提高排隊系統(tǒng)的服務性能，降低人力運營成本，對于排隊系統(tǒng)的優(yōu)化具有實際應用意義。目前，很多學者對休假和可修排隊模型進行了研究。參考文獻［1］提出一種以概率P進入和服務時間為Erlang分布的可修排隊模型，參考文獻［2］提出基于多重休假的min（N，V）-策略M/G/1排隊系統(tǒng)的隊長分布，參考文獻［3］提出了N策略帶啟動時間的Geom/Geom/1工作休假排隊。然而，很多研究學者主要關注的是休假或可修排隊模型，對多重休假策略和可修性質(zhì)相結(jié)合的排隊模型關注極少。

本文從排隊系統(tǒng)服務臺多重休假和可修的特點為改進方向，在Erlang排隊模型的基礎上，建立了空竭服務多重休假的GI/Gemo/C/∞可修排隊模型。對排隊系統(tǒng)服務過程進行仿真，仿真結(jié)果驗證了空竭服務多重休假的GI/Gemo/C/∞可修排隊系統(tǒng)的合理性及有效性，提高了服務臺利用率，減少了服務等待時間。

2 Erlang-A排隊模型及改進

2.1 Erlang-A排隊模型

Erlang-A的通用性需要四個參數(shù)：到達為固定速率λ的Poisson分布；服務服從服務率μ的指數(shù)分布；坐席數(shù)目C；顧客耐心等待時間1/θ，并假定其服從指數(shù)分布。Erlang-A對應的排隊模型為M/M/C/∞ 。系統(tǒng)的負載為 α=λ/μ ，如果 α≥C ，則系統(tǒng)超過系統(tǒng)的處理能力，出現(xiàn)無窮排隊，顧客的等待時間趨向于無窮大。一般主要分析在α＜C的狀態(tài)下，排隊等待時間的分布情況［4～6］。

在所需的各種經(jīng)驗參數(shù)都很準確、且滿足到達、服務持續(xù)時間符合前提分布的情況下，Er?lang-A模型對系統(tǒng)性能參數(shù)的估計較精確。但Er?lang-A模型考慮了客戶的等待時間問題，但并不能完全解決客戶的滿意度問題，僅僅適合輕負載排隊系統(tǒng)性能分析［7～8］?；诖耍槍υ撃Ｐ偷娜毕葸M行改進，建立一種新排隊模型來彌補它的不足。

2.2 改進的Erlang-A排隊模型

為了提高客戶的滿意度，不僅要考慮客戶的等待時間問題，還要考慮服務臺人員的排班問題，例如：服務臺休假、服務臺修理問題，降低服務成本?；谏鲜鲆蛩氐目紤]，本文在Erlang-A排隊模型的基礎上，考慮到服務時間為離散事件，將排隊系統(tǒng)服務時間分布推廣為離散型概率分布幾何分布［9～11］，并引入多重休假策略、可修性質(zhì)，建立了一個空竭服務多重休假的GI/Gemo/C/∞可修排隊模型。

假設到達間隔、服務時間、休假時間相互獨立；顧客的到達間隔時間是相互獨立同分布的正整值隨機變量；顧客實際所需的服務時間相互獨立并服從幾何分布；服務臺具有空竭服務的多重休假規(guī)則；系統(tǒng)中有C個服務臺，使用FIFO排隊規(guī)則。為了使休假期間內(nèi)發(fā)生的顧客到達時刻具有Markov性質(zhì)，假設休假時間V服從幾何分布：

P{V=j}= θθˉj-1，j≥ 1，0＜ θ ＜ 1， θˉ=1- θ

約定休假的開始和結(jié)束都發(fā)生在時隙末端，C個并行的服務臺，系統(tǒng)中有無限的等待場所，休假期間服務臺完全停止對顧客的服務。

空竭服務多重休假的GI/Gemo/C/∞可修排隊系統(tǒng)具體的描述如下：

1）顧客在時刻 t1，t2，… 分別以批量 ξ1，ξ2，… 成批陸續(xù)到來，到達時間間隔τn=tn+1-tn，(n=1，2，…)獨立同分布隨機變量，分布函數(shù)為F(t)=p{τn≤t}，t＞0，n≥1，而且平均到達時間間隔有 0＜1/λ=tdF(t)＜+∞ 。顧客到達間隔是相互獨立同分布的正整值的隨機變量，記為T，有概率分布和PGF：

2）批量 ξn，n≥1為取正整數(shù)值的i.i.d隨機變量 ，設 P(ξn=i)=bi，n≥1，i=1，2，… ，均 值 為bˉ?Eξi＜+∞，i=1，2，…n ；

3）第n批到來的顧客中第k個顧客接受服務系 統(tǒng) 的 服 務 時 間 為 Vnk，k=1，2，…，ξn且(Vnk，n=1，2，…，k=1，2，…，ξn)為i.i.d隨機變量序列，分布函數(shù)為G(t)=P{Vnk≤t}，t≥0，n≥1，且令平均服務時間有 0＜α=tdG(t)＜+∞（即每位顧客的服務時間獨立同分布G(t)。顧客服務時間S1相互獨立并服從幾何分布

4）服務規(guī)則為先到先服務，且同批到達顧客的服務次序是任意的。一個話務員，每次只服務一個顧客；

5）假定服務臺的休假時間序列{Vi，i≥1}相互獨立、服從相同任意分布V(t)，并且獨立于到達和服務過程；

6）服務臺可修，服務臺的壽命長度X服從分布 X(t)=1-e-at，t≥0。服務臺失效后的修理時間Y服從一般分布Y(t)=P{Y≤t}，t≥0，而且平均修理時間為 0＜β=tdY(t)＜+∞。進一步假定服務臺在空閑時間不會失效；當服務臺失效時，正在接受服務的顧客需等待其修復后再繼續(xù)接受服務，已服務過的時間仍然有效，即累積計算；服務臺修復如新，并能立即投入使用；

7）到達間隔τn，各個顧客服務時間Vnk，到達批量ξn及失效后的修理時間Y均相互獨立。

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

3.1 排隊系統(tǒng)性能指標

設系統(tǒng)交通強度 ρ=(cμE(T))-1＜1，L-表示的穩(wěn)態(tài)極限，稱為該排隊系統(tǒng)到達前夕的穩(wěn)態(tài)隊長。穩(wěn)態(tài)分布記為

實際上，空竭服務多重休假的GI/Gemo/C/∞可修排隊系統(tǒng)的這些指標與無休假的M/M/C/∞系統(tǒng)相同，于是有：

穩(wěn)態(tài)下時刻n+處的隊長L+，可得到穩(wěn)態(tài)隊長L+的PGF：

定理1ρ＜1時，M/M/C/∞排隊系統(tǒng)中穩(wěn)態(tài)等待時間有PGF：

證明 如果穩(wěn)態(tài)下到達的顧客遇狀態(tài) j(≥c)，其等待時間大于k意味著c個服務臺都工作，k個時隙上完成服務不超過 j-c個。因此，

容易得出式（2）。得證。

由定理1可知，對于空竭服務多重休假的GI/Gemo/C/∞可修排隊系統(tǒng)穩(wěn)態(tài)下的平均等待時間，有

3.2 服務臺可靠性指標

1）系統(tǒng)的可用度

定義服務臺可用度為服務臺處于服務期（非休假和故障）的概率。由模型的假設及忙期的定義，在一個忙期內(nèi)，服務臺依次處于“完好工作”和“失效修理”兩種狀態(tài)。

對t≥0，令

Ai(t)=P{時刻t處于服務員忙期|N(0)=i}，

其中N(0)表示t=0系統(tǒng)中的顧客數(shù)。

定理2 對復變量s的實部?(s)≥0，有

而且平穩(wěn)結(jié)果

在空竭服務多重休假的GI/Gemo/C/∞可修排隊系統(tǒng)中，對?(s)＞0，服務臺的瞬態(tài)可用度的L變換為

2）系統(tǒng)的故障頻度

系統(tǒng)在單位時間內(nèi)的故障次數(shù)，即故障頻度，也是我們所關心的重要可靠性指標，它反映了系統(tǒng)的優(yōu)劣。

定理3 對?(s)＞0，服務臺(0，t]內(nèi)平均失效次數(shù)的LS變換為

對于空竭服務多重休假的GI/Gemo/C/∞可修排隊系統(tǒng)，由定理3可知：

長期單位時間內(nèi)的平均失效次數(shù)為

4 數(shù)值實驗結(jié)果和圖形分析

本文通過Matlab平臺對基于空竭服務多重休假的GI/Gemo/C/∞可修排隊模型的排隊系統(tǒng)建模，輸入?yún)?shù)有如下設定：每個時隙顧客到達概率為0.1～0.9；每個時隙服務完成概率為0.1～0.5；服務臺個數(shù)為1～32。根據(jù)第3.1節(jié)和第3.2節(jié)得到的穩(wěn)態(tài)指標均值的概率表達式及排隊系統(tǒng)的性能分析指標，通過數(shù)值例子分析出系統(tǒng)參數(shù)對系統(tǒng)性能指標的影響，可以得出各種相關的性能指標變化曲線。

圖1 平均等待時間隨服務率變化的曲線

圖2 平均隊長隨服務率變化的曲線

圖3 系統(tǒng)交通強度隨平均到達間隔變化的曲線1

圖4 系統(tǒng)交通強度隨平均到達間隔變化的曲線2

從圖1～圖6中可以得出下列規(guī)律：圖1和圖2說明隨著服務率的增大，平均等待時間和平均隊長逐漸減小，并且平均等待時間和平均隊長隨著服務臺個數(shù)的增多而減小。圖3說明在服務率不變的前提下，系統(tǒng)交通強度隨著服務臺個數(shù)的增多、平均到達間隔的增大而減小。圖4說明在服務臺個數(shù)不變的前提下，系統(tǒng)交通強度隨著服務率和平均到達間隔的增大而減小。圖5說明在服務臺個數(shù)不變的前提下，系統(tǒng)不可用度隨著到達率和系統(tǒng)交通強度的增大而增大。圖6說明服務臺平均失效次數(shù)隨著到達率和系統(tǒng)交通強度的增大而增大。

圖5 系統(tǒng)不可用度隨系統(tǒng)交通強度變化的曲線

圖6 系統(tǒng)平均失效次數(shù)隨系統(tǒng)交通強度變化的曲線

5 結(jié)語

本文針對傳統(tǒng)Erlang排隊模型在重負載的條件下服務持續(xù)時間不能服從指數(shù)分布的問題，提出了基于空竭服務多重休假的GI/Gemo/C/∞可修排隊模型，利用嵌入馬爾可夫鏈理論方法研究基于空竭服務多重休假的GI/Gemo/C/∞可修排隊模型，得到了排隊模型的平穩(wěn)分布及相關性能指標。結(jié)合數(shù)值例子，獲得了該模型在排隊應用中的相關指標及各個性能指標之間的關系；根據(jù)得出的實驗結(jié)果，驗證了改進的排隊模型的合理性，該模型既提高排隊系統(tǒng)客戶滿意度，又降低了服務成本。

［1］譚秀輝.以概率P進入和服務時間為Erlang分布的可修排 隊 模 型［J］.科 學 技 術(shù) 與 工 程 ，2010，10（5）：1204-1205.

TAN Xiuhui.A repairable queueing model with probabili?ty P and Erlang distribution［J］.Science Technology and Engineering，2010，10（5）：1204-1205.

［2］唐應輝，吳文青，劉云頗，等.基于多重休假的min（N，V）-策略M/G/1排隊系統(tǒng)的隊長分布［J］.系統(tǒng)工程理論與實踐，2013，36（4）：1533-1534.

TANG Yinghui，WU Wenqing，LIU Yunpo，et al.Queue length distribution of M/G/1 queueing system with min（N，V）-policy based on multiple server vacations［J］.Systems Engineering Theory&Practice，2013，36（4）：1533-1534.

［3］朱翼雋，潘小春，胡彬.N策略帶啟動時間的Geom/Geom/1工作休假排隊［J］.應用數(shù)學與計算數(shù)學學報，2010，24（1）：26-27.

ZHU Yijun，PAN Xiaochun，HU Bin.Geom/Geom/1 Queue with Working Vacations and N-policy and Set-up Time［J］.Comm.on Appl.Math.and Comput，2010，24（1）：26-27.

［4］C G Park，D H Han.Comparison of loss formulas for a cir?cuit group with overflow traffic［J］.Journal of Applied Mathematics and Informatics，2012，30（1-2）：135-145.

［5］孫健，丁日佳，陳艷艷.M/M/c型與M/M/1型排隊系統(tǒng)對比仿真［J］.北京工業(yè)大學學報，2016，42（9）：1325.

SUN Jian，DING Rijia，CHEN Yanyan.Comparative Simu?lation on M/M/c and M/M/1 Queuing Systems［J］.Journal Of Beijing University of Technology，2016，42（9）：1325.

［6］G_Choudhury.An M/G/l Queue with Two Phases of Ser?vice Subject to the Server Breakdown and Delayed Repair［J］.Applied Mathematical Modeling，2009，16（33）：2699-2709.

［7］李惠.M/M/2排隊系統(tǒng)的閥值和休假策略的研究［D］.秦皇島：燕山大學，2015.

LI Hui.Research on M/M/2 Queueing System With Threshold And Vacation Policies［D］.Qinhuangdao：Yan?shan University，2015.

［8］Jishen Jia，Shaomin Wu.A replacement policy for a repair?able system with its repairman having multiple vacations［J］.Applied Mathematics and Computation，2011，21（217）：4994-4998.

［9］任鵬月.帶啟動—關閉期、多重工作休假的離散時間Geom/Geom/1排隊模型［D］.長沙：中南大學，2014.

REN Pengyue.A discrete time Geom/Geom/1 queue mod?elwith multipleworking vacation and set-up and closed-down period［D］.Changsha：Central South Univer?sity，2014.

［10］Lee D H，Yang W S.The N-policy of a discrete time Geo/G/1 queue with disasters and its application to wire?less senor networks［J］.Applied Mathematical Model?ling，2013，37（23）：972-976.

［11］Wang J T，Huang Y B，Tien V D.A single server dis?crete time queue with correlated positive and negative customer arrivals［J］.Applied Mathematical Modelling，2013，39（9）：332-361.