具有相依變量成批到達(dá)排隊系統(tǒng)等待時間的注記

蔡南蓮

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

具有相依變量成批到達(dá)排隊系統(tǒng)等待時間的注記

蔡南蓮

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

研究了成批到達(dá)排隊系統(tǒng)G(X)/G/1的基本變量具有相依關(guān)系時,等待時間的隨機(jī)比較性質(zhì).證明了當(dāng)?shù)竭_(dá)批量與到達(dá)間隔的相依關(guān)系越強(qiáng)時,相應(yīng)的等待時間越短;當(dāng)服務(wù)時間和到達(dá)間隔的相依關(guān)系越強(qiáng)時,相應(yīng)的等待時間越短.同時探討了基本變量相依時成批到達(dá)排隊系統(tǒng)的等待時間的界.

正象限相依;上模序;增凸序;Fr?chet界;成批到達(dá)排隊系統(tǒng);等待時間

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

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

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

1 隨機(jī)序、相依的概念及引理

首先回顧一下隨機(jī)序、相依的概念(有關(guān)更詳細(xì)的內(nèi)容可參見文獻(xiàn)[7]),及要用到的一些引理.

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

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

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

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

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

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

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

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

下面介紹一些引理.

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

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

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

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

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

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

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

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

2 到達(dá)批量與到達(dá)間隔相依的情形

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

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

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

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

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

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

對于上面的模型,有下面的結(jié)論.

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

從而

即

由式(2),(3)得

下面利用數(shù)學(xué)歸納法可以證明命題.

3 服務(wù)時間與到達(dá)間隔相依的情形

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

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

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

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

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

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

令wn表示第n批到達(dá)第一個接受服務(wù)的顧客的等待時間,則有下列循環(huán)關(guān)系式:

對于上面的模型,有下面的結(jié)論.

利用引理3得:

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

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

4 等待時間的界

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

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

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

固定α＞0,則F(x1,x2,λ,α)關(guān)于λ單調(diào)下降.

即(Xn,un)在≤c序意義下關(guān)于λ單調(diào)下降.

所以利用定理1,wn在增凸序的意義下關(guān)于λ單調(diào)增加.

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

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

[3] 蔡南蓮.成批到達(dá)排隊系統(tǒng)等待時間的隨機(jī)比較[J].廈門大學(xué)學(xué)報:自然科學(xué)版,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

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

Email:cainanlan@163.com

蔡南蓮.具有相依變量成批到達(dá)排隊系統(tǒng)等待時間的注記[J].廈門大學(xué)學(xué)報:自然科學(xué)版,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)