具有相依變量成批到達排隊系統等待時間的注記

蔡南蓮

(集美大學理學院,福建廈門361021)

具有相依變量成批到達排隊系統等待時間的注記

蔡南蓮

(集美大學理學院,福建廈門361021)

研究了成批到達排隊系統G(X)/G/1的基本變量具有相依關系時,等待時間的隨機比較性質.證明了當到達批量與到達間隔的相依關系越強時,相應的等待時間越短;當服務時間和到達間隔的相依關系越強時,相應的等待時間越短.同時探討了基本變量相依時成批到達排隊系統的等待時間的界.

正象限相依;上模序;增凸序;Fr?chet界;成批到達排隊系統;等待時間

單個服務員的成批到達排隊系統G(X)/G/1是運籌學中很重要的數學模型.研究問題時通常假設基本變量之間是相互獨立的.如在文獻[1-2]中,研究了成批排隊系統M(X)/G(Y)/1的隊長的性質,當2個成批排隊系統M(X)/G(Y)/1的基本變量滿足隨機序(增凸序)關系時,得出了成批排隊系統的隊長也滿足隨機序(增凸序)關系;文獻[3]探討了成批到達排隊系統的顧客的等待時間的隨機比較性質,當2個這樣的系統的基本變量滿足一定隨機序、凸序關系時,得出了顧客的等待時間的隨機序、凸序關系性質.

在實際應用中,成批到達排隊系統G(X)/G/1的基本變量間的相互獨立性的假設常常有局限性.眾所周知,如果到達批量較大或者顧客的服務時間較長時,下一個顧客更可能會“知難而退”,在這種情況下,是顧客的到達批量與顧客的到達間隔有相依關系,顧客的服務時間與顧客的到達間隔也有相依關系的一個例子.因此,基本變量之間的相依關系對排隊系統的隊長、等待時間和忙期等排隊系統的重要指標的影響的研究具有實際意義和應用價值.近年來,對具有相依變量的排隊系統的研究日益得到重視.如在文獻[4]中,通過模擬得出,對于M/M/1排隊系統,顧客的等待時間隨著顧客的服務時間與顧客的到達時間的相關程度而下降;文獻[5]中,假設G/G/1排隊系統中顧客的服務時間與接下來的顧客到達時間有相依關系時,研究對G/G/1系統的等待時間的影響;Cai等[6]在文獻[1-2]的基礎上,探討了在成批排隊系統M(X)/ G(Y)/1(G(X)/M(Y)/1)中,當顧客的服務時間與顧客的服務批量(顧客的到達間隔與顧客的到達批量)之間有相依關系時,排隊系統的基本隨機變量滿足一定的隨機序關系時,排隊系統的隊長的隨機序性質.

本文考慮成批到達排隊系統G(X)/G/1,分別在(i)顧客的到達批量與顧客的到達間隔相依;(ii)顧客的服務時間與顧客的到達間隔相依兩種情形下,當系統的基本變量滿足一定的隨機序關系時,探討系統的等待時間的性質.該研究結果可看成是文獻[3]中考慮的基本變量獨立到基本變量相依的進一步結論,也可看成是文獻[5]中考慮的G/G/1系統到G(X)/G/1系統的補充.

1 隨機序、相依的概念及引理

首先回顧一下隨機序、相依的概念(有關更詳細的內容可參見文獻[7]),及要用到的一些引理.

定義1 (i)二維隨機向量X=(X1,X2)稱為PQD(positive quadrant dependence),如果對任意的x1,x2∈R,P(X1≤x1,X2≤x2)≥P(X1≤x1)P(X2≤x2).

(ii)設X=(X1,X2)和Y=(Y1,Y2)是二維隨機向量,稱X≤cY,如果對任意的x1,x2∈R,P(X1≤x1, X2≤x2)≤P(Y1≤x1,Y2≤x2).

定義2 (i)二元函數f(x,y)稱為上模的,如果對任意的x1,x2∈R,ε,δ＞0,有f(x1+ε,x2+δ)-f(x1+ε,x2)-f(x1,x2+δ)+f(x1,x2)≥0.

(ii)設X=(X1,X2)和Y=(Y1,Y2)是2個二維隨機向量,稱X依上模序小于Y(記為X≤smY),如果Ef(X)≤Ef(Y)對所有使得積分存在的上模函數均成立.

(iii)設X和Y是2個隨機變量,稱X依增凸序序小于Y(記為X≤icxY),如果Ef(X)≤Ef(Y)對所有使得積分存在的增凸函數均成立.

容易得出,當X=(X1,X2)和Y=(Y1,Y2)有相同的邊際分布時,下列命題成立:

(i)如果X是PQD且Y1與Y2獨立時,有Y≤cX.

(ii)設X≤cY,則X≤smY(見文獻[8]定理2.5).

下面介紹一些引理.

引理1[6]設Y1,Y2,ξi,i=1,2,…是非負的隨機變量,N,M是取正整值的隨機變量.如果(N,Y1)≤sm(M, Y2),則ξ1+…+ξM-Y2≤icxξ1+…+ξN-Y1.

(ii)設隨機變量X,Y滿足X≤icxY,且f(x)是增凸函數,則f(X)≤cf(Y).

引理3[5]設X=(X1,X2)和Y=(Y1,Y2)是二維隨機向量,X≤icxY,則Y1-Y2≤icxX1-X2.

引理4 設v1k,v2k(k=1,2,…),u1,u2是非負隨機變量,(v11,u1)≤sm(v21,u2),(v12,…,v1k)與(v22,…,v2k)同分布,(vi1,ui)與(vi2,…,vik)相互獨立,i= 1,2.則

因為(vi1,ui)與(vi2,…,vik)相互獨立,i=1,2,則對任意的上模函數f(x,y)和t2,…,tk≥0,由式(1)得:

由于(v12,…,v1k)與(v22,…,v2k)同分布,所以

此即(v11+v12+…+v1k,u1)≤sm(v21+v22+…+v2k, u2).

引理5[2]函數f(x)是實凸函數當且僅當對任意的實數a＞0,f(x+a)-f(x)關于x是增函數.

2 到達批量與到達間隔相依的情形

顧客的到達批量與顧客的到達間隔有相依關系的成批到達排隊模型G(X)/G/1描述如下:

(i)顧客在時刻0=t0,t1,t2,…到達,到達批量分別為X1,X2,X3,…,到達間隔時間為un=tn-tn-1.設(Xn,n≥1),(un,n≥1)分別是相互獨立同分布隨機變量序列,在時刻tn-1到達的顧客稱為第n批到達的顧客.

(ii)第n批到達的顧客隨機地接受服務,設第k個接受服務的顧客的服務時間為vnk,n=1,2,…,k= 1,2,…,Xn.設(vnk,n,k=1,2,…)相互獨立同分布.

(iii)設隨機向量序列{(Xn,un),n≥1}相互獨立同分布.即僅允許第n批的到達批量Xn與下一批顧客的到達間隔un有相依關系,但第n批的到達批量Xn與其他批的到達間隔uk(k≠n)是相互獨立的.

(iv)設隨機過程{(Xn,un),n≥1}與(vnk,n,k=1, 2,…)相互獨立.

滿足(i)～(iv)的成批到達排隊系統G(X)/G/1稱為具有特征[(Xn,un),vnk].

對于上面的模型,有下面的結論.

其中不等式成立利用了引理2.

從而

即

由式(2),(3)得

下面利用數學歸納法可以證明命題.

3 服務時間與到達間隔相依的情形

顧客的服務時間與顧客的到達間隔有相依關系的成批到達排隊模型G(X)/G/1.描述如下.

(i)顧客在時刻0=t0,t1,t2,…到達,到達批量分別為X1,X2,X3,…,到達間隔時間為un=tn-tn-1.設(Xn,n≥1),(un,n≥1)分別是相互獨立同分布隨機變量序列,在時刻tn-1到達的顧客稱為第n批到達的顧客.

(ii)第n批到達的顧客隨機地接受服務,設第k個接受服務的顧客的服務時間為vnk,n=1,2,…,k= 1,2,…,Xn.設(vnk,n,k=1,2,…)相互獨立同分布.

(iii)設隨機向量序列{(vn1,un),n≥1}相互獨立同分布.即僅允許第n批到達第一個接受服務的顧客的服務時間vn1與下一批顧客的到達間隔un有相依關系,但第n批到達第一個接受服務的顧客的服務時間vn1與其他批的到達間隔uk(k≠n)是相互獨立的.

(iv)設隨機過程{(vn1,un),n≥1},{Xn,n≥1}與(vnk,n≥1,k≥2)相互獨立.

滿足(i)～(iv)的成批到達排隊系統G(X)/G/1稱為具有特征[Xn,(vnk,un)].

令wn表示第n批到達第一個接受服務的顧客的等待時間,則有下列循環關系式:

對于上面的模型,有下面的結論.

利用引理3得:

接下來,可以證明下面的不等式:

利用數學歸納法可以證明余下的部分,與定理1類似,略去.

4 等待時間的界

利用定理1和定理2,可以得到到達批量與到達間隔相依,服務時間與到達間隔相依兩種情形下的成批到達排隊系統的顧客等待時間的界,下面給出例子.

例1 設Σ表示到達批量與到達間隔相依具有特征[(Xn,un),vnk]的成批到達排隊模型,wn表示第n批到達第一個接受服務的顧客的等待時間.設(Xn, un)具有聯合分布函數(二維Pareto分布[9]),

λ,α＞0,x1,x2＞0.

固定α＞0,則F(x1,x2,λ,α)關于λ單調下降.

即(Xn,un)在≤c序意義下關于λ單調下降.

所以利用定理1,wn在增凸序的意義下關于λ單調增加.

[1] Prabhu N U.Stochastic comparison for bulk queue[J]. Queueing System,1987(1):265-277.

[2] 蔡南蓮,肖必泉,鄭耀輝.成批排隊系統的隨機比較[J].運籌學雜志,1994,13(2):59-65.

[3] 蔡南蓮.成批到達排隊系統等待時間的隨機比較[J].廈門大學學報:自然科學版,1999,38(5):661-663

[4] Mitchell C R,Paulson A S.M/M/1-queues with inter-dependent arrival and service processes[J].Naval Research Logistics Quarterly,1979,40:467-475.

[5] Müller A.On the waiting times in queues with dependence between interarrival andservice times[J].Operations Research Letters,2000,26:43-47.

[6] Cai N,Zheng X.Increasing convex ordering of length queue in bulk queues[J].Operations Research Letters, 2008,36:123-126.

[7] Shaked M,Shanthikumar J G.Stochastic orders and their applications[M].New Xork:Academic Press,1994.

[8] Müller A.Some remarks on the supermodual order[J]. Journal of Multivariate Analysis,2000,73:107-119.

[9] Denuit M,Dhaene J,Goovaerts M,et al.Actuarial theory for dependence risks[M].New Xork:John Wiley,2005.

A Note on the Waiting Times for Bulk Arrival Queues with Dependent Variables

CAI Nan-lian
(School of Sciences,Jimei University,Xiamen 361021,China)

We consider single-server bulk arrivals queues G(X)/G/1 with the dependence between group sizes and inter-arrival times of customers and between service times and inter-arrival times,respectively.In these two cases,we show that stronger dependence between them leads to shorter waiting times in the increasing convex ordering sense.We also obtain bounds of waiting times in bulk arrival queues.

positive quadrant dependence;supermodular order;increasing convex order;Fr?chet bound;bulk arrivals queues;waiting time

10.6043/j.issn.0438-0479.2015.02.015

O 211.5

A

0438-0479(2015)02-0238-04

2014-03-10 錄用日期:2014-08-24

國家自然科學基金(11171278);集美大學黃慧貞學科建設基金

Email:cainanlan@163.com

蔡南蓮.具有相依變量成批到達排隊系統等待時間的注記[J].廈門大學學報:自然科學版,2015,54(2):238-241.

:Cai Nanlian.A note on the waiting times for bulk arrival queues with dependent variables[J].Journal of Xiamen University:Natural Science,2015,54(2):238-241.(in Chinese)