# The Analysis, Optimization, and Simulation of a Two-Stage Tandem Queueing Model with Hyperexponential Service Time at Second Stage

Authors: Vedat Sağlam; Murat Sağır; Erdinç Yücesoy; Müjgan Zobu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The aim of this paper is to analyze a tandem queueing model with two stages. The arrivals to the first stage are Poisson stream and the service time at this stage is exponential. There is no waiting room at first stage. The service time is hyperexponential and no waiting is allowed at second stage. The transition probabilities and loss probabilities of this model are obtained. In addition, the loss probability at second stage is optimized. Performance measures and the variance of the numbers of customers of this tandem queueing model are found. It is seen that the numbers of customers in first stage and second stage are dependent. Finally we have simulated this queueing model. For different values of parameters, exact values, simulated values, and optimal values of obtained performance measures of this model are numerically shown in tables and graphs.


---

## Body

## 1. Introduction

Queueing systems and modeling of these systems have many uses in production lines, service facilities, telecommunication, computer sciences, transportation, and so forth. The main interest in queueing modeling is that it allows us to process mathematical analysis. Hence the analysis gives us the ability to obtain important properties such as measures of performances of considered models. There follows then optimization of these measures. One of important study areas in Queueing Theory is the tandem queues. Many various important studies are done on tandem queues. Niu gave an upper bound for the stationary expected delay at second server for a sequence of two queues in tandem [1]. Some moment results for certain tandem and multiple-server queues are studied by Wolfson [2]. Ohno and Ichiki discussed the use of modified policy iteration algorithms to find the optimal control for the service rate for a tandem queueing system in [3]. Analysis for the steady state of a two-stage tandem queueing with single server is given by [4]. Scheduling service time in tandem queues is studied in [5]. Ziedins showed that, for some simple service time distributions with support on two points, the throughput can be calculated exactly and that it is always optimal to allocate the capacity as uniformly as possible, even when blocking occurs, in [6]. The moments in tandem queues are widely studied in [7]. A study, on control of a single-server tandem queueing system, is given by [8]. Knessel and Tier considered a diffusion model for two tandem queues with general renewal input [9]. Marin and Bulo studied explicit solutions for queues with hypoexponential service time and they gave applications to product form analysis in [10]. The queues with phase-type distributions are widely investigated by [11]. Throughout maximization for tandem lines is studied by [12]. Recently, performance analysis of tandem queues with small buffers is studied [13] and a paper on a tandem queueing model with parallel phases is given by [14] in which a numerical example is performed. In this paper we analyze a tandem queueing model in which the second stage has hyperexponential distribution. The arrivals to the first stage of the queue are Poisson-distributed and the service time at this stage has exponential distribution. There is no waiting room at first stage of the queue. The service time is hyperexponentially distributed and no waiting is allowed at second stage of the queue. The transition probabilities and loss probabilities of this model are obtained. The loss probability at second stage is optimized. The measures of performances are obtained. We also show that the numbers of customers in first and second stages are dependent. Furthermore this queueing model is simulated. For different values of parameters, exact values, simulated values, and optimal values of obtained performance measures of this model are numerically shown in tables and graphs. In simulation, it is seen that the simulation results tend to exact results after 10000 iteration steps. This queueing model is an extended model of the one studied in [14]. Choosing α1=α2=1/2 and μ1=μ2 gives the model given in [14].


## 2. The Definition of Model

A new tandem queueing discipline is investigated in which the customers arrive to system withλ parameter Poisson stream. In the first stage, there is a single server with exponential distributed service time having rate μ. No waiting is allowed in front of this single server. Hence the first loss occurs. The service time at second stage is hyperexponentially distributed. After completing service in first stage, the customers proceed to second stage. At second stage, the customers choose the first server or second server with probabilities α1 and α2=1-α1, respectively. The service time parameters of servers at second stage are μ1 and μ2. After having service at first stage if any of two servers in second stage is busy then the customers leave the system. In this case second loss occurs.Now we give a formal mathematical definition of this queueing discipline as below.LetX1t, X2t, and X3t be the numbers of customers in first stage, in the first server of second stage, and in the second server of second stage, respectively, where T=0,∞) and t∈T. We define a 3D Markov chain {X1(t),X2(t),X3(t);T}. And the state space of this chain is (1)T=0,0,0,0,0,1,0,1,0,1,0,0,1,1,0,1,0,1,where (2)Pk1,k2,k3t=ProbX1t=k1,X2t=k2,X3t=k3;T,k1,k2,k3∈T.Assuming that the limit distribution exists, we need to find the steady-state probabilities πk1,k2,k3(3)limt→∞⁡Pk1,k2,k3t=πk1,k2,k3,limt→∞⁡Pk1,k2,k3′t=0.


### 2.1. Difference Equations of the 3D Markov Chain

We have the difference equations of this Markov chain as given in(4)-λπ000+μ1π010+μ2π001=0,-λ+μ2π001+α2μπ100+μπ101=0,-λ+μ1π010+α1μπ100+μπ110=0,-μπ100+λπ000+μ1π110+μ2π101=0,-μ+μ1π110+λπ010=0,-μ+μ2π101+λπ001=0.


## 2.1. Difference Equations of the 3D Markov Chain

We have the difference equations of this Markov chain as given in(4)-λπ000+μ1π010+μ2π001=0,-λ+μ2π001+α2μπ100+μπ101=0,-λ+μ1π010+α1μπ100+μπ110=0,-μπ100+λπ000+μ1π110+μ2π101=0,-μ+μ1π110+λπ010=0,-μ+μ2π101+λπ001=0.


## 3. Transition Probabilities

By solving the equation system above, we have the transition probabilities as follows:(5)π000=1/λα1μμ+μ1/λ+μ+μ1+α2μμ+μ2/λ+μ+μ21+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2,π100=11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2,π010=α1μμ+μ1/μ1λ+μ+μ11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2,π001=α2μμ+μ2/μ2λ+μ+μ21+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2,π101=λα2μ/μ2λ+μ+μ21+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2,π110=α1λμ/μ1λ+μ+μ11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2.


### 3.1. The Dependence of Number of Customers at First and Second Stages

Considering the first stage, inM/M/c/c queue if we take c=1, then (6)π0=μλ+μ,π1=λλ+μare obtained in [15]. Where π0 is the probability that the system is idle and π1 is the probability the system is busy. Because there is a probability of loss at first stage, the customers can not arrive to second stage with λ rate. Therefore the transition probabilities at second stage are found with λeffective=μ/λ+μλ rate. Then,(7)π00=11+α1λμ/μ1λ+μ+α2λμ/μ2λ+μ,π10=α1λμ/μ1λ+μ1+α1λμ/μ1λ+μ+α2λμ/μ2λ+μ,π01=α2λμ/μ2λ+μ1+α1λμ/μ1λ+μ+α2λμ/μ2λ+μ.In this manner, for example, since π100≠π1·π00, the transition probability is written as(8)πk1,k2,k3≠πk1·πk2,k3.As a result, the numbers of customers at first and second stages are dependent on each other.


### 3.2. Loss Probabilities

There are two loss probabilities in this model. Now we go on by calculating these probabilities:(a)
LetPL1 denote the loss probability at first stage. Then,(9)PL1=π100+π101+π110=1+λα2μ/μ2λ+μ+μ2+α1λμ/μ1λ+μ+μ11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2=λλ+μ.It is easy to see that this probability depends onλ and μ parameters only. Hence the loss probability at first stage is independent of the parameters μ1 and μ2 of second stage.(b)
LetPL2 denote the loss probability at second stage. This probability is showed as follows.To be loss at second stage, the second stage must be busy under condition that the first stage is busy. Considering this, the following events are defined:E
1 is the event that first stage is busy.E
2 is the event that second stage is busy.Consider(10)PL2=PE2∣E1=PE2∩E1PE1=π101+π110π1,where π1=π100+π101+π110.The following theorem on optimization ofPL2 is given.Theorem 1.
Fixingα1=α2=1/2 and μ1+μ2=c (c is constant), the minimum PL2 is obtained when μ1=μ2=c/2.Proof.
P
L
2 is rewritten as follows: (11)PL2=α1λμ/μ1λ+μ+μ1+λα2μ/μ2λ+μ+μ21+α1λμ/μ1λ+μ+μ1+λα2μ/μ2λ+μ+μ2.Taking α1=α2=1/2 in (11), PL2 is written as below:(12)PL2=11+2/λμ/μ1λ+μ+μ1+λμ/μ2λ+μ+μ2.To simplify, we write (13)Σ=λμμ1λ+μ+μ1+λμμ2λ+μ+μ2.To make PL2 minimum, Σ must be minimum:(14)Σ=λμλ+μμ1+μ2+μ1+μ22-2μ1μ2μ1μ22+μ1μ2λ+μ+λ+μμ1μ2μ1+μ2.Equation (13) is written under condition μ1+μ2=c as follows: 14′Σ=λμλ+μc+c2-2μ1μ2μ1μ22+μ1μ2λ+μc+1.The values which make 14′ minimum are μ1=μ2=c/2.
Therefore the probabilityPL2 has its minimum value when the μ1μ2 product is maximum, that is, when μ1=μ2=c/2:(15)minα1=α2=1/2μ1=μ2=c/2⁡PL2=11+cλ+μ+c/2/2λμ.


## 3.1. The Dependence of Number of Customers at First and Second Stages

Considering the first stage, inM/M/c/c queue if we take c=1, then (6)π0=μλ+μ,π1=λλ+μare obtained in [15]. Where π0 is the probability that the system is idle and π1 is the probability the system is busy. Because there is a probability of loss at first stage, the customers can not arrive to second stage with λ rate. Therefore the transition probabilities at second stage are found with λeffective=μ/λ+μλ rate. Then,(7)π00=11+α1λμ/μ1λ+μ+α2λμ/μ2λ+μ,π10=α1λμ/μ1λ+μ1+α1λμ/μ1λ+μ+α2λμ/μ2λ+μ,π01=α2λμ/μ2λ+μ1+α1λμ/μ1λ+μ+α2λμ/μ2λ+μ.In this manner, for example, since π100≠π1·π00, the transition probability is written as(8)πk1,k2,k3≠πk1·πk2,k3.As a result, the numbers of customers at first and second stages are dependent on each other.


## 3.2. Loss Probabilities

There are two loss probabilities in this model. Now we go on by calculating these probabilities:(a)
LetPL1 denote the loss probability at first stage. Then,(9)PL1=π100+π101+π110=1+λα2μ/μ2λ+μ+μ2+α1λμ/μ1λ+μ+μ11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2=λλ+μ.It is easy to see that this probability depends onλ and μ parameters only. Hence the loss probability at first stage is independent of the parameters μ1 and μ2 of second stage.(b)
LetPL2 denote the loss probability at second stage. This probability is showed as follows.To be loss at second stage, the second stage must be busy under condition that the first stage is busy. Considering this, the following events are defined:E
1 is the event that first stage is busy.E
2 is the event that second stage is busy.Consider(10)PL2=PE2∣E1=PE2∩E1PE1=π101+π110π1,where π1=π100+π101+π110.The following theorem on optimization ofPL2 is given.Theorem 1.
Fixingα1=α2=1/2 and μ1+μ2=c (c is constant), the minimum PL2 is obtained when μ1=μ2=c/2.Proof.
P
L
2 is rewritten as follows: (11)PL2=α1λμ/μ1λ+μ+μ1+λα2μ/μ2λ+μ+μ21+α1λμ/μ1λ+μ+μ1+λα2μ/μ2λ+μ+μ2.Taking α1=α2=1/2 in (11), PL2 is written as below:(12)PL2=11+2/λμ/μ1λ+μ+μ1+λμ/μ2λ+μ+μ2.To simplify, we write (13)Σ=λμμ1λ+μ+μ1+λμμ2λ+μ+μ2.To make PL2 minimum, Σ must be minimum:(14)Σ=λμλ+μμ1+μ2+μ1+μ22-2μ1μ2μ1μ22+μ1μ2λ+μ+λ+μμ1μ2μ1+μ2.Equation (13) is written under condition μ1+μ2=c as follows: 14′Σ=λμλ+μc+c2-2μ1μ2μ1μ22+μ1μ2λ+μc+1.The values which make 14′ minimum are μ1=μ2=c/2.
Therefore the probabilityPL2 has its minimum value when the μ1μ2 product is maximum, that is, when μ1=μ2=c/2:(15)minα1=α2=1/2μ1=μ2=c/2⁡PL2=11+cλ+μ+c/2/2λμ.


## 4. Measures of Performances

### 4.1. The Mean Number of Customers in the System

If we denote the number of customers in the system byN, then we calculate the mean number of customers as follows:(16)EN=∑k1∑k2∑k3k1+k2+k3πk1,k2,k3=π001+π010+π100+2π110+π101=1+α1μμ+μ1/μ1λ+μ+μ1+α2μμ+μ2/μ2λ+μ+μ2+2λα2μ/μ2λ+μ+μ2+2α1λμ/μ1λ+μ+μ11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2.


### 4.2. The Variance of Customers Number in the System

Consider(17)VarN=EN2-EN2,EN2=∑k1∑k2∑k3k1+k2+k32πk1,k2,k3=π001+π010+π100+4π110+π101=1+α1μμ+μ1/μ1λ+μ+μ1+α2μμ+μ2/μ2λ+μ+μ2+4λα2μ/μ2λ+μ+μ2+4α1λμ/μ1λ+μ+μ11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2,VarN=1+α1μμ+μ1/μ1λ+μ+μ1+α2μμ+μ2/μ2λ+μ+μ2+4λα2μ/μ2λ+μ+μ2+4α1λμ/μ1λ+μ+μ11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2-1+α1μμ+μ1/μ1λ+μ+μ1+α2μμ+μ2/μ2λ+μ+μ2+2λα2μ/μ2λ+μ+μ2+2α1λμ/μ1λ+μ+μ11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2.


### 4.3. Mean Waiting Time in the System

Letτ be the waiting time in the system. Using total expectation in [16], we have(18)Eτ=PAEτ∣A+PA-Eτ∣A-,where A is the event of the loss at first stage. So,(19)PA-=1-PAand the conditional expectations are written as (20)EτA=1μ,EτA-=1μ+α1μ1+α2μ2.It follows then that (21)PA=PL2.Now the mean waiting time of a customer in the system is calculated as given in(22)Eτ=1μ+α1/μ1+α2/μ21+α1λμ/μ1λ+μ+μ1+λα2μ/μ2λ+μ+μ2.


## 4.1. The Mean Number of Customers in the System

If we denote the number of customers in the system byN, then we calculate the mean number of customers as follows:(16)EN=∑k1∑k2∑k3k1+k2+k3πk1,k2,k3=π001+π010+π100+2π110+π101=1+α1μμ+μ1/μ1λ+μ+μ1+α2μμ+μ2/μ2λ+μ+μ2+2λα2μ/μ2λ+μ+μ2+2α1λμ/μ1λ+μ+μ11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2.


## 4.2. The Variance of Customers Number in the System

Consider(17)VarN=EN2-EN2,EN2=∑k1∑k2∑k3k1+k2+k32πk1,k2,k3=π001+π010+π100+4π110+π101=1+α1μμ+μ1/μ1λ+μ+μ1+α2μμ+μ2/μ2λ+μ+μ2+4λα2μ/μ2λ+μ+μ2+4α1λμ/μ1λ+μ+μ11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2,VarN=1+α1μμ+μ1/μ1λ+μ+μ1+α2μμ+μ2/μ2λ+μ+μ2+4λα2μ/μ2λ+μ+μ2+4α1λμ/μ1λ+μ+μ11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2-1+α1μμ+μ1/μ1λ+μ+μ1+α2μμ+μ2/μ2λ+μ+μ2+2λα2μ/μ2λ+μ+μ2+2α1λμ/μ1λ+μ+μ11+μ/λ+α1μ/μ1+α2μ/μ2-μα1/λ+μ+μ1+α2/λ+μ+μ2.


## 4.3. Mean Waiting Time in the System

Letτ be the waiting time in the system. Using total expectation in [16], we have(18)Eτ=PAEτ∣A+PA-Eτ∣A-,where A is the event of the loss at first stage. So,(19)PA-=1-PAand the conditional expectations are written as (20)EτA=1μ,EτA-=1μ+α1μ1+α2μ2.It follows then that (21)PA=PL2.Now the mean waiting time of a customer in the system is calculated as given in(22)Eτ=1μ+α1/μ1+α2/μ21+α1λμ/μ1λ+μ+μ1+λα2μ/μ2λ+μ+μ2.


## 5. The Simulation of the Model

In this section we give the simulation of the queueing model which we analyze. The mean waiting time in the system and the loss probabilities are obtained by performing some number of iterationsn=1000,5000,10000,20000 and the simulation results are given together with exact values in tables. Furthermore, it is seen that the simulation results tend to exact values.The exact and simulation values ofPL2 in Tables 1, 2, 3, and 4 are given in Figure 1. Also the exact values of PL2 are the initial values of this figure.Table 1
Forλ=0.34, μ=0.70, α1=0.40, α2=0.60, μ1=0.30, and μ2=0.50.
Iterations number
Simulation result
Exact result
P
L
1
P
L
2
E
(
τ
)
P
L
1
P
L
2
E
(
τ
)
1000
0.317000
0.304539
3.188647
0.326923
0.296899
3.209761
5000
0.321400
0.303566
3.196287
0.326923
0.296899
3.209761
10000
0.320800
0.302709
3.196279
0.326923
0.296899
3.209761
20000
0.329000
0.293592
3.230218
0.326923
0.296899
3.209761Table 2
Forλ=0.34, μ=0.70, α1=0.60, α2=0.40, μ1=0.30, and μ2=0.50.
Number of iterations
Simulation result
Exact result
P
L
1
P
L
2
E
(
τ
)
P
L
1
P
L
2
E
(
τ
)
1000
0.327000
0.329866
3.290284
0.326923
0.323804
3.321921
5000
0.329200
0.333930
3.316146
0.326923
0.323804
3.321921
10000
0.327900
0.323613
3.331552
0.326923
0.323804
3.321921
20000
0.332700
0.323842
3.310026
0.326923
0.323804
3.321921Table 3
Forλ=0.34, μ=0.70, α1=α2=0.50, μ1=0.30, and μ2=0.50.
Number of iterations
Simulation result
Exact result
P
L
1
P
L
2
E
(
τ
)
P
L
1
P
L
2
E
(
τ
)
1000
0.334000
0.318318
3.291144
0.326923
0.310614
3.266935
5000
0.324600
0.307373
3.281803
0.326923
0.310614
3.266935
10000
0.333100
0.315190
3.258010
0.326923
0.310614
3.266935
20000
0.325450
0.308354
3.270625
0.326923
0.310614
3.266935Table 4
Forλ=0.34, μ=0.70, α1=α2=0.50, μ1=0.40, and μ2=0.40.
Number of iterations
Simulation result
Exact result
P
L
1
P
L
2
E
(
τ
)
P
L
1
P
L
2
E
(
τ
)
1000
0.312000
0.289244
3.148811
0.326923
0.292383
3.197613
5000
0.332600
0.301468
3.241776
0.326923
0.292383
3.197613
10000
0.329800
0.298717
3.171507
0.326923
0.292383
3.197613
20000
0.323800
0.293848
3.169682
0.326923
0.292383
3.197613Figure 1
The exact and simulation values ofPL2.In this figure, we see that as the number of iterations increases, the simulation values ofPL2 converge to its exact values. Furthermore under condition α1=α2, PL2 has its minimum value when μ1=μ2 and it seen in Figure 1, as is shown in Table 4.


## 6. Conclusions

A two-stage tandem queueing model is analyzed. The transition probabilities and loss probabilities are given and a theorem is given for the minimization of the loss probability at second stage. This queueing model is simulated for 1000, 5000, 10000, and 20000 iteration steps. The obtained simulation results are compared to exact results and it is shown in Tables1, 2, 3, and 4 and Figure 1 that the simulation results are close to exacts results. Exact values and simulation results given in Tables 3 and 4 numerically satisfy Theorem 1. These results are also shown in Figure 1.For further studies on this queueing model, this model can be extended by adding some servers, increasing the capacities of the servers, and letting queues in front of the servers.



---

*Source: 165219-2015-11-11.xml*