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

彭 懿

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

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

彭 懿

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

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

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

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

在過去三十年中, 很多學(xué)者致力于研究休假排隊系統(tǒng). 休假是指服務(wù)臺終止在隊列中服務(wù), 服務(wù)臺可能正在修復(fù), 或者是被迫停止服務(wù). 休假排隊系統(tǒng)已廣泛用于通信系統(tǒng), 計算機(jī)網(wǎng)絡(luò), 生產(chǎn)管理, 業(yè)務(wù)管理的性能分析等許多現(xiàn)實生活應(yīng)用中. 關(guān)于休假排隊系統(tǒng)的文獻(xiàn)參見Doshi[4], Takagi[5]以及Tian和Zhang[6]等. 在這些研究中, 通常假設(shè)服務(wù)器在休假期間停止服務(wù). 最近, 越來越多的學(xué)者感興趣于工作休假排隊系統(tǒng). 工作休假是指當(dāng)服務(wù)臺休假時并不完全停止服務(wù), 只是服務(wù)速度比正常工作時的服務(wù)速度要慢. Servi和Finn[7]首先研究了M/M/1工作休假排隊系統(tǒng). Wu和Takagi[8]將這項工作擴(kuò)展到多重工作休假的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). 其次, 當(dāng)其模型中的重試率趨于無窮時, 其穩(wěn)定性條件與離散時間Geo/Geo/1隊列的穩(wěn)定性條件不一致. 所以我們試圖重新探究具有工作休假的離散時間重試排隊系統(tǒng).

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

1 模型描述

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

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

2 模型求解及性能指標(biāo)分析

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

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

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

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

其中

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

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

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

(1)

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

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

(2)

3 平穩(wěn)分布

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

我們記轉(zhuǎn)移概率矩陣P對應(yīng)的平穩(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.

為了推導(dǎo)未知數(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)得到.

將以上結(jié)論總結(jié)為下述定理.

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

其中

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

推論1:

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

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

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

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

其中

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

其中

(6)服務(wù)臺忙的概率為

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

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

本刊編輯部

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

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

O122

A

1000-2537(2017)02-0089-06

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