Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

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

Thaga Keaogile, Adebayo Fatai Adewole*, Sivasamy Ramasamy

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₁=k slots for k=1,2, …∞, with mass function f₁(k)==Pr(S₁=k) = μ(1- μ) k-1 with mean rate 0<μ<1 or by server-2 with a general service time S₂= k for k=1,2, …, with mass function f₂(k)==Pr(S₂=k) with mean service time is or mean service rate μ₂=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

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

Citation: Thaga Keaogile, Adebayo Fatai Adewole, Sivasamy Ramasamy, Geo (λ)/ Geo (μ) +G/2 Queues with Heterogeneous Servers Operating under FCFS Queue Discipline. American Journal of Applied Mathematics and Statistics, 3 (2). 54-58. January 2015. doi:10.12691/ajams-3-2-2

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

[picture] | (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 Ls(z)= the PGF of the number of departures in a slot are respectively

[picture] | (2)

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

[picture] | (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 fmin(k)=P(Smink), where Smin = Min(S₁, S₂) and the PGF of Smin is Fmin(z):

[picture] | (4)

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

It is then evident that the service rate of Smin 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 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 f₁(k). Since the arrivals come from a Geometric process at rate λ, we get, for j=1, 2, 3, ... that

[picture] | (5)

and

[picture] | (6)

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

[picture] | (7)

and

[picture] | (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 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:

[picture] | (9)

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=(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 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:

[picture] | (10)

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}.

[picture] | (11)

Since q₁= ρq₀, Amin'(1)<1, A₁'(1)=ρ and V(1)=1, we derive from (11) that

[picture] | (12)

Thus

[picture] | (13)

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

[picture] | (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 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

[picture] | (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 Fmin(z)=; this in turn proves that Amin((z))=F₁(1-λ+λz)=A₁(z). Proof of the lemma follows from replacing Amin(z) by A₁(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 S₁ and S₂ denote the service times of server-1 and server-2 respectively as already defined and Smax = Max(S₁, S₂) 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

[picture] | (16)

where π₁ 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

[picture] | (17)

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

[picture] | (18)

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

[picture] | (19)

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

Proof: Notice that F₂(1-μ)=μ2 (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

[picture] | (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

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.

3.1. Conclusion

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.
[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.
[3]   | P. Hoksad, “On the steady state solution of the M/G/2 queue”, Advanced applied probability}, 11, 240-255. 1979.
[4]   | D. Efrosinin, “Controlled Queueing Systems with Heterogeneous Servers: Dynamic Optimization and Monotonicity Properties of Optimal Control Policies in Multiserver Heterogeneous Queues”, 2008.
[5]   | B.Krishnamoorthy, “On Poisson Queue with two Heterogeneous Servers”, Operations Research, 2 (3), 321-330, 1962.
[6]   | V. P. Singh “Two-Server Markovian Queues with Balking: Heterogeneous vs. Homogeneous Servers”, Operations Research, 18 (1), 145-159, 1968.
[7]   | J. H. Kim, H.-S. Ahn, and R. Righter, “Managing queues with heterogeneous servers”, J. Appl. Probab., 48 (2), 435-452, 2011.
[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.
[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.
[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.
[11]   | H.Takagi, “Queueing Analysis-A Foundation of Performance Ealuation, Vol. 3. Discrete-Time systems( Elsevier Science Publishers, Amsterdam)
[12]   | H.Bruneel and B. Kim, “Discretetime models for communication systems including ATM. Kluwer Academic Publishers, 1993.
[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).