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₁ follows geometric distribution with mass function f₁(k)=P(S₁=k)=(1-)^k-1 for k=1,2, …,with mean 1/μ or service rate μ (0<μ<1) per slot and hence the PGF of S₁ and L_s(z)= the PGF of the number of departures in a slot are respectively

(2)

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

(3)

Both of these service times S₁ and S₂ 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_mink), where S_min = Min(S₁, S₂) and the PGF of S_min is F_min(z):

(4)

The expected (i.e. mean) values of S₁, S₂ and of S_min variables are respectively E(S₁) =F₁’(z) ==(1/μ), E(S₂) =F₂’(1) and E(S_min) =F_min’(1). For example, if the service time S₂ is a geometric random variable with mean (1/μ₂) 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 μ₁+ μ₂ –μ₁μ₂ 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₁(k) and f₂(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₂’(1)= and F₁’(1)= respectively. Thus the mean service rate of server-2 is μ₂=1/β. Letbe used in the sequel. It is remarked that closed form expression to r(k) can be obtained for particular cases of f₂(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₂ of server-2 be Negative-binomial NB(α,β) random variable with mass function b(k; α, μ₂)=P(S₂=k). If S₂ 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₂ is E(S₂)= (α/β) and variance V(S₂)=α(1-β)/β². The mean service rate μ₂=β/α, 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₁(k) and f₂(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/μ₂) (tends to ∞) then his service rate μ₂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,...}.

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₁(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₁(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ⁿ represents the n-step probability of moving from state 'i to j'. Let q=(q₀,q₁ ,q₂,…) 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 qQ=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₁= ρq₀, A_min'(1)<1, A₁'(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₀(z) and W₀(z) below:

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

Proof: If (1/µ₂)∞ as µ₂0 then F₂(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-λ+λz)=A₁(z). Proof of the lemma follows from replacing A_min(z) by A₁(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₁ and S₂ denote the service times of server-1 and server-2 respectively as already defined and S_max = Max(S₁, S₂) 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 π₁ and π₂ 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₂(1-μ)=μ₂ (1-μ)/(1-(1-μ)(1-μ₂)=μ /(μ+μ₂- μ μ₂) and

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

Conditional Average Waiting Time(s): Let w₁ and w₂ be the mean waiting times corresponding to μ < μ₂ and μ>μ₂ values respectively. Thus w₁=E(N)/λ when μ < μ₂ and w₂=E(N)/λ when μ > μ₂. 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 μ₂ of server-2 then w₂< w₁ with increasing values of π₁. For an illustration, assuming that the probability of serving a job simultaneously by both servers in the same slot is zero (i.e. µµ₂=0) w₁ is calculated fixing λ=0.48, μ=0.45 and μ₂=0.8 (geometric case) and w₂ is computed fixing λ=0.48, μ=0.8 and μ₂=0.45 (geometric case)while π₁ varies between 0.4 and 1 and these values are reported in Table-1 (which also ensures that w₂<w₁ uniformly).

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

Download as

PowerPoint Slide

Larger image(png format)

Tables index

Veiw figure

View current table in a new window

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 μ₂ of server-2.

As the analysis of the above Geo(λ)/ Geo(μ)+G(μ₂)/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 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