具有多重休假策略和可修性質(zhì)GI/Gemo/C/∞排隊(duì)模型?

甘 娜 黃裕鋒 陸曉梅

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

1 引言

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

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

2 Erlang-A排隊(duì)模型及改進(jìn)

2.1 Erlang-A排隊(duì)模型

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

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

2.2 改進(jìn)的Erlang-A排隊(duì)模型

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 排隊(duì)系統(tǒng)性能指標(biāo)

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

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

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

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

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

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

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

3.2 服務(wù)臺可靠性指標(biāo)

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

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

對t≥0，令

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 平均隊(duì)長隨服務(wù)率變化的曲線

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

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

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

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

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

5 結(jié)語

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

［1］譚秀輝.以概率P進(jìn)入和服務(wù)時間為Erlang分布的可修排 隊(duì) 模 型［J］.科 學(xué) 技 術(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］唐應(yīng)輝，吳文青，劉云頗，等.基于多重休假的min（N，V）-策略M/G/1排隊(duì)系統(tǒng)的隊(duì)長分布［J］.系統(tǒng)工程理論與實(shí)踐，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工作休假排隊(duì)［J］.應(yīng)用數(shù)學(xué)與計算數(shù)學(xué)學(xué)報，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型排隊(duì)系統(tǒng)對比仿真［J］.北京工業(yè)大學(xué)學(xué)報，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排隊(duì)系統(tǒng)的閥值和休假策略的研究［D］.秦皇島：燕山大學(xué)，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］任鵬月.帶啟動—關(guān)閉期、多重工作休假的離散時間Geom/Geom/1排隊(duì)模型［D］.長沙：中南大學(xué)，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.