Queue Length Distribution for Geo/G/1 Queue with θ-Entering Discipline During Multiple Adaptive Vacations

WEI Yingyuan(魏瑛源),TANG Yinghui (唐应辉),YU Miaomiao(余玅妙)

(1.School of Mathematics & Statistics,Hexi University,Zhangye 734000,China;2.School of Mathematics & Software Science,Sichuan Normal University,Chengdu 610066,China; 3.Sichuan University of Science & Engineering,Zigong 643000,China)

Abstract: This paper considers a discrete time Geo/G/1 queue with multiple adaptive vacations where the customers who arrive during server vacations enter the system with probability θ (0 < θ ≤1).Using renewal process theory and total probability decomposition technique,from the beginning of arbitrary initial state,the z-transform recursive expressions of the transient queue length distribution at time epoch n+ are obtained.Based on the transient analysis,the explicit recursive formulae of the steady state queue length distribution at time epochs n−,n and n+ are derived,respectively.Furthermore,the results obtained in this paper indicate that the equilibrium queue length distribution no longer follows the stochastic decomposition structure.Finally,numerical results are offered to discuss the sensitivity of the steady state queue length distribution towards system parameters,and illustrate the significant application value of the recursive formulae for the steady state queue length distribution in the system capacity optimum design.

Key words: Discrete time Geo/G/1 queue; Multiple adaptive vacation; θ-entering discipline; Queue length distribution; Total probability decomposition technique; System capacity optimum design

1.Introduction

During the past decade,discrete time queues with vacations have been widely used in the performance analysis of communication systems.[1−3]

In the classical queueing systems with vacations the authors often assume that the customer input rate is fixed.However,the truth was quite different.TANG and MAO[4]introduced a kind ofp-entering discipline:The arriving customers directly enter the system when they find the server does not take vacations.While,they enter the system with probabilityp(0< p≤1)when the server take vacations.LUO and TANG[5]studied the M/G/1 queue withp-entering discipline during single server vacations.Subsequently,this research was extended to the MX/G/1 queue withp-entering discipline during adaptive multistage vacations by LUO and YU[6].Recently,LIU and TANG[7]analyzedM/G/1 repairable queue system withp-entering discipline during multiple server vacations,TANG et al.[8]investigated M/G/1 repairable queue withp-entering discipline during second type failure times.

In this paper we consider the discrete time Geo/G/1 queue withθ-entering discipline during multiple adaptive vacations,in which the customer input rate depend on the server status (being in vacations or not).This model is very useful since it takes the behavior of arriving customers into consideration.The customer’s attitude to join the queue can be different according to whether the server is immediately available or not.For example,the entering rate may be higher when the server is busy than when the server is in vacations since the arriving customer expects he would be served very soon.

The remaining of this paper is structured as follows.Section 2 presents a description of the model and some notations used in this paper.In Section 3,we study the transient probability distribution of the queue length at time epochn+during server busy period.In Section 4,we study the transient probability distribution of the queue size at time epochn+.We study the steady state probability distribution of the queue length at time epochsn+,n−andnin Section 5 and Section 6,respectively.In Section 7,Several special cases are given.Finally,we give some numerical results in the form of tables and graphs in Section 8.

2.Model Description

We deal with a discrete time Geo/G/1 queueing withθ-entering discipline during multiple adaptive vacations.In this study,we consider the late arrival system with delayed access(LAS-DA)[3],that is,a potential arrival occurs only within(n−,n),n=0,1,2,···,a potential service and departure takes place in (n,n+),n=1,2,···.Furthermore,we assume that there is no customer arrival in (0−,0)and no departure in (0,0+).

The inter-arrival times{τk,k=1,2,···} are independent and identically distributed (i.i.d.)random variables with geometrical distributionP{τk=j}=p(1−p)j−1,j=1,2,··· ,0

There is only one service station in the system and the customers are served one by one according to the first-come-first-served (FCFS)discipline.The service times,denoted by{χk,k=1,2,···} are i.i.d.discrete time random variables with the probability mass function (p.m.f.)P{χk=j}=gj,j=1,2,···,and the probability generating function(p.g.f.)G(z)=The mean service time isµ(1 ≤µ<∞).

The server takes multiple adaptive vacations (MAV)[2]when the system becomes empty.LetHbe the times of vacation.The p.m.f.and the p.g.f.ofHisP{H=j}=hj,j=1,2,···andH(z)=,respectively.Vacations,denoted byV,are i.i.d.discrete time random variables with the p.m.f.P{V=j}=vj,j=1,2,···and the p.g.f.ofVisand have finite meanE[V].

The arriving customers enter directly the system when server does not take vacations.However,the customers who arrive during server vacations enter the system with probabilityθ(0<θ1).

We assume that the arrival process,service process,service vacation and random variableHare independent of each other.It is also supposed that the server will stay idle and wait for the first arrival if there is no customer at initial timen+=0+.If there arei(i1)customers in the queue at initial time epoch 0+,the service begins at once.After the first busy period,the server begins to take vacations.

In this paper,letN(n−),N(n),N(n+)denote the number of customers in the system at time epochsn−,n,n+,letρ=pµdenote the traffic intensity of the system; letVkbe thekth vacation,whereVk,k=1,2,··· ,Hare independent mutually and satisfy the same distribution asV,V =V1+V2+···+VH;=1−p.

3.Transient Queue Length Distribution at Epoch n+ During Server Busy Period

For mathematical clarity,we note that the“server busy period”is from the instant when the server begins to serve the waiting customers until the system becomes idle again.Letbrepresent the length of the server busy period beginning with only one customer.We have the following lemma which is also given by Bruneel and Kim[1].

Lemma 3.1Let t henB(z)is subject to the equationB(z)=G(z−pz(1−B(z))),and mean value ofbis given by

ProofLetχ1denote the service time of the first customer served in the server busy periodb,andγthe number of customers arriving duringχ1.Then

We consider the customers who arrive in the system duringχ1as primary customers,and the other customers who arrive after the primary customers as secondary customers.Furthermore,letA1,A2,··· ,Aγdenote the primary customers.Since the order of service for arriving customers is irrelevant to the length of server busy period,we introduce the following service order:primary customers are served in the order ofA1,A2,··· ,Aγ.After serving each primary customer,however,the server will serves every secondary customers until there are no secondary customers at present.So the server busy periodbis expressed by

whereDk(k=1,2,··· ,γ)denotes the time interval from the time epoch when the server begins to serve thekth primary customer until the next time epoch when the service of the(k+1)th primary customer begins.It also means that there are no secondary customers present in the system when thekth primary customer has departed.Hence,eachDk(k=1,2,··· ,γ)can be considered as a new sever busy period begins with one customer when the service timeχ1ends.Therefore,Dk(k=1,2,··· ,γ)are independent random variables from each other with the same distribution asb.LetD1+D2+···+Dγ=0 only ifγ=0.Since the point when the server busy period ends is a renewal point,we have

Taking the p.g.f.on both sides of Equations (3.1)yieldsB(z),andE(b)can be derived by

Letbdenote the server busy period initiated withicustomers.Due to the Markovian property of geometric distribution,bcan be expressed asb=b1+b2+···+bi,i=1,2,··· ,whereb1,b2,··· ,biare independent of each other,and have the same distribution function asb,so that

The intervals of customers who arrive and enter the system during server vacations,denote byIk,k=1,2,···are i.i.d.random variable with p.m.f.P{Ik=j}=θp(1−θp)j−1,j=1,2,··· .

The “System idle period” is from the instant when the system becomes empty until a new customer arrives and enters the system.Letdenote thekth “system idle time”,k=1,2,···.Based on the assumptions given above,we have

WhenN(0+)=0,

WhenN(0+)=i(i≥1),

In the remaining part of this section,we will give the joint distribution of the queue length at epochn+during server busy period beginning with only one customer.LetQj(n+)=P{b>n+,N(n+)=j},j=1,2,···represent the probability that the queueing length equals tojat epochn+during server busy periodb,where the instantn+=0+is the beginning of the busy periodb,and the boundary condition isQ1(0+)=1,Qj(0+)=0,j=2,3,···.With the similar argument in [9-10],we have the following lemma.

Lemma 3.2If|z|<1,lettingpresent thez-transform ofQj(n+),we have

ProofEmploying renewal process theory and total probability decomposition,we obtainQ1(n+)=P{χ1>n+,N(n+)=1}+P{χ1n+<χ1+D1+D2+···+Dγ,N(n+)=1}=P{χ1>n+,no customer arrive in(0,n+]}+

whereDk(k=1,2,··· ,γ)are given in the proof of Lemma 3.1.It is important to note that eachDk(k=1,2,··· ,i)follows the same probability properties asb.Hence,

Forj=2,3,···,we have

If time point(n−k)+locates inDmandN((n−k)+)=j,according to the service order that mentioned in the proof of Lemma 3.1,there arei−mprimary customers waiting for service.That implies,at epoch (n−k)+,the number of secondary customers present in the system is equal toj−(i−m).Hence,

Substituting (3.6)into (3.5),we have

Taking the p.g.f.on both sides of the Equations (3.4)and (3.7),and interchanging order of summation yield the conclusion given by Lemma 3.2.

4.Transient Queue Length Probability Distribution at Epoch n+

LetPij(n+)=P{N(n+)=j|N(0+)=i} be the conditional probability of there beingjcustomers at epochn+with initial stateN(0+)=i,andbe thez-transform ofPij(n+),i,j=0,1,2,···.Using the total probability decomposition andz-transform,we derive thez-transform expressions(z)of the transient queue length distribution.

Theorem 4.1If|z|<1,then(z)and(z)are given by

ProofLetsk=Vm,k=1,2,··· ,ands0=0.The system is empty at time epochn+if and only if the system is in “system idle period”.Thus,the conditional probabilityP00(n+)indicates that there is no customer in the queue at epochn+under initial stateN(0+)=0.Using the renewal process theory and total probability decomposition technique,we have

By the same probabilistic argument as the analysis ofP00(n+),forN(0+)=i,i=1,2,···,we can get

Taking thez-transform on both sides of the equations (4.3)and (4.4),respectively,we have

From equations (4.5)and (4.6),the relationship betweenandis given by

Substituting (4.7)into (4.5),we have

Note that

Substituting (4.9)into (4.8)gives (4.1),and furthermore,we can get (4.2)by inserting (4.1)into (4.7).

Theorem 4.2If|z|<1,then(z)and(z)are given by

where(z)is determined by Lemma 3.2,∆is given by Theorem 4.1,and

ProofForj=1,2,···,statingN(n+)=jindicates that epochn+locates in server busy period or server vacation withjcustomers waiting for service.So

ForN(0+)=i,i=1,2,···,similarly,we have

Taking thez-transform on both sides of the equations (4.12)and (4.13),respectively,we have

With (4.14)and (4.15),we obtain the relationship between(z)and(z)as follows

Substituting (4.16)into (4.14),we obtain

Interchanging order of summation,we have

Moreover,it can be easily obtained that

Substituting (4.18)and (4.19)into equation (4.17)yield (4.10),then,we can get (4.11)by using (4.10)and (4.16).

5.Steady State Queue Length Probability Distribution at Epoch n+

Based on the transient distribution of the queue length at epochn+obtained in Theorems 4.1 and 4.2,we will investigate the steady state queue length distribution at epochn+.

Theorem 5.1Let

1)Ifρ＜1,=0,j=0,1,2,···;

where

E[V]is the mean value of a vacation; for

ProofUsing total probability decomposition and noting 0≤P{N(0+)=i}Pij(n+)<1,we get

Employing Lemmas 3.1 and 3.2,Theorems 4.1 and 4.2,and applying L’Hospital’s rule,Theorem 5.1 can be obtained.In fact,L’Hospital’s rule used in the calculation ofbased on limitation theory ofz-transform[11]leads toE[b]in the denominator.Because the condition ofρ <1 given in Lemma 3.1 ensures the existence ofE[b]andρ≥1 results inE[b]=∞,which brings to=0,j=0,1,2,···,the equilibrium queue length distribution does not exist ifρ≥1 holds on.

Corollary 5.1Lettingrepresent the p.g.f.of the steady state queue length distribution{p+j ,j=0,1,2,···} at epochn+,forρ<1,we have

ProofCarrying out direct calculations onwe get

Noting that

we have

Substituting (5.5)and (5.6)into (5.4)yields (5.3)after some algebraic simplifications.

Remark 5.1The conclusion given by Corollary 5.1 shows thatπ+θ(z)can not be decomposed byπ+(z)·Φ+(z)under the assumption ofθ-entering discipline during multiple adaptive vacations,that is,πθ+(z)=π+(z)·Φ+(z),wheredenotes the p.g.f.of equilibrium queue length distribution of classical the discrete-time Geo/G/1 queue,Φ+(z)denotes the p.g.f.of the additional queue length caused byθ-entering discipline during multiple adaptive vacations,and it contains noG(1−p+pz).It implies that the equilibrium queue length discussed in this paper no longer follows the stochastic decomposition structure under the assumption ofθ-entering discipline during multiple adaptive vacations.

Corollary 5.2LettingE[L+]denote the mean steady state queue length at epochn+,forρ<1,we get

ProofWe can easily obtain (5.7)by using

6.Steady State Queue Length Probability Distribution at Time Epochsn−and n

In order to obtain the queue length distributions at time epochsn−andn,we define some additional notations.LetPij(n−)=P{N(n−)=j|N(0−)=i},Pij(n)=P{N(n)=j|N(0)=i} denote the transient probability.are equilibrium probability,LetE[L]denote the mean steady state queue length at epochn.Furthermore we suppose there is no customer arrival in the beginning time interval (0−,0)and no departure in (0,0+).It meansP{N(0−)=i}=P{N(0)=i}=P{N(0+)=i}.Therefor,fori≥0,j≥0,n≥1,we have

Taking limit asn→∞on the equation(6.1)and using Theorem 5.1,we get the following theorem.

Theorem 6.1Forρ<1,we have

wherep+j(j=0,1,2,···)is determined by Theorem 5.1,πθ+(z)is given by Corollary 5.1.

The results in Theorem 6.1 indicate that the equilibrium queue length distribution at time epochn+is the same as the one at time epochn−.

We proceed to find the recursive solution for the queue length at time epochn.Since the customers arrive in the system according to Bernoulli process,and the departure occurs only in interval (n,n+),we obtain the relations betweenandpjunder the stability conditionρ<1 as follows:

We can obtain from the above relational expressions the following theorem by direct calculation.

Theorem 6.2Forρ<1,we have

where=0,1,2,···are determined by Theorem 5.1.

Remark 6.1From Theorems 5.1,6.1 and 6.2,we can obtain the following relationship

The relationship indicates the important difference between the discrete-time queueing system and the continuous-time queueing system.

7.Several Special Cases

Some models are special cases of the model discussed in this paper.

Corollary 7.1TakeP{H=∞}=1.ThenH(z)=0,therefore the model reduces to the discrete time Geo/G/1 queue with multiple vacations andθ-entering discipline during server vacations.

Corollary 7.2TakeP{H=1}=1.ThenH(z)=z,so the model discussed in this paper becomes the discrete time Geo/G/1 queue with single vacation andθ-entering discipline during server vacation.

Corollary 7.3SetP{H=∞}=1,θ=1.Then the model discussed in this paper becomes the discrete time Geo/G/1 queue with multiple vacations.

Corollary 7.4SetP{H=1}=1,θ=1.Then our model becomes the discrete time Geo/G/1 queue with single vacation.

8.Numerical Examples and Discussion

To demonstrate the applicability of the formulae provided by Theorem 5.1 and Corollary 5.2,we present some numerical examples in the form of tables and graphs.Here we first investigate the effect of different vacation time and parameterθon the steady state queue length distribution.Then,we illustrate the effect of variantHon the idle probabilityp+0and the stationary mean queue length.Finally,under a special case,we investigate the system capacity optimization design.

In Tab.8.1,we present the steady state queue length distribution and the average queue length.Here we consider that service timeχ,vacation timeVandHfollow geometric distribution with parametersqandh,respectively.Furthermore,we selectp=0.1,µ=2,h=0.2.Four cases (q=0.02,θ=0.5;q=0.02,θ=0.75;q=0.05,θ=0.5;q=0.05,θ=0.75)are considered to illustrate the effect of variant vacation time and parameterθon the steady state queue length distribution.Tab.8.1 shows that the steady state queue size distributionis very close to 0 whenjexceeds some value.

Remark 8.1The notation used in the tables and graphs are the same as those defined earlier in this paper.

Tab.8.1 Steady state queue length distribution for vacation time and parameter θ

In Figs.8.1 and 8.2,we illustrate the effect of variant H.Hereχfollows geometric distribution with meanµ=2,andVfollows geometric distribution with parametersq=0.05.We takeθ=0.75.In Fig.8.1,system idle probabilityp+0is plotted versus arrival ratep.We have presented four curves corresponding to constantH=1,2,5,∞,respectively.In Fig.8.2,mean queue lengthE[L+]is plotted versusp.As we expected,the graphs show that asHincreasesp+0decreases andE[L+]increases.The figures are useful for optimization; for example,they show that the results forH=5 and∞are very close.

Fig.8.1 The idle probability vs. p

Fig.8.2 The mean queue length vs. p

Fig.8.3 The idle probability vs. θ

Fig.8.4 The mean queue length vs. θ

Figs.8.3 and 8.4 illustrate the effect of variantθandV.Hereχfollows geometric distribution with meanµ=2,VandHfollow geometric distribution with parametersqandh=0.2,respectively.We takep=0.1.In Fig.8.3p+0is plotted versusθ.Three curves are presented corresponding toq=0.01,0.02 and 0.05,respectively.It is clear thatp+0increases as the parameterθdecreases.Fig.8.3 illustrates thatp+0is larger for shorter vacation time.The same discussing holds for Fig.8.4,which illustrates the behavior ofE[L+]as function ofθ.

In practice,the congestion of facilities is a key factor to be considered in decision-making,since it has serious negative implications in both the manufacturing and the service sectors.The immediate consequence of congestion is that it leads to an increase in operating costs;further,the degradation in the quality of service results in customer dissatisfaction and eventual loss of market share.In most of the cases,queueing managers often use the stationary mean queue length to calculate the buffer capacity,so as to reduce the blocking probability of the system.However,through the following numerical example,we can see that employing the stationary mean queue length to estimate the buffer capacity may be not very suitable.

Letp=0.1,q=0.05,µ=2,h=0.2,θ=1,by Corollary 5.2,we obtainE[L+]=2.0678.Furthermore,using the datums presented in Tab.8.2,Eqs.(8.1)and (8.2)give the probability that the number of customers in the system exceeds the mean queue length.From the calculation results,we can realize that the probability of more than 30.724% is too high,this also means that a considerable number of customers will be rejected by the system due to no waiting place available upon arrival.Therefore,using the mean queue length to design the system capacity is quite inaccurate.On the other hand,from Tab.8.2,we further observe that the probability that the number of customers in the system exceeds 20 is less than 0.01%.Thus,design a system with large capacity is also unnecessary.In practice,we may use the steady state queue length distribution and give some more reasonable system designs,so as to reduce the system operating costs.

Tab.8.2 The steady state queue length distribution when p=0.1,q=0.05,µ=2,h=0.2,θ=1

9.Conclusion

Using a different method,we present a complete analysis of a discrete time Geo/G/1 queue withθ-entering discipline during multiple adaptive vacations for LAS-DA model.We have investigated various performance measures which include not only the transient queue size distribution at epochn+,but also the explicit recursive formulae of equilibrium queue size distributions at epochsn−,nandn+.The recursive formulae given by Theorems 5.1 can be used to calculate the accurate numerical value of queue length distribution{=0,1,2,···}.It is very important to the application of discrete time queue.In addition,from Theorems 6.1 and 6.2,we have the important relations among equilibrium queue length distribution at different epochsn−,nandn+.Moreover,from Remark 5.1 we know that the property about stochastic decomposition of queue length no longer comes into existence in Geo/G/1 withθ-entering discipline during multiple adaptive vacations.Finally,some numerical results are given to illustrate the effect of variant parameters on equilibrium queue length distribution,and the significant application value of stationary queue size{=0,1,2,···} in designing system capacity is also analyzed.