Geo (λ)/ Geo (μ) +G/2 Queues with Heterogeneous Servers Operating under FCFS Queue Discipl...

Thaga Keaogile, Adebayo Fatai Adewole, Sivasamy Ramasamy

  Open Access OPEN ACCESS  Peer Reviewed PEER-REVIEWED

Geo (λ)/ Geo (μ) +G/2 Queues with Heterogeneous Servers Operating under FCFS Queue Discipline

Thaga Keaogile1, Adebayo Fatai Adewole1,, Sivasamy Ramasamy1

1Department of statistics, University of Botswana, Gaborone, Botswana


This article discusses the steady analysis of a discrete time queue of Geo/Geo+G/2 type. All arriving customers are served either by server-1 according to a geometrically distributed service time S1=k slots for k=1,2, …∞, with mass function f1(k)==Pr(S1=k) = μ(1- μ) k-1 with mean rate 0<μ<1 or by server-2 with a general service time S2= k for k=1,2, …, with mass function f2(k)==Pr(S2=k) with mean service time is or mean service rate μ2=1/β. Sequel to some objections raised on the use of the classical 'First Come First Served (FCFS)' queue discipline when the two heterogeneous servers operate as parallel service providers, an alternative queue discipline in a serial configuration of servers are considered in this work; the objective is that if, in a single-channel queue in equilibrium, the service rate suddenly increases and exceeds the present service capacity, install a new channel to work serially with the first channel as suggested by Krishnamoorthy (1968). Using the embedded method subject to different service time distributions we present an exact analysis for finding the ‘Probability generating Function (PGF)’ of steady state number of customers in the system and most importantly, the actual waiting time expectation of customers in the system. This work shows that one can obtain all stationery probabilities and other vital measures for this queue under certain additional and simple but realistic assumptions.

Cite this article:

  • Keaogile, Thaga, Adebayo Fatai Adewole, and Sivasamy Ramasamy. "Geo (λ)/ Geo (μ) +G/2 Queues with Heterogeneous Servers Operating under FCFS Queue Discipline." American Journal of Applied Mathematics and Statistics 3.2 (2015): 54-58.
  • Keaogile, T. , Adewole, A. F. , & Ramasamy, S. (2015). Geo (λ)/ Geo (μ) +G/2 Queues with Heterogeneous Servers Operating under FCFS Queue Discipline. American Journal of Applied Mathematics and Statistics, 3(2), 54-58.
  • Keaogile, Thaga, Adebayo Fatai Adewole, and Sivasamy Ramasamy. "Geo (λ)/ Geo (μ) +G/2 Queues with Heterogeneous Servers Operating under FCFS Queue Discipline." American Journal of Applied Mathematics and Statistics 3, no. 2 (2015): 54-58.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

1. Introduction

Asynchronous transfer mode (ATM) multiplexers and broadband integrated services digital network (B-ISDN) use to transfer data sets, voice and video communications on a discrete time basis. Hence for studying the important characteristics of such discrete-time queueing of jobs served by a computer or a telecommunication device, the time axis can be divided into slots(fixed-length of contiguous intervals called slots of unit length (=right-end boundary-left-end boundary)).

Over the recent years, several authors Singh (1968), Hoksad (1979), Boxma et al. (2002), Efrosinin (2008), Kim et al. (2011), Krishnamoorthy and Srineevasan (2012) have studied continuous time queue length processes of either two server or multi-servers service systems. As the discrete–time queueing systems has been used to model computer and communication systems, authors Takagi (1993), and Bruneel and Kim (1993) have presented most of the basic features of discrete-time parallel queueing systems to that of continuous counterparts.

This paper discusses a special case of at the most only one arrival occurring(early arrival or late arrival)in a slot at slot boundaries and service to a job that can only start at a slot boundary. The service duration of a job and the inter-arrival durations between consecutive job arrivals are measured as random number of slot durations. The proposed discrete-time queueing system is Geo()/ Geo()+G/2 that has an infinite number of waiting positions with one faster server i.e. server-1 and a slow server i.e. server-2. One special feature of this investigation is that it derives those parallel results that have already been obtained to the corresponding continuous time version M/M+G/2 queues by Sivasamy and Kgosi (2014).

Late Arrival Model: Arrivals that come late in the slot (i.e. just before the slot boundary and before the service completions due to occur at the end of that slot) are called late arrivals. Number left behind in the queue as seen by a departure will include each late arrival and the time spent waiting in queue equals number of slots spent waiting for service not including the slot in which the job arrives.

Early Arrival Model: Arrivals that come early in a slot just after the left end slot boundary such that service completion of this arrival can occur just before the right-end slot boundary of the same slot. Number left behind in the queue as seen by a departure will not include the arrivals as in the late arrival cases. However the time spent waiting in queue equals number of slots spent waiting for service including the slot in which the job arrives.

Geometric (or Bernoulli) Arrival Process: Assume that the numbers of jobs that arrive in successive slots are independent, identically distributed (i.i.d.) random variables subject to a condition that only one job can arrive in a slot with probability (0<<1) and that no jobs arrive in a slot with probability 1-.

It ensures that the inter-arrival time A is geometrically distributed with mean 1/and with probability the probability distribution P{A= k slots}=(1-)k-1 for k=1,2,..., while A(z)= probability generating function (PGF) A(z) of inter-arrival times and L(z)= the PGF of the number of arrivals in a slot are respectively given by


Service time distributions: For customers serviced by server-1, their service time S1 follows geometric distribution with mass function f1(k)=P(S1=k)=(1-)k-1 for k=1,2, …,with mean 1/μ or service rate μ (0<μ<1) per slot and hence the PGF of S1 and Ls(z)= the PGF of the number of departures in a slot are respectively


Let the service times S2 of customers serviced by server-2 follow a general distribution f2(k)=P(S2=k) with PGF is


Both of these service times S1 and S2 are assumed to be mutually independent and each is independent of inter-arrival time distribution also. One of simple ways of connecting the servers in series subject to servicing of customers according to the FCFS queue discipline is proposed below:

•  If an arriving job or customer enters into the idle system, his service is immediately initiated by server-1. This customer is then served by the server-1 at a constant rate μ if no other customer arrives during the on-going service period;

•  Otherwise i.e. if at least one more customer arrives before the on-going service is completed then the same customer is served jointly by both servers according to the service time distribution fmin(k)=P(Smink), where Smin = Min(S1, S2) and the PGF of Smin is Fmin(z):


The expected (i.e. mean) values of S1, S2 and of Smin variables are respectively E(S1) =F1’(z) ==(1/μ), E(S2) =F2’(1) and E(Smin) =Fmin’(1). For example, if the service time S2 is a geometric random variable with mean (1/μ2) then the mean of Smin can be obtained from (4) i.e.

It is then evident that the service rate of Smin is μ1+ μ2 –μ1μ2 due to the fact that there is a positive probability of serving a job simultaneously by both servers just before the end boundary of a slot.

Lemma: If no job is served simultaneously by both servers with service time=k slots, the service (or departure) rate ‘r(k)’ of jobs offered by the combined service time distributions f1(k) and f2(k) of serialized servers of the Geo()/Geo()+G/2 queueing system is given by

Let the mean service times of server-2 and that of server-1 be β= F2’(1)= and F1’(1)= respectively. Thus the mean service rate of server-2 is μ2=1/β. Letbe used in the sequel. It is remarked that closed form expression to r(k) can be obtained for particular cases of f2(k) like Geometric, Negative-binomial, or Phase (PH) type distributions. Assume that the service time distribution of the server-2 is one of these distributions with finite mean for our discussions to follow.

Negative-binomial Distribution: Let the service time S2 of server-2 be Negative-binomial NB(α,β) random variable with mass function b(k; α, μ2)=P(S2=k). If S2 denotes the number of slots required to complete the service by server-2 at the αth success in a sequence independent Bernouli trials with probability of success β (0<β<1), then

The mean of S2 is E(S2)= (α/β) and variance V(S2)=α(1-β)/β2. The mean service rate μ2=β/α, a constant for a fixed and known α and β values. Then the service (or departure) rate ‘r(k)’ of jobs offered by the combined service time distributions f1(k) and f2(k) of serialized servers of the Geo()/Geo()+NB(α,β)/2 queueing system is given by

If the mean service time of server-2 i.e. (1/μ2) (tends to ∞) then his service rate μ2and thus Geo()/Geo()+G/2 system Geo()/Geo()/1 system.

Queueing models operating under the above (1) through (4) conditions are a discrete time class of Geo()/Geo()+G/2 queues. We are motivated by the numerous physical applications and contributions of the above Geo/Geo+G/2 model since it can conceptualize well in the analysis of queues found in modern telecommunications, computer business centres, banking systems and similar service operations where human nature is evident.

Primary objective part of this study is to highlight the needs for designing serially connected system with two heterogeneous servers/machines which does not violate the FCFS principle in place of paralleled heterogeneous servers who violate the classical FCFS queue discipline. For instance, if there are two parallel clerks in a reservation counter who provide service with varying speeds then customers might prefer to choose the fastest service provider among the free servers. On the other hand if the customer chooses the slowest server among the free servers then the one who could come subsequently may clear out earlier by obtaining service from the server providing service with faster rates what is exactly called a violation of the FCFS discipline. Hence there is a need for the designing of alternative ways to the parallel service providers that would reduce the impacts of violating the FCFS so that the resulting waiting times of customers are identical.

The PGFs of the number of customers present in the system and the waiting time distribution and their mean values have been obtained in section 2. A numerical illustration is also provided to support the results on mean waiting times. Section 3 highlights the various special features of the proposed methodology and its future scope.

2. Steady State Characteristics of Geo(λ)/ Geo(μ)+G/2 Queues with Service Time Distribution Fmin(K)

We consider here 'the embedded time points' generated at the departure instants of jobs just after a service completion either by server-1 or by server-2. Hence the sequence of system states observed at these embedded points where the state of the system is represented by the number, Nk=N(tk), of jobs left behind in the queue by the kth departing job at the departure epoch ‘tk’ forms a Markov Chain process{Nk} on the state space ={0,1,...}.

2.1. PGF of {Nk}

Let qj be the steady state probability of finding 'j' customers in the system as observed by a departing customer and the z-transform of the probability distribution of {qj ; j=0, 1, ,... } be V(z) =

Let αj denote the probability of 'j' arrivals in a service completion period with mass function fmin(k) and δj denote the probability of 'j' arrivals in the geometrically distributed service time mass function f1(k). Since the arrivals come from a Geometric process at rate λ, we get, for j=1, 2, 3, ... that




Let the respective z-transforms of the probability distributions {αj} and {δj} be Amin(z) and A1(z):




Focusing on the embedded points under equilibrium conditions, let the unit step conditional transition probability of the system going from state 'i' of the (k-1)st embedded point to state 'j' in the kth embedded point be qij=P(Nk = j /Nk-1=i) for i, j . These transition probabilities will form the unit step transition probability matrix Q=(qij) as below:


Thus equilibrium state probabilities at the departure instants are given by qj = where qijn represents the n-step probability of moving from state 'i to j'. Let q=(q0,q1 ,q2,…) be a row vector and let e=(1,1, …,1) be a column vector of unit elements of infinite order. Assume that Amin’(1)<1, then the stationary distribution of the state transition matrix Q exits and is given by the unique solution of the following system of equations:


Multiplying the jth (j=0, 1, 2, …) equation of qQ=q , of (10) by zj and summing all the left-hand sides and the right-hand sides from j=0 to j=, we get the PGF (Probability generating Function) Vmin(z) of the queue length distribution {qj} of the sequence{Nk}.


Since q1= ρq0, Amin'(1)<1, A1'(1)=ρ and V(1)=1, we derive from (11) that




The mean number E(N) of customers present in the system at a random point or at a departure epoch of time is


The discrete time equivalent of the PASTA (Poison Arrivals See Time Averages) is referred to as BASTA (Bernoulli Arrivals See Time Averages) or GASTA (Geometric Arrivals See Time Averages). Using this BASTA property, it can be claimed that the distribution given by Vmin(z) of (13) will also hold for the number of jobs found in the system as seen by an arriving job.

Denote the PGF of the waiting time W that equals the number of slots for which an arriving job stays in the system with its distribution W(k)=P(W= k) by W(z)for 0<z<1. Then replacing 1- (λ -λz) by z in (13) one can show that


The mean waiting time of a customer in the system obtained from (15) is found to satisfy the well-known Little's formula λ=E(N).

2.2. How Geo (λ)/ Geo (μ) + G/2Geo(λ)/ Geo(μ)/1

For the purpose of proving the behaviour Geo()/ Geo()+G/2 Geo()/ Geo()/1, the PGFs of queue length and the waiting time distributions of Geo()/ Geo()/1 system, assuming the load ρ=(λ/µ)<1, are respectively given by Q0(z) and W0(z) below:

Lemma 2: If the mean service time (1/µ2) of the general distribution G of the second server does not exist i.e. (1/µ2)∞ as µ20, it is shown that

Proof: If (1/µ2)∞ as µ20 then F2(z) cannot exist and thus which is replaced by a zero in Fmin(z)=; this in turn proves that Amin((z))=F1(1-λ+λz)=A1(z). Proof of the lemma follows from replacing Amin(z) by A1(z) in the PGF of the queue length distribution Vmin(z) of (13) of the Geo()/ Geo()+G/2 since Vmin(z)=

3. Shortest Delay Time Environment For Geo(λ)/ Geo(μ)+G/2queues

The forgoing embedded methodology of analysing the embedded queue length process of the {Nk} sequence of Geo()/ Geo()+G/2 queues through the PGF Vmin(z) queues can also be extended to design a shortest processing environment as outlined below.

Let fmax(k)=P(Smax<k), where S1 and S2 denote the service times of server-1 and server-2 respectively as already defined and Smax = Max(S1, S2) and the PGF of Tmax be Fmax(z). Then

Considered below in (16) is the new joint service time PGF of ‘f(k)’ , the probability mass function of the cjoint service time of the two independent servers who are serially connected to serve the jobs without violating the FCFS discipline


where π1 and π2 are the probability values of choosing the service time PDFs fmin(k) and fmax(k) respectively. The corresponding z-transform of number of arrivals during the joint service PGF of f(k) is


Let and . Assume that A’(1) < 1 of (17), i.e.


Now on substituting A(z) of (17) in place of Amin(z) of (13), one can verify that V(z),the PGF of the queue length distribution of the sequence{Nk} (V(z) replaces Vmin(z) of (13) and f(k) in place of fmin(k)) is


Lemma: If and then A’(1)<1 of (17) implies that .

Proof: Notice that F2(1-μ)=μ2 (1-μ)/(1-(1-μ)(1-μ2)=μ /(μ+μ2- μ μ2) and

If A1’(1)<1, then ; hence the lemma.

Conditional Average Waiting Time(s): Let w1 and w2 be the mean waiting times corresponding to μ < μ2 and μ>μ2 values respectively. Thus w1=E(N)/λ when μ < μ2 and w2=E(N)/λ when μ > μ2. Now E(N)=V’(1) from (19) is


From the design criterion of the above model, it is expected that if the service rate μ of server-1 is larger than that μ2 of server-2 then w2< w1 with increasing values of π1. For an illustration, assuming that the probability of serving a job simultaneously by both servers in the same slot is zero (i.e. µµ2=0) w1 is calculated fixing λ=0.48, μ=0.45 and μ2=0.8 (geometric case) and w2 is computed fixing λ=0.48, μ=0.8 and μ2=0.45 (geometric case)while π1 varies between 0.4 and 1 and these values are reported in Table-1 (which also ensures that w2<w1 uniformly).

Table 1. Conditional Mean waiting times w1 when(λ=0.48,µ=0.45, µ2=0.8) and w2 when((λ=0.48, µ=0.8, µ2=0.45) of Geo(λ)/ Geo(μ)+Geo(μ2)/2 queues

This is a kind of two-server queueing application subject to unequal service rates will lead to the event of shortest mean waiting time or delay only if the service rate μ of server-1 is larger than that μ2 of server-2.

3.1. Conclusion

As the analysis of the above Geo(λ)/ Geo(μ)+G(μ2)/2 queues seems to be simpler and it is an easy procedure to implement if any real life application warrants. We conclude that the proposed method so far discussed is a good alternative for use instead of fitting of Geo(λ)/ Geo(μ), G(μ2)/2 parallel server queues. Most importantly there are few new results produced from above work that could be applied on the two-serially connected machines in the field of engineering problems rather than applied science areas. To extract more information like arrival epoch probabilities one can employ Markov Renewal theory as in Senthamarikannan and Sivasamy [9] and [10].


[1]  J. Medhi, Stochastic Models in Queueing Theory, 1: 01-457, 2003.
In article      
[2]  O.J Boxma, Q. Deng and A.P Zwart, “Waiting time asymptotic for the M/G/2 queue with heterogeneous servers’, Queueing Systems, 40: 5-31, 2002.
In article      CrossRef
[3]  P. Hoksad, “On the steady state solution of the M/G/2 queue”, Advanced applied probability}, 11, 240-255. 1979.
In article      CrossRef
[4]  D. Efrosinin, “Controlled Queueing Systems with Heterogeneous Servers: Dynamic Optimization and Monotonicity Properties of Optimal Control Policies in Multiserver Heterogeneous Queues”, 2008.
In article      
[5]  B.Krishnamoorthy, “On Poisson Queue with two Heterogeneous Servers”, Operations Research, 2 (3), 321-330, 1962.
In article      
[6]  V. P. Singh “Two-Server Markovian Queues with Balking: Heterogeneous vs. Homogeneous Servers”, Operations Research, 18 (1), 145-159, 1968.
In article      CrossRef
[7]  J. H. Kim, H.-S. Ahn, and R. Righter, “Managing queues with heterogeneous servers”, J. Appl. Probab., 48 (2), 435-452, 2011.
In article      CrossRef
[8]  Krishnamoorthy, B. and Sreenivasan, S. “An M/M/2 queue with Heterogeneous Servers including one with Working Vacations”, International Journal of Stochastic Analysis, Hindawi publishing company, 2012.
In article      
[9]  K. Senthamaraikannan, and R. Sivasamy, “Markov Renewal Queues of a M/M(a,d)/1/(b,N) System-Part I and Part II” Optimization, , Vol. 40, pp 121-145, 1997.
In article      CrossRef
[10]  K. Senthamaraikannan and R. Sivasamy, “Embedded Processes of a Markov Renewal Bulk Service Queue”, Asia Pacific Journal of Operational research, 11 (1), 51-65, 1997.
In article      
[11]  H.Takagi, “Queueing Analysis-A Foundation of Performance Ealuation, Vol. 3. Discrete-Time systems( Elsevier Science Publishers, Amsterdam)
In article      
[12]  H.Bruneel and B. Kim, “Discretetime models for communication systems including ATM. Kluwer Academic Publishers, 1993.
In article      CrossRef
[13]  R. Sivasamy and P M Kgosi, “An M/M+G/2 queue with heterogeneous machines operating under FCFS queue discipline, International Journal of Engineering and technical Research, (2014).
In article      
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn