彭 懿

(長沙師范學院初等教育系，中國 長沙 410100)

具有工作休假的離散時間Geo/Geo/1重試排隊系統(tǒng)

彭 懿

(長沙師范學院初等教育系，中國 長沙 410100)

研究了具有工作休假的離散時間Geo/Geo/1重試排隊系統(tǒng). 服務臺具有工作休假模式，休假時間服從幾何分布并且不能被打斷. 分析了此排隊系統(tǒng)的馬氏鏈, 得到了系統(tǒng)穩(wěn)態(tài)存在的充要條件. 利用系統(tǒng)演化的平衡方程組求出了重試組隊長和服務臺狀態(tài)的聯(lián)合平穩(wěn)分布. 最后利用重試組隊長的概率母函數(shù), 進一步得到了一系列重要的排隊性能指標.

離散時間重試排隊系統(tǒng)；工作休假；擬生滅過程

近年來, 越來越多的文獻探究了重試排隊系統(tǒng), 特別是連續(xù)時間重試排隊系統(tǒng). 重試排隊系統(tǒng)是指顧客到達系統(tǒng)時, 若發(fā)現(xiàn)服務臺空閑則立即接受服務; 若發(fā)現(xiàn)服務臺忙但有空的等待位置, 則按某種排隊規(guī)則在隊列中等待服務; 若發(fā)現(xiàn)服務臺忙且所有的等待位置均被占據(jù), 則進入重試組不斷重試直到成功接受服務. 重試排隊系統(tǒng)廣泛應用于電話交換系統(tǒng), 通信網(wǎng)絡以及計算機網(wǎng)絡等領域. 電話訂票系統(tǒng)和網(wǎng)上訂票系統(tǒng)都可理解為重試排隊系統(tǒng), 包括無線網(wǎng)絡的計算機和具有以太網(wǎng)類協(xié)議的局域網(wǎng). 有關重試排隊系統(tǒng)的主要研究方法和成果, 有Yang和Templeton[1], Falin[2]以及Falin和Templeton等[3]. 目前重試排隊系統(tǒng)的研究主要集中于連續(xù)時間的情形. 然而, 在一些應用中, 離散時間重試排隊系統(tǒng)比連續(xù)時間重試排隊系統(tǒng)更加適合模擬計算機通訊系統(tǒng)和電信系統(tǒng). 這是因為在許多通信系統(tǒng)中, 時間被劃分為可作為一個時間單位的時隙. 例如, 在ATM網(wǎng)絡中, 每個單元具有固定的大小和服務時間. 系統(tǒng)從一個狀態(tài)轉換到另一個狀態(tài)只發(fā)生在時隙的開始或結束. 盡管離散時間重試排隊系統(tǒng)十分重要, 關于這方面的研究工作卻很少.

在過去三十年中, 很多學者致力于研究休假排隊系統(tǒng). 休假是指服務臺終止在隊列中服務, 服務臺可能正在修復, 或者是被迫停止服務. 休假排隊系統(tǒng)已廣泛用于通信系統(tǒng), 計算機網(wǎng)絡, 生產(chǎn)管理, 業(yè)務管理的性能分析等許多現(xiàn)實生活應用中. 關于休假排隊系統(tǒng)的文獻參見Doshi[4], Takagi[5]以及Tian和Zhang[6]等. 在這些研究中, 通常假設服務器在休假期間停止服務. 最近, 越來越多的學者感興趣于工作休假排隊系統(tǒng). 工作休假是指當服務臺休假時并不完全停止服務, 只是服務速度比正常工作時的服務速度要慢. Servi和Finn[7]首先研究了M/M/1工作休假排隊系統(tǒng). Wu和Takagi[8]將這項工作擴展到多重工作休假的M/G/1排隊系統(tǒng). Baba[9]考慮了具有多重工作休假的GI/M/1隊列. Li[10]分析了具有工作休假的GI / Geo / 1離散時間排隊系統(tǒng). Tian 等[11]研究了具有多重工作休假的Geo/Geo/1離散時間排隊系統(tǒng). Li[12]分析了指數(shù)工作休假的M/G/1排隊系統(tǒng). Chae[13]探究了單重工作休假的GI/M/1隊列和GI/Geo/1排隊系統(tǒng). Goswami和Selvaraju[14]研究了多重工作休假的MAP/PH/1離散時間排隊系統(tǒng). Do[15]考慮了工作休假的M/M/1重試排隊系統(tǒng). Li等[16]研究了具有工作休假且休假可被打斷的離散時間Geo/Geo/1重試排隊系統(tǒng). 然而, 他們的模型并不能包含具有工作休假且休假不能被打斷的離散時間重試排隊系統(tǒng). 其次, 當其模型中的重試率趨于無窮時, 其穩(wěn)定性條件與離散時間Geo/Geo/1隊列的穩(wěn)定性條件不一致. 所以我們試圖重新探究具有工作休假的離散時間重試排隊系統(tǒng).

本文重新探究具有多重工作休假的離散時間Geo/Geo/1重試排隊系統(tǒng), 得到一系列非常重要的排隊性能指標. 本文的研究主要應用于無線網(wǎng)絡中的媒體訪問控制功能的性能分析[17].

1 模型描述

考慮一個單服務臺的離散時間重試排隊系統(tǒng), 系統(tǒng)時間軸被分割成等長的時隙. 離散時間重試排隊系統(tǒng)中的所有事件都只能發(fā)生在時隙的分點處. 時間軸被分割為0,1,…,m,…. 假設顧客的離開只能位于時隙(m-,m)處, 顧客的到達和重試點依次只能在時隙首端(m,m+)處. 休假的開始和結束也只能發(fā)生在時隙m+處. 這里m-表示時刻前一瞬間,m+表示時刻m后一瞬間. 即本文考慮的是早到系統(tǒng)(EAS)情形. EAS的相關概念參見Hunter[18].

顧客的到達服從參數(shù)為p的Bernoulli過程. 服務臺前無等待位置, 因此, 若顧客到達系統(tǒng)時發(fā)現(xiàn)服務臺空閑則立即開始服務, 否則, 按先到先服務規(guī)則進入重試組, 即只有隊首的顧客允許重試. 重試時間服從參數(shù)為δ的幾何分布. 當某次服務結束時, 重試組中若無顧客,服務臺開始一個工作休假, 休假時間服從參數(shù)為θ的幾何分布, 即在任意一個時隙末端, 系統(tǒng)以概率θ結束工作休假. 在服務臺正常工作期間和工作休假期間服務時間分別服從參數(shù)為μb和μv(μv<μb)的幾何分布. 一個工作休假結束時, 若系統(tǒng)中有顧客等待, 則結束工作休假進入正常工作狀態(tài), 即服務率由μv轉為μb; 否則繼續(xù)開始一個新的工作休假.

2 模型求解及性能指標分析

在時刻m+, 令Nm表示重試組中的顧客數(shù), 并記服務臺的狀態(tài)變量為Jm.Jm=0表示服務臺處于工作休假和閑期;Jm=1表示服務臺處于工作休假和忙期;Jm=2表示服務臺處于閑期且不在工作休假;Jm=3表示服務臺處于忙期且不在工作休假. 易知, 馬氏鏈Ψ={(Nm,Jm),m≥1}是一個離散時間擬生滅過程, 其狀態(tài)空間為

Ω={(i,j):i≥0,j=0,1,3;(i,2):i≥1}.

以下的主要工作是求馬爾可夫鏈Ψ的平穩(wěn)分布

將狀態(tài)空間按照字典順序排序, 得到QBD過程的轉移概率矩陣P為

其中

此排隊系統(tǒng)的穩(wěn)態(tài)存在條件由以下定理給出

證 顯然此QBD過程不可約. 矩陣A=A0+A1+A2為

則矩陣A是不可約的隨機矩陣. 根據(jù)文獻[19]中定理7.3.1此QBD過程Ψ是正常返的當且僅當

(1)

其中ν=νC1,νe=1,e表示所有分量為1的一列向量. 這里

經(jīng)過一系列復雜的代數(shù)運算, 得到

(2)

3 平穩(wěn)分布

這一節(jié)，通過求解系統(tǒng)穩(wěn)態(tài)分布的Kolmogorov方程推導出重試組隊長的概率母函數(shù)和一系列重要的排隊性能指標. 利用快速Fourier變換方法，可以計算重試組隊長穩(wěn)態(tài)分布的各階矩.

我們記轉移概率矩陣P對應的平穩(wěn)向量為Π=(Π0,Π1,…), 其中Π0=(π0,0,π0,1,π0,3),Πk(πk,0πk,1,πk,2,πk,3),k≥1. 系統(tǒng)演化的平衡方程如下

Π0B00+Π1B10=Π0,

Π0B01+Π1A1+Π2A2=Π1,

Πk-1A0+ΠkA1+Πk+1A2=Πk,k≥2.

因此, 描述系統(tǒng)平穩(wěn)分布的Kolmogorov方程為：

(3)

(4)

(5)

(6)

(7)

其中δi,j為Kronecker記號, 其歸一化條件為

(8)

為求解方程(3)～(8), 引入如下概率母函數(shù)：

將方程(4)～(7)左右兩邊同乘zk，然后對k求和，得到

(9)

(10)

(11)

(12)

其中

由(9)和(10), 得到母函數(shù)φ1(z)和φ0(z)為

(13)

(14)

由(11)和(12), 得到母函數(shù)φ3(z)和φ2(z)為

(15)

(16)

其中

Λ=π0,0θ+π0,1θμv+π0,3μb.

為了推導未知數(shù)π0,0,π0,1和π0,3, 需要下述引理.

所以函數(shù)f(z)區(qū)間[0,1]恰好有一個根. 證畢.

根據(jù)引理1,φ1(z)的分母在點z0處等于零. 而φ1(z)在|z|≤1是解析的, 所以有

或

(17)

將(17)代入(3), 得到

(18)

將(17)和(18)代入(13)～(16)知道如φ0(z),φ1(z),φ2(z)和φ3(z)只依賴于未知數(shù)π0,0. 最后,π0,0可由歸一化條件(8)得到.

將以上結論總結為下述定理.

定理1 QBD過程Ψ的平穩(wěn)分布具有以下母函數(shù)

其中

下述推論給出此排隊系統(tǒng)穩(wěn)態(tài)時的一些性能指標.

推論1:

(1)系統(tǒng)空的概率為

(2)服務臺空閑且處于工作休假狀態(tài)的概率為

(3)服務臺忙且處于工作休假狀態(tài)的概率為

(4)服務臺空閑且處于正常工作狀態(tài)的概率為

其中

(5)服務臺忙且處于正常工作狀態(tài)的概率為

其中

(6)服務臺忙的概率為

(7)服務臺空閑的概率為

PI=φ0(1)+φ2(1)=1-Pb=

(8)重試組平均隊長為

[1] YANG T, TEMPLETON J. A survey on retrial queues[J]. Queueing Syst, 1987,2(3):201-233.

[2] FALIN G. A survey of retrial queues[J]. Queueing Syst, 1990,7(2):127-167.

[3] FALIN G, TEMPLETON J. Retrial queues[M]. London: Chapman & Hall, 1997.

[4] DOSHI B. Queueing systems with vacations: a survey[J]. Queueing Syst, 1986,1(1):29-66.

[5] TAKAGI H. Queueing Analysis: a foundation of performance evaluation, Vacation and Priority Systems, Part I.[M]. Amsterdam: North-Holland, 1991.

[6] TIAN N, ZHANG Z. Vacation queueing models—theory and applications[M]. New York: Springer Science, 2006.

[7] SERVI L, FINN S. M/M/1 queue with working vacations (M/M/1/WV) [J]. Perf Eval, 2002,50(1):41-52.

[8] WU D, TAKAGI H. M/G/1 queue with multiple working vacations[J]. Perf Eval, 2006,63(7):654-681.

[9] BABA Y. Analysis of a GI/M/1 queue with multiple working vacations[J]. Oper Res Lett, 2005,33(2):201-209.

[10] LI J, TIAN N, LIU W. Discrete-time GI/Geom/1 queue with multiple working vacations[J]. Queueing Syst, 2007,56(1):53-63.

[11] TIAN N, MA Z, LIU M. The discrete time Geom/Geom/1 queue with multiple working vacations[J]. Appl Math Model, 2007,32(12):2941-2953.

[12] LI J, TIAN N, ZHANG Z,etal. Analysis of the M/G/1 queue with exponentially working vacations-a matrix analytic approach[J]. Queueing Syst, 2009,61(1):139-166.

[13] CHAE K, LIM D, YANG W. The GI/M/1 queue and the GI/Geo/1 queue both with single working vacation[J]. Perf Eval, 2009,66(2):356-367.

[14] GOSWAMI C, SELVARAJU N. The discrete-time MAP/PH/1 queue with multiple working vacations[J]. Appl Math Model, 2010,34(4):931-946.

[15] DO T. M/M/1 retrial queue with working vacations[J]. Acta Inform, 2010,47(1):67-75.

[16] LI T, WANG Z, LIU Z. Geo/Geo/1 retrial queue with working vacations and vacation interruption[J]. J Appl Math Comput, 2012,39(1):131-143.

[17] ARORA A, JIN F, SAHIN G,etal. Throughput analysis in wireless networks with multiple users and multiple channels[J]. Acta Inform, 2006,43(1):147-164.

[18] HUNTER J. Mathematical techniques of applied probability, vol. 2, discrete-time models: techniques and applications[M]. New York: Academic Press, 1983.

[19] LATOUCHE G, RAMASWAMI V. Introduction to matrix analytic methods in stochastic modeling[M]. Alexandria: ASA-SIAM Series on Applied Probability, 1999.

[20] ATENCIA I, MORENO P. A discrete-time Geo/G/1 retrial queue with general retrial times[J]. Queueing Syst, 2004,48(1):5-21.

(編輯 CXM)

重要啟事

“優(yōu)先數(shù)字出版”是以紙質(zhì)版期刊錄用稿件為出版內(nèi)容，先于紙質(zhì)期刊出版日期出版的數(shù)字期刊出版方式．我刊已于2012年起與中國學術期刊(光盤版)電子雜志社簽訂了優(yōu)先數(shù)字出版協(xié)議．凡被我刊錄用的稿件一經(jīng)優(yōu)先數(shù)字出版，讀者即可在中國知網(wǎng)(CNKI)全文數(shù)據(jù)庫進行檢索和下載．凡向本刊投稿的作者，如無特別申明，均被視為作者授權本刊編輯部在紙質(zhì)期刊出版前，可以在中國學術期刊(光盤版)電子雜志社主辦的“中國知網(wǎng)”(www.cnki.net)上優(yōu)先數(shù)字出版；也被視為作者同意并授權我刊與其他電子雜志社簽訂的協(xié)議，并許可其在全球范圍內(nèi)使用該文的信息網(wǎng)絡傳播權、數(shù)字化復制權、數(shù)字化匯編權、發(fā)行權及翻譯權，并不再額外支付稿酬．

本刊編輯部

The Discrete-Time Geo/Geo/1 Retrial Queue with Working Vacations

PENGYi*

(Junior Education Department, Changsha Normal University, Changsha 410100, China)

The classical Geo/Geo/1 retrial queue with working vacations was studied, where working vacations are geometric distributed and cannot be interrupted. The Markov chain underlying the considered queueing system was analyzed and its stability condition was derived. Using the balance equations, the steady-state joint distribution of the number of customers in the obit and the states of the server was obtained. Furthermore, the generating functions of the number of customers in the orbit was found and some performance measures of the system in the steady-state was presented.

discrete-time retrial queues; working vacations; QBD

10.7612/j.issn.1000-2537.2017.02.015

2017-01-07

國家自然科學基金數(shù)學天元基金資助項目(11626045)；湖南省自然科學基金資助項目(2016JJ6001)；湖南省教育廳資助科研項目(15C0100)

O122

A

1000-2537(2017)02-0089-06

*通訊作者,E-mail：pengyiqueue@163.com