# A Two-Stage Model Queueing with No Waiting Line between Channels

Authors: Vedat Sağlam; Müjgan Zobu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We consider a new queuing model with sequential two stations (stages), single server at each station, where no queue is allowed at station 2 and with no restriction at station 1. There is a FCFS service discipline in which the input stream is Poisson having rateλ. The service time of any customer at server i (i=1,2) is exponential with parameter μi. The state probabilities and loss probability of this model are given. The performance measures are obtained and optimized, and, additionally, the model is simulated.   The simulation results, exact results, and optimal results of  the performance measures are numerically  computed  for different parameters.


---

## Body

## 1. Introduction

New models of queuing theory have been needed lately concerning the developments in areas such as production line, communication, and computer systems. One of these necessary models is for a tandem queuing system. Many important studies have been done in this area. The mean waiting time and the mean customer number at two tandem channels (servers) which are Poisson arrival and exponential service time were given in [1]. The mean customer number, distribution of waiting time, and the probabilities of various numbers of the tandem queuing system at every stage of the Poisson arrival and the exponential service time of the tandem queuing system were found in [2]. In [3], it was proved that if arrivals to the system are Poisson process with the parameter, then the output of this system is also Poisson process with a parameter λ. A more complicated example with network analysis was studied in [4]. In queuing theory, it is usually assumed that service channels are homogeneous. However, it is seen that in real queuing systems, service channels sometimes are heterogeneous. Understanding such systems is important for finding solutions to both theoretical and technical problems. Under the condition that the sum of service rates is fixed, homogeneous systems have been compared with the heterogeneous systems for performance measures in [5–9]. The measures of effectiveness for tandem queues with blocking were calculated according to an approximation method and simulated in [10]. The tandem queues with one server in the first queue, and n≥1 servers in the second queue, where the arrivals to the system with Poisson process having parameter λ and there is no waiting room between the two stages, were analyzed and some probabilities for the number of customers were found in [11]. In the literature usually, for some similar models to ours, blocked tandem queueing systems have been studied and probabilities of number of customers have been obtained. Approximate and simulation results of performance measures have been obtained. In our proposed model, there is no restriction for the first stage, there is no waiting room between both stages and no blocking (i.e., customers leave the system after having service in the first stage if the second stage is busy). Probabilities of being-nonbeing of customers in the first and second stages, performance measures, and the optimal values of these measures are theoretically obtained by analyzing our proposed method. Also, we have compared some results by obtaining simulation results.In real life, while there is waiting case in the service systems, because of obligations and urgency and unavailability of desired features, the loss may occur in the beginning of second stage as in our proposed model. Therefore, we have decided to construct such a model and analyze it. The following two examples can be proposed as potential applications of our model under some conditions.The following examples can be proposed as the applications of our model on some topics.(a)Fruit-Vegetable Packing Line. There is a company which exports fresh fruits and vegetables. This company has a product packing line which consists of two stages, for a special export fruit. The product comes to first stage for quality control. Later, if the product is not in the desirable size or quality, then it is taken away from the system (the loss occurs). The product is sent to the second stage to be packed with no waiting time, if it qualifies the desirable size and quality.(b)VoIP (Voice Over Internet Protocol). Internet telephony refers to communications services—voice, fax, SMS, and/or voice-messaging applications—that are transported via an IP network, rather than the public switched telephone network (PSTN). The steps involved in originating a VoIP telephone call are signalling and media channel setup, digitization of the analogy voice signal, encoding, packetization, and transmission as Internet Protocol (IP) packets over a packet-switched network. On the receiving side, similar steps (usually in the reverse order) such as reception of the IP packets, decoding of the packets, and digital-to-analogy conversion reproduce the original voice stream.More generally, the server transfers voice messaging to the recipient. In this system, the server is first service, the recipient is second service. If the recipient is busy, and then the server destroys voice messaging at that moment.


## 2. The Model

Letn1and n2be the number of customers in the first and second stages, respectively, at any time of t, including those being served, wheren1=0,1,2,…; n2=0,1.For stagei, let  ξi(t)be defined as follows:
(1)ξi(t)={n1,i=1,n2,i=2.
We can denote
(2)Pn1,n2(t)=Prob{ξ1(t)=n1,ξ2(t)=n2}.
The random process
(3){ξi(t):i=1,2;t≥0}
is a continuous-time two-dimensional Markov chain.  Forn≥1, the state space of this chain becomes
(4)E={(0,0),(0,1),(n,0),(n,0)}.
We wish to find the steady-state probability pn1,n2:
(5)pn1,n2=limt→∞Pn1,n2(t).
The usual procedure leads to the steady-state equations for this Markov chain:
(6)0=-λp00+μ2p10,(7)0=-(λ+μ2)p01+μ1p10+μ1p11,(8)0=-(λ+μ1)pn1,0+λpn1-1,0+μ2pn1,1,n1≥1,(9)0=-(λ+μ1+μ2)pn1,1+λpn1-1,1+μ1(pn1+1,0+pn1+1,0),n1≥1.
We define  ρi=λ/μifori=1,2andρ=λ/(μ1+μ2).


### 2.1. State Probabilities

The probabilitypn1 denotes the probability of finding n1 customers in the first stage at an arbitrary point in time (see [12]). We can write these as
(10)pn1=pn1,0+pn1,1=ρ1n1(1-ρ1),n1≥0,(11)p00+p01=1-ρ1.
Using this equation and (6), we obtain the following:
(12)p01=λ(1-ρ1)λ+μ2=(1-ρ1)ρ21+ρ2,p00=μ2λp01=1-ρ11+ρ2.
By substituting the expressionpn1+1 in (9), we get
(13)(λ+μ1+μ2)pn1,1=λpn1-1,1+μ1pn1+1,n1≥1.
Let us take a=ρ/(1+ρ)and choose pn1,1 a place to put yn1 in (13), for simplicity. In this case, the following equation can be obtained:
(14)yn1=ayn1-1+ayn1,n1≥1.
Both sides of (14) are divided into an1, and later, the index n1 is changed to k. Then, we sum this obtained value:
(15)yn1an1-y0=∑k=1n1pkak-1=ρ1(1-ρ1)(an1-ρ1n1)(1-(ρ1/a))an1,(16)pn1,1-an1p01=aρ1(1-ρ1)(an1-ρ1n1)a-ρ1,(17)pn1,1=aρ1(1-ρ1)(an1-ρ1n1)a-ρ1+(1-ρ1)ρ21+ρ2an1.
When the value  of  ain (17) is substituted, the following equation is obtained:
(18)pn1,1=(1-ρ1)ρ21+ρ2ρ1n1.We get the probabilitypn1,0 from (10) and (18):
(19)pn1,0=(1-ρ1)1+ρ2ρ1n1.


### 2.2. Loss Probability

The customer’s loss probability is given as(20)pL=∑n1=0∞pn1,1=ρ21+ρ2.
In other way, the formula (20) can be obtained from “Erlang’s loss formula” or “Erlang’s B formula” for the M/M/c/c queue. In [13], it is denoted as B(c,ρ2)and  formulated as the follows:
(21)B(c,ρ2)=ρ2/c!∑n=0cρ2n/n!,
where ρ2 is the utilization factor. Substituting c=1in (21), we have (20).


## 2.1. State Probabilities

The probabilitypn1 denotes the probability of finding n1 customers in the first stage at an arbitrary point in time (see [12]). We can write these as
(10)pn1=pn1,0+pn1,1=ρ1n1(1-ρ1),n1≥0,(11)p00+p01=1-ρ1.
Using this equation and (6), we obtain the following:
(12)p01=λ(1-ρ1)λ+μ2=(1-ρ1)ρ21+ρ2,p00=μ2λp01=1-ρ11+ρ2.
By substituting the expressionpn1+1 in (9), we get
(13)(λ+μ1+μ2)pn1,1=λpn1-1,1+μ1pn1+1,n1≥1.
Let us take a=ρ/(1+ρ)and choose pn1,1 a place to put yn1 in (13), for simplicity. In this case, the following equation can be obtained:
(14)yn1=ayn1-1+ayn1,n1≥1.
Both sides of (14) are divided into an1, and later, the index n1 is changed to k. Then, we sum this obtained value:
(15)yn1an1-y0=∑k=1n1pkak-1=ρ1(1-ρ1)(an1-ρ1n1)(1-(ρ1/a))an1,(16)pn1,1-an1p01=aρ1(1-ρ1)(an1-ρ1n1)a-ρ1,(17)pn1,1=aρ1(1-ρ1)(an1-ρ1n1)a-ρ1+(1-ρ1)ρ21+ρ2an1.
When the value  of  ain (17) is substituted, the following equation is obtained:
(18)pn1,1=(1-ρ1)ρ21+ρ2ρ1n1.We get the probabilitypn1,0 from (10) and (18):
(19)pn1,0=(1-ρ1)1+ρ2ρ1n1.


## 2.2. Loss Probability

The customer’s loss probability is given as(20)pL=∑n1=0∞pn1,1=ρ21+ρ2.
In other way, the formula (20) can be obtained from “Erlang’s loss formula” or “Erlang’s B formula” for the M/M/c/c queue. In [13], it is denoted as B(c,ρ2)and  formulated as the follows:
(21)B(c,ρ2)=ρ2/c!∑n=0cρ2n/n!,
where ρ2 is the utilization factor. Substituting c=1in (21), we have (20).


## 3. The Measures of Performance and Optimization of Performance Measures

### 3.1. The Mean Sojourn Time

LetT be a random variable that describes the sojourn time of customers in the system. Using the law of total expectation, we can write is as follows
(22)E(T)=E(T∣A)P(A)+E(T∣A-)P(A-),
where P(A) is the probability of the loss of a customer. Now it is clear that
(23)E(T∣A)=1μ1-λ,E(T∣A-)=1μ1-λ+1μ2.
Thus,
(24)E(T)=μ1+μ2(μ1-λ)(μ2+λ).
Our main results about the problem of minimizing the mean sojourn time can be explained by the following theorem.Theorem 1.
If sum of two service ratesμ1+μ2=μis fixed, then the mean sojourn time of this tandem system attains its minimum value forμ1=μ/2+λ andμ2=μ/2-λ.Proof.
We will prove the theorem by using the following inequality:(25)(∏I˙=1mai)1/m≤1m∑i=1mai,∀ai>0,∀m∈ℤ+.
From inequality (25), we have
(26)1(μ1-λ)(μ2+λ)≥4μ2.
If we replace  the expressionsμ1+μ2=μand4/μ2in equality (24), we obtain the minimum value of E(T)as follows:
(27)minE(T)=4μ,
where the equality (27) is provided with μ1=μ/2+λ andμ2=μ/2-λ.


### 3.2. The Mean Number of Customers

LetNbe the random variable that describes the number of customers in the system:(28a)E(N)=∑n1=0∞∑n2=01(n1+n2)pn1,n2=λ(μ1+μ2)(μ1-λ)(μ2+λ),
or
(28b)E(N)=λE(T).The mean number of customers in the system is optimized from Theorem1 and the equality (28b) as below:
(29)minE(N)=λminE(T)=4λμ.
The independence of the number of customers can be expressed by the following theorem.Theorem 2.
If the random variablesN1 andN2 are taken as the number of customers in the first and second stages, respectively, then N1 and N2 are independent random variables.Proof.
The joint probability mass functions ofN1 andN2 random variables is
(30)pn1,n2=P(N1=n1,N2=n2),n1=0,1,2,…;n2=0,1.
Ifn2=0 and (n2=1) are substituted in (30), the equations (19) and (18) are obtained, respectively.
The marginal probability mass function ofN1 is given as (10).
The marginal probability mass function ofN2 is obtained from Erlang’s B formula or (20):
(31)p0′=P(N2=0)=11+ρ2,(32)p1′=P(N2=1)=ρ21+ρ2,(33)pn1,n2=pn1pn2′,n1=0,1,2,…;n2=0,1.
If (10) and (31) are substituted in (30), the equation (19) is obtained, and if (10) and (32) are substituted in (30),  the equation (18) is  obtained. Thus, the independence ofN1 and N2 has been demonstrated.


## 3.1. The Mean Sojourn Time

LetT be a random variable that describes the sojourn time of customers in the system. Using the law of total expectation, we can write is as follows
(22)E(T)=E(T∣A)P(A)+E(T∣A-)P(A-),
where P(A) is the probability of the loss of a customer. Now it is clear that
(23)E(T∣A)=1μ1-λ,E(T∣A-)=1μ1-λ+1μ2.
Thus,
(24)E(T)=μ1+μ2(μ1-λ)(μ2+λ).
Our main results about the problem of minimizing the mean sojourn time can be explained by the following theorem.Theorem 1.
If sum of two service ratesμ1+μ2=μis fixed, then the mean sojourn time of this tandem system attains its minimum value forμ1=μ/2+λ andμ2=μ/2-λ.Proof.
We will prove the theorem by using the following inequality:(25)(∏I˙=1mai)1/m≤1m∑i=1mai,∀ai>0,∀m∈ℤ+.
From inequality (25), we have
(26)1(μ1-λ)(μ2+λ)≥4μ2.
If we replace  the expressionsμ1+μ2=μand4/μ2in equality (24), we obtain the minimum value of E(T)as follows:
(27)minE(T)=4μ,
where the equality (27) is provided with μ1=μ/2+λ andμ2=μ/2-λ.


## 3.2. The Mean Number of Customers

LetNbe the random variable that describes the number of customers in the system:(28a)E(N)=∑n1=0∞∑n2=01(n1+n2)pn1,n2=λ(μ1+μ2)(μ1-λ)(μ2+λ),
or
(28b)E(N)=λE(T).The mean number of customers in the system is optimized from Theorem1 and the equality (28b) as below:
(29)minE(N)=λminE(T)=4λμ.
The independence of the number of customers can be expressed by the following theorem.Theorem 2.
If the random variablesN1 andN2 are taken as the number of customers in the first and second stages, respectively, then N1 and N2 are independent random variables.Proof.
The joint probability mass functions ofN1 andN2 random variables is
(30)pn1,n2=P(N1=n1,N2=n2),n1=0,1,2,…;n2=0,1.
Ifn2=0 and (n2=1) are substituted in (30), the equations (19) and (18) are obtained, respectively.
The marginal probability mass function ofN1 is given as (10).
The marginal probability mass function ofN2 is obtained from Erlang’s B formula or (20):
(31)p0′=P(N2=0)=11+ρ2,(32)p1′=P(N2=1)=ρ21+ρ2,(33)pn1,n2=pn1pn2′,n1=0,1,2,…;n2=0,1.
If (10) and (31) are substituted in (30), the equation (19) is obtained, and if (10) and (32) are substituted in (30),  the equation (18) is  obtained. Thus, the independence ofN1 and N2 has been demonstrated.


## 4. Numerical Results

The random arrivals and service times were generated from exponential distribution as seconds by using MATLAB 7.10.0 (R2010a) programming for this proposed model. The number of customers taken was 10000 and was performed in three iterations. Performance measures are calculated for different values ofρi(i=1,2) and three different iterations steps, that is, 100, 1000, and 5000. These results were shown in Tables 1, 2, and 3.Table 1
Forλ=0.30,μ1=0.80;μ2=1.00.
Iteration number
Simulation results
Exact results
Optimal results
E
(
T
)
E
(
N
)
E
(
T
)
E
(
N
)
E
(
T
)
E
(
N
)
100
2.8163
0.8452
2.7692
0.8308
2.2222
0.6667
1000
2.8111
0.8433
2.7692
0.8308
2.2222
0.6667
5000
2.8124
0.8436
2.7692
0.8308
2.2222
0.6667Table 2
Forλ=0.1,μ1=0.9;μ2=0.9.
Iteration number
Simulation results
Exact results
Optimal results
E
(
T
)
E
(
N
)
E
(
T
)
E
(
N
)
E
(
T
)
E
(
N
)
100
2.2661
0.2263
2.2500
0.2250
2.2220
0.2222
1000
2.2599
0.2261
2.2500
0.2250
2.2220
0.2222
5000
2.2500
0.2260
2.2500
0.2250
2.2220
0.2222Table 3
Forλ=0.01,μ1=0.6;μ2=0.7.
Iteration number
Simulation results
Exact results
Optimal results
E
(
T
)
E
(
N
)
E
(
T
)
E
(
N
)
E
(
T
)
E
(
N
)
100
3.1042
0.0311
3.1034
0.0310
3.0769
0.0308
1000
3.1034
0.0310
3.1034
0.0310
3.0769
0.0308
5000
3.1043
0.0310
3.1034
0.0310
3.0769
0.0308


## 5. Conclusions

A new queuing discipline is given for a Markov model which consists of two consecutive channels and no waiting line between channels. In this model, steady-state equations, the mean sojourn time, the mean number of customers, and loss probability are obtained. Additionally, two theorems are given which are about optimization of performance measures and the independent of the number of customers, respectively. Performance measures are calculated for different values ofρi(i=1,2) and for three different iterations steps, that is, 100, 1000, and 5000. Moreover, results of these measures are compared in the tables above. It has been seen that the simulation results approximated the theoretical results. Although the iteration number is increased, the simulation results of performance measures have not changed. However, as ρi(i=1,2) converges to zero, both the simulation results and exact results approximately are equal to optimal results. Thus, it is said that our proposed queueing model operates well.For further research, a model, in which a customer who completed his service in channel 1, blocks channel 1 with probabilityπor leaves the system with probability 1-πwhile channel 2 is busy, can be studied.



---

*Source: 679369-2013-06-04.xml*