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

**Thaga Keaogile**^{1}, **Adebayo Fatai Adewole**^{1,}, **Sivasamy Ramasamy**^{1}

^{1}Department of statistics, University of Botswana, Gaborone, Botswana

### Abstract

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 S_{1}=k slots for k=1,2, …∞, with mass function f_{1}(k)==Pr(S_{1}=k) = μ(1- μ) k-1 with mean rate 0<μ<1 or by server-2 with a general service time S_{2}= k for k=1,2, …, with mass function f_{2}(k)==Pr(S_{2}=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.

**Keywords:** poisson arrival, service time distribution, pgf of queue length distribution, waitime distribution, mean queue length and mean waiting time

*American Journal of Applied Mathematics and Statistics*, 2015 3 (2),
pp 54-58.

DOI: 10.12691/ajams-3-2-2

Received July 02, 2014; Revised March 01, 2015; Accepted March 06, 2015

**Copyright**© 2015 Science and Education Publishing. All Rights Reserved.

### 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

(1) |

**Service time distributions:*** *For customers serviced by server-1, their service time S

_{1}follows geometric distribution with mass function f

_{1}(k)=P(S

_{1}=k)=(1-)

^{k-1}

^{ }for k=1,2, …,with mean 1/μ or service rate μ (0<μ<1) per slot and hence the PGF of S

_{1}

_{ }and L

_{s}(z)= the PGF of the number of departures in a slot are respectively

(2) |

Let the service times S_{2} of customers serviced by server-2 follow a general distribution f_{2}(k)=P(S_{2}=k) with PGF is

(3) |

Both of these service times S_{1} and S_{2}_{ }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 f_{min}(k)=P(S_{min}k), where S_{min} = Min(S_{1}, S_{2}) and the PGF of S_{min} is F_{min}(z):

(4) |

The expected (*i.e.** *mean) values of S_{1}, S_{2} and of S_{min}_{ }variables are respectively E(S_{1}) =F_{1}’(z) ==(1/μ), E(S_{2}) =F_{2}’(1) and E(S_{min}) =F_{min}’(1). For example, if the service time S_{2} is a geometric random variable with mean (1/μ_{2}) then the mean of S_{min} can be obtained from (4)* i.e.*

It is then evident that the service rate of S_{min}_{ }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 f_{1}(k) and f_{2}(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 β= F_{2}’(1)= and F_{1}’(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 f_{2}(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 S_{2} of server-2 be Negative-binomial NB(α,β) random variable with mass function b(k; α, μ_{2})=P(S_{2}=k). If S_{2} 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 S_{2} is E(S_{2})= (α/β) and variance V(S_{2})=α(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 f_{1}(k) and f_{2}(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 μ_{2}and 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 F_{min}(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, N_{k}=N(t_{k}), of jobs left behind in the queue by the k^{th} departing job at the departure epoch ‘t_{k}’ forms a Markov Chain process{N_{k}} on the state space ={0,1,...}.

**2.1. PGF of {N**

_{k}}Let q_{j} 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 {q_{j} ; j=0, 1, ,... } be **V**(z) =

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

(5) |

and

(6) |

Let the respective z-transforms of the probability distributions {α_{j}} and {δ_{j}} be A_{min}(z) and A_{1}(z):

(7) |

and

(8) |

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 k^{th} embedded point be q_{ij}=P(N_{k} = j /N_{k-1}=i) for i, j . These transition probabilities will form the unit step transition probability matrix Q=(q_{ij}) as below:

(9) |

Thus equilibrium state probabilities at the departure instants are given by q_{j} = where q_{ij}^{n} represents the n-step probability of moving from state 'i to j'. Let **q**=(q_{0},q_{1} ,q_{2},…) be a row vector and let **e**=(1,1, …,1) be a column vector of unit elements of infinite order. Assume that A_{min}’(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:

(10) |

Multiplying the j^{th} (j=0, 1, 2, …) equation of **q**Q=**q** , of (10) by z^{j} and summing all the left-hand sides and the right-hand sides from j=0 to j=, we get the PGF (Probability generating Function) V_{min}(z) of the queue length distribution {q_{j}} of the sequence{N_{k}}.

(11) |

Since q_{1}= ρq_{0}, A_{min}'(1)<1, A_{1}'(1)=ρ and V(1)=1, we derive from (11) that

(12) |

Thus

(13) |

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

(14) |

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 V_{min}(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

(15) |

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 Q_{0}(z) and W_{0}(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 µ_{2}0, it is shown that

**Proof:** If (1/µ_{2})∞ as µ_{2}0 then F_{2}(z) cannot exist and thus which is replaced by a zero in F_{min}(z)=; this in turn proves that A_{min}((z))=F_{1}(1-λ+λz)=A_{1}(z). Proof of the lemma follows from replacing A_{min}(z) by A_{1}(z) in the PGF of the queue length distribution V_{min}(z) of (13) of the Geo()/ Geo()+G/2 since V_{min}(z)=

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

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

Let f_{max}(k)=P(S_{max}<k), where S_{1} and S_{2} denote the service times of server-1 and server-2 respectively as already defined and S_{max} = Max(S_{1}, S_{2}) and the PGF of T_{max} be F_{max}(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

(16) |

where π_{1} and π_{2 }are the probability values of choosing the service time PDFs f_{min}(k) and f_{max}(k) respectively. The corresponding z-transform of number of arrivals during the joint service PGF of f(k) is

(17) |

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

(18) |

Now on substituting A(z) of (17) in place of A_{min}(z) of (13), one can verify that V(z),the PGF of the queue length distribution of the sequence{N_{k}} (V(z) replaces V_{min}(z) of (13) and f(k) in place of f_{min}(k)) is

(19) |

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

Proof: Notice that F_{2}(1-μ)=μ_{2 }(1-μ)/(1-(1-μ)(1-μ_{2})=μ /(μ+μ_{2}- μ μ_{2}) and

If A_{1}’(1)<1, then ; hence the lemma.

* Conditional Average Waiting Time*(s): Let w

_{1}and w

_{2}be the mean waiting times corresponding to μ < μ

_{2}and μ>μ

_{2}values respectively. Thus w

_{1}=E(N)/λ when μ < μ

_{2}and w

_{2}=E(N)/λ when μ > μ

_{2}. Now E(N)=V’(1) from (19) is

(19) |

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 w_{2}< w_{1} 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) w_{1} is calculated fixing λ=0.48, μ=0.45 and μ_{2}=0.8 (geometric case) and w_{2} 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 w_{2}<w_{1} uniformly).

#### Table 1. Conditional Mean waiting times w_{1} when(λ=0.48,µ=0.45, µ_{2}=0.8) and w_{2} 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].

### References

[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 | |||