# Discrete-Time Bulk Queueing System with Variable Service Capacity Depending on Previous Service Time

Authors: Yutae Lee
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

This paper considers a discrete-time bulk-arrival bulk-service queueing system
with variable service capacity, where the service capacity varies depending on
the previous service time. Using the supplementary variable method and the
generating function technique, we obtain the queue length distributions at arbitrary
slot boundaries and service completion epochs.


---

## Body

## 1. Introduction

For the last two decades, there has been a growing interest in the analysis of discrete-time queueing systems due to their numerous applications in the modeling and performance analysis of manufacturing and telecommunication systems [1–4]. In discrete-time system, time is treated as a discrete variable, and arrivals and service completions can only occur at boundary epochs of time slots. The discrete-time system can also be used to approximate the continuous system in practice. The earliest work on discrete-time queueing system was presented by Meisling [5]. The books of Hunter [6], Bruneel and Kim [7], and Takagi [8] and their references provide us with a wide study of different discrete-time queues.Bulk-service queueing systems are useful to investigate the performance of various systems in the areas such as manufacturing, production, telecommunication, and transportation [9]. It may happen that the server in bulk-service systems has a fixed maximum capacity, or else the server may take customers according to variable service capacity. Such systems may serve as a model for a shuttle or automatic elevator [10].Let us review some related previous work. In the existing literature, there have been a number of contributions with respect to bulk-service queueing systems. The reader is referred to Chaudhry and Templeton [11], Dshalalow [12], Medhi [13], and Banerjee et al. [14] and the references therein for a detailed account of continuous-time bulk-service queueing systems. This paper considers a discrete-time bulk queueing system. Dummler and Schomig [15] considered the Geo/Ga,b/1 queueing systems with a≤b for nonnegative integers a and b. In this section we use the notation A/BX,Y/c, where X denotes the threshold value of activating the server and Y the service capacity. Gupta and Goswami [16] discussed analytic and computational aspects of Geo/Ga,b/1/N queueing system. Using the arrival time approach of Chae et al. [17], Kim and Chae [18] found the probability generating function (PGF) of the queue length for a discrete-time GeoX/Gb,b/1 queueing system. Chaudhry and Chang [19] considered a discrete-time Geo/G1,Y/1/N queueing system with variable capacity. They discussed the computational aspects of the distribution for the number of customers in the queue at various epochs. Using an invariance relation, Kim et al. [20] considered GeoX/Ga,Y/1 and D-BMAP/Ga,Y/1 queueing systems with variable service capacity and obtained the PGF of the stationary queue length at a random point on the continuous-time domain.An interesting service discipline in bulk-service queueing system, which has received considerable attention in recent years, is bulk-size-dependent service. Claeys et al. [21] carried out analysis of discrete-time bulk-service queueing systems with infinite buffer under bulk-size-dependent service and obtained various performance measures. Banerjee et al. [22] analyzed a finite-buffer discrete-time bulk-service queueing system with bulk-size-dependent service. To the best of author’s knowledge, no such queueing model involving bulk-service queue with variable service capacity depending on previous service time has been discussed so far in the literature.In this paper, we analyze a single-server infinite-buffer discrete-time bulk-service queueing system where the service time of each bulk is arbitrary distributed and the service capacity depends on the previous service time. This kind of queues can be applied to model vehicle operations in the field of transportation engineering. For example, consider a shuttle bus service from hotels to airport. An improved understanding of bus operation is important for well-managed bus services [23]. To analyze the quality of service such as waiting time and travel time, which are the top two most important bus transport service attributes [23], at an intermediate bus stop along the route of shuttle bus, we can take into account a queueing model, the service time of which can be viewed as an interarrival time of buses at the bus stop. The longer the interarrival time at a bus stop is, the more passengers the arriving bus has picked up at the previous bus stops and the less the available capacity of the bus at the bus stop is. Thus, the service capacity of the bulk-service queueing system depends on the previous service time. By using the supplementary variable method and the generating function technique, we compute the queue length distributions at arbitrary slot boundaries and service completion epochs.


## 2. System Model

This paper considers a discrete-time single-server queueing system in which the time axis is divided into fixed-length contiguous intervals, referred to as slots. It is always assumed that service times can be started and completed only at slot boundaries and that their durations are integral multiples of slot durations [24].Customers arrive to the system in accordance with a batch geometric process [25] and are accommodated in the buffer with infinite waiting-room. Let ak be the number of customers that arrive during slot k. The numbers of customers entering the system during the consecutive slots are assumed to be i.i.d. nonnegative discrete random variables with an arbitrary probability distribution and are characterized by the PGF:(1)Az≡Ezak,where the operator E[·] indicates the expected value of the expression between the square brackets.The customers are served in groups. Letcn be the service capacity for the nth bulk service; that is, the nth bulk size is less than or equal to cn. If the number of customers waiting in the buffer is less than or equal to cn, the server takes all the customers in the buffer; otherwise, if the number of customers in the buffer is larger than cn, the server only takes cn customers among the waiting customers in the buffer. The service capacity cn is assumed to be less than or equal to a specified maximum service capacity C.Letsn be the service time of the nth bulk. It is assumed that the service times and the service capacities are independent of the arrival process. But we assume that the service capacity cn for the nth bulk service is dependent on the previous service time sn-1. We define ϕi(j) as the joint probability that the service time of the (n-1)th bulk is j slots and the service capacity for the nth bulk service is C-i customers:(2)ϕij≡Pcn=C-i,sn-1=j,0≤i≤C,j≥1.Note that, in shuttle bus service model described in the previous section, the subscript i in the notation ϕi(j) specifies the number of passengers already on the arriving bus, the maximum capacity of which is C.We define the joint PGFΦ(y,z) as(3)Φy,z≡∑i=0C∑j=1∞ϕijyizjand also define the average service capacity and the average service time as(4)C¯≡C-dΦy,1dyy=1,S¯≡dΦ1,zdzz=1,respectively.In this paper, even if there are no customers in the buffer and/or the service capacity is zero, the server starts its service. In other words, the server continues serving even if no customer is picked up for service. It is also assumed that arriving customer cannot be accepted into the bulk already undergoing service even if the capacity of server is available but has to wait until the next service instant.


## 3. Embedded Markov Chain

We define some random variables. Let a random variablenk indicate the number of customers in the queue at the end of slot k and let a random variable(5)uk=C-cn+1for σn-1<k≤σn, where σn, n=0,1,2,…, are the instants at service completion of successive bulk. Clearly, the set (nk,uk) does not form a Markov chain because the knowledge of the value of (nk,uk) is not sufficient to determine the probability distribution of (nk+1,uk+1). Some more information is needed to form a Markov chain. Let us introduce a supplementary random variable rk, which indicates the remaining service time at the end of slot k as follows:(6)rk=σn-kfor σn-1<k≤σn. With this definition, the stochastic process {(nk,uk,rk),k≥0} constitutes a three-dimensional Markov chain embedded at the end of each slot.


## 4. Stability Condition

We will find the stability condition of the Markov chain{(nk,uk,rk),k≥0}. We assume that the Markov chain {(nk,uk,rk),k≥0} is irreducible. Obviously, S¯A′(1)<C¯ is the necessary condition for the Markov chain {(nk,uk,rk)} to be positive recurrent. Note that S¯A′(1) is the average number of customers arriving during a service time and C¯ is the average service capacity. We intend to show that S¯A′(1)<C¯ is the sufficient condition for the Markov chain to be positive recurrent.Now, we assume thatS¯A′(1)<C¯. Foster’s criterion [26] is used in order to show that the Markov chain {(nk,uk,rk),k≥0} is positive recurrent. We choose a real number α such that(7)S¯-1C¯-A′1<α<1A′1and choose the test function as follows:(8)fi,j,l≡αi+j+l.The mean drift of the test function is(9)zijl≡Efnk+1,uk+1,rk+1-fnk,uk,rk∣nk,uk,rk=i,j,l=αA′1-1+S¯-αi+j+C¯-Cif0≤i+j≤C-1,l=0,αA′1-1+S¯-αC¯ifi+j≥C,l=0,αA′1-1ifl≥1.Then, zijl<∞ for all i, j, and l, and(10)zijl≤min⁡αA′1-1+S¯-αC¯,αA′1-1<0for i+j≥C and/or l≥1. Let(11)ϵ=-minαA′1-1+S¯-αC¯,αA′1-12>0.Then, zijl<-ϵ for i+j≥C and/or l≥1. Hence, except finite subset {(i,j,l)∣0≤i+j≤C-1,l=0} of the state space for the Markov chain {(nk,uk,rk)}, we have(12)zijl<-ϵ.Thus, by Foster’s criterion, we see that the Markov chain is positive recurrent. Hence, S¯A′(1)<C¯ is also the sufficient condition for the Markov chain {(nk,uk,rk)} to be positive recurrent. Therefore, assuming that the Markov chain {(nk,uk,rk)} is irreducible, the Markov chain is stable if and only if(13)S¯A′1<C¯.


## 5. Queue Length Distribution

In this section, the queue lengths at the end of slots are analyzed. If we denote byak the number of customers entering the system during slot k, then the following state equations can be established:(a)
ifrk=0, then (14)nk+1=nk-C-uk++ak+1,uk+1=i,rk+1=j-1with  probabilityϕij,where(a)+ denotes the maximum value of a and 0;(b)
ifrk>0, then (15)nk+1=nk+ak+1,uk+1=uk,rk+1=rk-1.Now, let us definePk(x,y,z) as the joint generating function of the state vector (nk,uk,rk), valid at the end of slot k:(16)Pkx,y,z≡Exnkyukzrk.Our next step is to derive a relationship betweenPk(x,y,z) and Pk+1(x,y,z) by using the above state equations. We proceed as follows:(17)Pk+1x,y,z≡Exnk+1yuk+1zrk+1=EIrk=0xnk+1yuk+1zrk+1+Irk>0xnk+ak+1yukzrk-1=AxzPkx,y,z-Pkx,y,0+Ax·EIrk=0xnk+uk-C+yuk+1zrk+1=AxzPkx,y,z-Pkx,y,0+Ax·∑i=0C∑j=1∞ϕijyizj-1EIrk=0xnk+uk-C+=AxzPkx,y,z-Pkx,y,0+AxΦy,zzEIrk=0xnk+uk-C+=AxzPkx,y,z-Pkx,y,0+Φy,z·EIrk=0,nk+uk<C+Irk=0,nk+uk≥Cxnk+uk-C=AxzPkx,y,z-Pkx,y,0+Φy,z·1xCPkx,x,0-1xCQkx+Qk1=AxzPkx,y,z-Pkx,y,0+Φy,zxCPkx,x,0-Qkx+xCQk1,where the function Qk(x) is defined as(18)Qkx≡EIrk=0,nk+uk<Cxnk+uk.Equation (17) provides the relationship between Pk(x,y,z) and Pk+1(x,y,z). It is clear that both of these functions will converge to a common limiting function:(19)Px,y,z≡limk→∞Pkx,y,z,provided that the system reaches a steady state; that is, the stability condition S¯A′(1)<C¯ is satisfied. In the sequel, we assume that this requirement is fulfilled. In these circumstances the limiting function P(x,y,z) can be derived by taking the limit of k→∞ in (17) and solving for P(x,y,z). As a result we obtain(20)z-AxPx,y,z=Ax·Φy,zxCPx,x,0-Qx+xCQ1-Px,y,0,where(21)Qx≡limk→∞Qkx.We notice that the functionP(x,y,z), as a result of its definition (16) and (19), must be bounded for all values of x, y, and z such that x≤1, |y|≤1, and |z|≤1. In particular, this should be true for z=A(x) and x≤1, since the PGF A(x) satisfies A(x)≤1 for all such x. The above implies that if we choose z=A(x) in (20), where x≤1, the left-hand side of this equation vanishes. Of course, the same must then be true for the right-hand side of (20), which yields the following equation for P(x,y,0):(22)Px,y,0=Φy,AxxCPx,x,0-Qx+xCQ1.By puttingy=x in (22) and solving for P(x,x,0), we obtain(23)Px,x,0=Φx,AxxCQ1-QxxC-Φx,Ax.It now remains to determine the unknown functionQ(x), which has the C unknowns:(24)limk→∞⁡Prk=0,nk+uk=l,l=0,1,…,C-1,in order to obtain an expression for P(x,y,z). The expression (23) allows us to determine the unknowns, contained in the function Q(x), in the following way. Whenever the condition (13) for the existence of a stochastic equilibrium is fulfilled, the denominator of (23)(25)xC-Φx,Ax=0has exactly C zeros inside the unit disk of the complex plane, one of which equals unity. This can be proved using Rouche’s theorem from complex analysis. A detailed explanation can be found in Saaty’s work [27]. Since P(x,x,0) is a generating function, it cannot have any poles inside the unit disk. This means that the C zeros of the denominator of (23) must be zeros of the numerator as well. This condition provides us with C-1 linear equations in the unknowns, which, together with the equation(26)P1,1,0=1S¯,can be used to determine the unknowns and hence P(x,y,z). Note that, using l’Hopital’s rule, the relation (26) is found to be(27)C¯-S¯A′1=S¯CQ1-Q′1,which equates two expressions for the average unused service capacity.TheC roots of xC-Φ(x,A(x))=0 in the closed unit disk {x:|x|≤1} are denoted by x0=1,x1,…,xC-1. If one of the roots is a zero of Φ(x,A(x)), then it should be 0, which cannot be true. Thus, all the C roots are zeros of xCQ(1)-Q(x), not of Φ(x,A(x)). Hence, by writing xCQ(1)-Q(x) in (23) as(28)Hx-1∏l=1C-1x-xlwith H a constant and using (27) to derive the value of H, it follows that(29)xCQ1-Qx=C¯-S¯A′1S¯x-1∏l=1C-1x-xl1-xl,so that (23) can be written as(30)Px,x,0=C¯-S¯A′1Φx,AxS¯xC-Φx,Axx-1∏l=1C-1x-xl1-xlfor |x|≤1.Therefore, using (22) and (30) in (20), the joint PGF P(x,y,z) can be written as(31)Px,y,z=C¯-S¯A′1AxS¯z-Ax·Φy,z-Φy,AxxC-Φx,Axx-1·∏l=1C-1x-xl1-xl.LetN(x) be the PGF of the queue length at an arbitrary slot boundary. The PGF N(x) can be obtained from P(x,y,z) by simply putting y=z=1:(32)Nx≡limk→∞Exnk=Px,1,1=C¯-S¯A′1AxS¯1-Ax·1-Φ1,AxxC-Φx,Axx-1∏l=1C-1x-xl1-xl.LetD(x) be the PGF of the queue length at a service completion time. Clearly, the PGF D(x) can be expressed as(33)Dx=Px,1,0P1,1,0=C¯-S¯A′1Φ1,AxxC-Φx,Axx-1∏l=1C-1x-xl1-xl.The PGFsN(x) and D(x) are related by(34)Nx=Dx·1Φ1,Ax·Ax1-Φ1,AxS¯1-Ax,where the denominator Φ(1,A(x)) of the second term of the right-hand side represents the PGF of the number of customers that arrive during a service time, and the third term(35)Ax1-Φ1,AxS¯1-Axrepresents the PGF of the number of customers that arrive during an elapsed service time.Now we can calculate the mean queue lengths at an arbitrary slot boundary and a service completion time by using the differentiation of the respective PGFsN(x) and D(x) for x=1. We obtain(36)μN≡N′1=A′12-12S¯A′1-CC-12C¯-S¯A′1+12∑l=1C-111-xl+A′1S¯d2Φ1,xdx2x=1+12C¯-S¯A′1d2Φx,Axdx2x=1,μD≡D′1=12S¯A′1-CC-12C¯-S¯A′1+12∑l=1C-111-xl+12C¯-S¯A′1d2Φx,Axdx2x=1.The expressions for the higher-order moments can be derived as well from the appropriate derivatives of the respective generating functions.


## 6. Conclusions

This paper considered the discrete-time bulk-arrival bulk-service queueing system with variable service capacity depending on the previous service time. The stability condition for our system was investigated. By means of the generating function technique and the supplementary variable method, we provided an analysis of the queue length distributions at an arbitrary slot boundary and a service completion time and calculated their moments.



---

*Source: 482179-2015-06-15.xml*