Parallel lines are often used to increase production rate in many manufacturing systems where the main line splits into several lines in parallel, and after some operations, they merge into a main line again. Queueing networks with finite buffers have been widely used for modeling and analyzing manufacturing systems. This paper provides an approximation technique for multiserver twostage networks with merge configuration and blocking which will be a building block for analysis of general manufacturing systems with parallel lines and merge configuration. The main idea of the method is to decompose the original system into subsystems that have two service stations with multiple servers, two buffers and external arrivals to the second stage are allowed. The subsystems are modeled by level dependent quasibirthanddeath (LDQBD) process.
AMS Mathematics Subject Classification : 60K25, 68M20.
1. Introduction
A complex manufacturing system usually consists of one or more complex operations, such as assembly, disassembly, split, merge, rework, parallel, feedforward and scrap, etc.
[10]
. Parallel lines are often used to increase production rate in many manufacturing systems. In parallel systems, the main line splits into several lines in parallel, and after some operations, they merge into a main line again. For example, three types of lens module installed in smart phone are assembled in their own assembly line. After finishing assembly, all lens modules are sent to the resolution inspection machines which can inspect all types of lens modules automatically.
Queueing networks with finite buffers have been widely used for modeling and analyzing many manufacturing systems. However, exact analytical results for queueing networks with finite buffers are limited only to some special systems with one or two queues
[4
,
6
,
13
,
16
,
19]
. So many approximation methods are presented for analysis of queueig networks with finite buffers. Most of the approximation methods for serial lines or assembly systems are either based on decomposition or on aggregation approaches
[3]
. The principal procedure of decomposition methods is to decompose the long line into subsystems that are mathematically tractable, and derives a set of equations that determine the unknown parameters of each subsystem, and finally develops an algorithm to solve these equations. The basic idea of aggregation method is to replace a twonode system by a single equivalent node and reduce the number of nodes in the network. For a detailed list references for approximations and their application to manufacturing system, see review papers
[3
,
11
,
14]
and monographs
[1
,
2
,
7
,
12
,
15]
. The literature on the analysis of queueing networks with finite buffer and multiple servers is more scarce than the case of single server system, e.g. see
[5
,
18]
which are focused on the approximation of serial lines with reliable servers. Almost all decomposition method use subsystems with two nodes and single buffer between them. Recently, approximate analysis for multiserver tandem queues with exponential service times and finite buffers is presented in
[17]
where the subsystems with two nodes and two buffers are used to reflect the dependence between consecutive stages and improves the quality of approximation.
The literature on the approximation for the system with parallel lines with multiple servers and finite buffer is very limited. The purpose of this paper is to provide an approximation method for multiserver twostage networks with merge configuration and blocking which will be a building block for analysis of multiserverfinitebuffer queueing networks with parallel lines and merge configuration. The main idea of the method is to decompose the original system into subsystems that have two service stations with multiple servers, two buffers and external arrivals to the second stage are allowed. The subsystems are modeled by level dependent quasibirthanddeath (LDQBD) process.
This paper is organized as follows. In Section 2, the model is described in detail. Approximation procedure is presented in Section 3. Numerical results and concluding remarks are presented in Sections 4 and 5, respectively.
2. Model description
We model the manufacturing with parallel lines by the twostage open queueing network in which the first stage consists of
J
multiserver queues with finite buffers and the second stage is one queue with multiple servers and finite buffer. Two stages are linked in merge configuration as depicted in
Fig. 1
. The queues (merging queues) at the first stage will be denoted by node
i, i
= 1, 2, · · · ,
J
, and the queue (merged queue) at the second stage is denoted by node 0. The node
i
consists of a service station
M_{i}
with
m_{i}
parallel identical servers and a buffer
B_{i}
of size
b_{i}
and let
I_{i}
=
m_{i}
+
b_{i}
,
i
= 0, 1, 2, · · · ,
J
. The index
i
can be viewed as the sequential number of the nodes at the first stage runs from 1 to
J
unless otherwise stated. The service time of each server at
M_{i}
is exponentially distributed with rate
µ_{i}
,
i
= 0, 1, 2, · · · ,
J
. Customers arrive to node
i
from outside according to a Poisson process with rate
λ_{i}
,
i
= 1, 2, · · · ,
J
. The arrivals to any node at the first stage are dispatched to some of its servers if there is one free, and if all servers are occupied the request waits in the corresponding buffer. When an arrival finds no free position in the buffer (buffer is full), it is lost. After completion of the service at node of the first stage the request proceeds to node 0, and is taken immediately into service if one of the servers is free (no queue at node 0), otherwise is placed into the buffer
B
_{0}
and waits there until a server is available. If buffer
B
_{0}
is full at the instant of service completion at node
i
, the customer is forced to stay at node
i
until a space becomes available at node 0. During this period, the server just completed its service is blocked. This type of blocking mechanism is called blockingafterservice (BAS). Since there are more than one node directly linked to node 0, the servers in more than one upstream node can be blocked simultaneously. In this case, we assume that the corresponding blocked customers enter node 0 on a random dispatching rule. Let
α_{j}
(
y
_{1}
, · · · ,
y_{J}
) be the probability that a blocked customers at node
j
joins the node 0 upon a space in
B
_{0}
is available when there are
y_{i}
servers blocked at node
i, i
= 1, 2, . . . ,
J
. A customer who has completed service at node 0 leaves the system.
A twostage queueing network with merge configuration
Let
X_{i}
be the number of customers at node
i
which includes the customers being served at
M_{i}
and waiting requests at
B_{i}
but does not include the customers blocked to enter node 0 and
Y_{i}
the number of blocked servers at
M_{i}
,
i
= 1, 2, · · · ,
J
in stationary state. By
X
_{0}
denote the number of customers at node 0 that include the customers blocked at node
i, i
= 1, 2, · · · ,
J
. It can be seen that 0 ≤
X
_{0}
≤
H
, where
H
=
l
_{0}
+
m
with
Let
X
= (
X
_{1}
, · · · ,
X_{J}
) and
Y
= (
Y
_{1}
, · · · ,
Y_{J}
). Then the state space of (
X
_{0}
,
X , Y
) is
S
=
S
_{0}
∪
S
_{1}
, where
and
where
x
= (
x
_{1}
, · · · ,
x_{J}
),
y
= (
y
_{1}
, · · · ,
y_{J}
) and
e
is the column vector of appropriate size whose components are all 1. The state space
S
is so complex and its size increase drastically as the number
J
of nodes and/or
m_{i}
,
b_{i}
increase.
Main goal of this analysis is to provide an approximation method for the mean departure rate from node 0 that is the throughput of the system.
3. Approximation
In this section, we derive an algorithm for approximate analysis of throughput of the system. First we fix a node
i
. For an investigation of the behavior of node
i
and node 0, we consider the twonode queue denoted by
L_{i}
where the arrivals from outside to the second stage are allowed as depicted in
Fig.2
. We denote the first node and the second node by
respectively. The node
is the same as node
i
of the original system and has a service station, that is, there are
m_{i}
exponential servers with rate
µ_{i}
in parallel and a finite buffer of size
b_{i}
. The BAS blocking rule is assumed in the system. The node
consists of a service station
M
_{0}
with
m
_{0}
exponential servers with rate
µ
_{0}
in parallel and a buffer
of size
b
_{0}
. In order to reflect the effects of node
j, j
≠
i
, we assume that
has
J
− 1 virtual buffers
whose size is of
m_{j}
,
j
= 1, 2, · · · ,
J
,
j
≠
i
and type
j
customers arrive from outside to queue
. If a type
j
customer finds that the queue
is full upon arrival, the customer is blocked and stayed at the virtual buffer
until the queue
can accommodate the customer. We assume that the distribution of interarrival time of type
j, j
≠
i
customer is exponential with rate
γ_{j}
(
h
,
y
) that depends not only on the state
h
of
but also on the state
y
= (
y
_{1}
, · · · ,
y_{J}
) of the number of blocked customers
Y
. We assume that the arrivals of type
j
are blocked when
Y_{j}
=
m_{j}
, that is,
γ_{j}
(
h
,
y
) = 0 for
y_{j}
=
m_{j}
. If buffer
is full upon type
j
arrival, we let
Y_{j}
increase by 1. The state of
Y_{j}
s decreased by 1 with probability
α_{j}
(
y
) upon a service completion
The arrival rate
γ_{j}
(
h
,
y
) will be approximated by iteration in the later.
Twonode tandem queue L_{i} with virtual buffers and external arrivals to the second node
Let
be the number of customers excluding the blocked one and
the number of blocked customers at
at time
t
. Denote by
the number of type
j, j
≠
i
customers blocked and by
the sum of the number of customers at
and
the number of blocked customers at time
t
. Then the stochastic process
and
is a Markov chain on the state space
where
h
= {(
h, n,
0
), 0 ≤
n
≤
l_{i}
},
h
= 0, 1, · · · ,
l
_{0}
and for
h
=
l
_{0}
+
k, k
= 1, 2, · · · ,
m
,
h
= {(
h, n,
y
),
It can be easily seen that the Markov chain
is a level dependent quasibirthanddeath (LDQBD) process whose generator
Q_{i}
is of the form
The block matrix
is the square matrix of size 
h
, the number of states of level
h
,
h
= 0, 1, 2, · · · ,
H
and whose component
are given as follows:
where
I
(
A
) is the indicator function of
A
, that is, if
A
is true,
I
(
A
) = 1, otherwise
I
(
A
) = 0. The components of
are given as follows: for 0 ≤
h
≤
l
_{0}
− 1,
and for
l
_{0}
≤
h
≤
H
− 1,
where
e
_{k}
is the
J
dimensional vector whose
i
th component is 1 and others are all 0 and
µ_{i}
(
n
,
y_{i}
) = min(
n
,
m_{i}
−
y_{i}
)
µ_{i}
is the service rate at node
S_{i}
when
The components of
are given as follows: for 1 ≤
h
≤
l
_{0}
,
and for
l
_{0}
+ 1 ≤
h
≤
H
,
Let
and
Y
* be the stationary version of
and
Y
*(
t
), respectively and
The stationary distribution
π
_{i}
= (
π
_{i}
(0),
π
_{i}
(1), · · · ,
π
_{i}
(
H
)) satisfies the following equations
where
is obtained recursively as follows
The vector
π
_{i}
(0) is the unique solution of the equations
Noting that the number Ψ
_{i}
of busy servers at
once
π
_{i}
is given, we can calculate the approximation formulae for arrival rate from node
i
to node 0 given
as follows :
where
and the arrival rate from node
i
to node 0 given
where
S_{i}
(
h
,
y
) = {
y
:
y
e
= max(
h
−
l
_{0}
, 0)} and
We use the iterative algorithm to determine the parameters and calculate the throughput.
be the system
L_{i}
in the
k
th iteration and
be the arrival rate to
Algorithm

Step 0:Initial Step: Initially we assume that no servers at nodej, j= 2, · · · ,Jare blocked and consider the nodejas ordinaryM/M/mj/ljqueue with arrival rateλjand service rateµj. Set

wherepj(n) is the stationary distribution ofM/M/mj/ljqueue.

Step 1:Fori= 1, 2, · · · ,J, calculate the stationary distributionwith parametersUpdateusing (1).

Step2:Check the stopping criterion

whereϵ> 0 is a given tolerance. If the stopping condition is satisfied, then stop the iteration. Otherwise, go to Step 1.
Once
γ_{i}
(
h
,
y
) are obtained, calculate the stationary distribution
π_{i}
and
γ_{i}
(
h
) using (2),
i
= 1, 2, · · · ,
J
. Modeling node 0 as
M/M/m
_{0}
/H
queue with state dependent arrival rate
and service rate
µ
_{0}
and calculate throughput (TP)
No proof of convergence or accuracy can be given for this algorithm, as for many similar algorithms for serial line decomposition. However extensive numerical experiments show the convergence of the algorithm.
4. Numerical results
In this section, some numerical results are presented for accuracy of approximations for the performance measures such as throughput, mean number
E
[
X
_{0}
] of customers at node 0 and mean number
of blocked customers. The selection probability is used as
where
y
^{∗}
= max
_{1≤i≤J}
y_{i}
. Note that
is the number of nodes in which the number of blocked customers is biggest among other nodes.
In the following tables, the vectors
m
= (
m
_{0}
, · · · ,
m_{J}
) and
b
= (
b
_{0}
, · · · ,
b_{J}
) denote the server allocation and buffer size allocation, respectively. The total service rate allocation is denoted by
mµ
= (
m
_{0}
µ
_{0}
, · · · ,
m_{J}
µ_{J}
). For example, the vector (2, 3, 4) in the column corresponding to
b
means that
b
_{0}
= 2,
b
_{1}
= 3,
b
_{2}
= 4 and the vector
mµ
= (2.0, 1.0, 1.0) means
µ
_{0}
= 2.0/
m
_{0}
,
µ
_{1}
= 1.0/
m
_{1}
,
µ
_{2}
= 1.0/
m
_{2}
in
Table 1
. The arrival rates from outside to node
i
are assumed to be the same and denote it by
λ_{i}
=
λ, i
= 1, · · · ,
J
and the tolerance for the stopping criterion (3) is chosen as
ϵ
= 10
^{−5}
.
Approximation results for the system withJ= 2,m= (4, 3, 2),mµ= (2.0, 1.0, 1.0)
Approximation results for the system with J = 2, m = (4, 3, 2), mµ = (2.0, 1.0, 1.0)
Since the state space of the Markov chain for the system with
J
= 2 is small, we can have the exact results by solving the balance equations. In
Table 1
, approximation results (App) for the system with two merging nodes (
J
= 2) are compared with exact one (Exact). The relative percentage error is calculated by Err(%) = App − Exact × 100/Exact. The errors in
Table 1
seem to be due to the approximation of arrival rates
γ_{i}
(
h
,
y
) by decomposition. In
Tables 2

4
, approximation results for the throughput,
E
[
Y
_{0}
] and
E
[
Y
] in the system with
J
= 3,
m
= (5, 4, 3, 2),
mµ
= (2.5, 1.0, 1.0, 1.0) are compared with those of simulation (Sim). Simulation models are developed with ARENA
[9]
. Simulation run time is set to 220,000 unit times including 20,000 unit times of warmup period. Ten replications are conducted for each case and the average value and the half length of 95% confidence interval (c.i.) are obtained. The deviation (Dev) between simulation and approximation in Tables 24 is calculated by Dev=AppSim. The number of iterations of the algorithm to obtain each result in the tables is less than or equal to 4.
The throughput for the system withJ= 3,m= (5, 4, 3, 2),mµ= (2.5, 1.0, 1.0, 1.0)
The throughput for the system with J = 3, m = (5, 4, 3, 2), mµ = (2.5, 1.0, 1.0, 1.0)
E[X0] for the system withJ= 3,m= (5, 4, 3, 2),mµ= (2.5, 1.0, 1.0, 1.0)
E[X_{0}] for the system with J = 3, m = (5, 4, 3, 2), mµ = (2.5, 1.0, 1.0, 1.0)
E[Y] for the system withJ= 3,m= (5, 4, 3, 2),mµ= (2.5, 1.0, 1.0, 1.0)
E[Y] for the system with J = 3, m = (5, 4, 3, 2), mµ = (2.5, 1.0, 1.0, 1.0)
Numerical results show the approximation works well. Almost all the approximations for throughput are contained in the 95% confidence intervals and the relative percentage errors are all less than 1%. The approximations for
E
[
X
_{0}
] and
E
[
Y
] also provide satisfactory results.
5. Conclusion
In this paper, we developed an approximation method for a multiserver twostage queueing network with finite buffers and merge configuration. We decompose the system into subsystem. The subsystem is approximated by the tandem queue with two service stations and two buffer spaces and external arrivals at second stage. Approximate system is modeled with LDQBD process. An iterative algorithm is presented for calculating the parameters. The approximation method proposed can be used to analyze the more complex queueing networks with merge configuration.
BIO
Yang Woo Shin received B.S. from Kyungpook National University, and M.Sc. and Ph.D in Mathematics at KAIST. He is currently a professor at Changwon National University since 1991. His research interests include queueing theory and its applications.
Department of Statistics, Changwon National University, Changwon, Gyeongnam 641773, Korea.
ywshin@changwon.ac.kr
Dug Hee Moon received B.Sc. from Hanyang University, and M.Sc. and Ph.D in Industrial Engineering at KAIST. He is currently a professor at Changwon National University since 1990. His research interests include simulation, manufacturing system design, queueing theory and its applications.
Department of Industrial and Systems Engineering, Changwon National University, Changwon, Gyeongnam 641773, Korea.
dhmoon@changwon.ac.kr
ltiok A
1997
Performance Analysis of Manufacturing Systems
Springer
New York
Buzacott J.A.
,
Shantikumar J.G.
1993
Stochastic Models of Manufacturing Systems
PrenticeHall
Englewood Cliffs, NJ
Dallery Y.
,
Gershwin S.B.
(1992)
Manufacturing flow line systems: A review of models and analytical results
Queueing Systems
12
3 
94
DOI : 10.1007/BF01158636
Diamantidis A.C.
,
Papadopoulos C.T.
(2009)
Exact analysis of a twoworkstation onebuffer flow line with paralel unreliable machines
European Journal of Operational Research
197
592 
580
Diamantidis A.C.
,
Papadopoulos C.T.
,
Heavey C.
(2007)
Approximate analysis of serial flow lines with multiple parallelmachine stations
IIE Transactions
39
361 
375
DOI : 10.1080/07408170600838423
Fadiloglu M.M.
,
Yeralan S.
(2002)
Models of production lines as quasibirthdeath processes
Mathematics and Computer Modeling
35
913 
930
DOI : 10.1016/S08957177(02)000596
Gershwin S.B.
1994
Manufacturing Systems Engineering
PrenticeHall
Englewood Cliffs, NJ
Jain S.
,
MacGregor Smith J.
(1994)
Open finite queueing networks withM/M/C/Kparallel servers
Computers & Operations Research
21
297 
317
DOI : 10.1016/03050548(94)900922
Kelton W. D.
,
Sadowski R. P.
,
Sadowski D. A.
1998
Simulation with ARENA
2nd Ed.
McGrawHill
New York
Li J.
(2005)
Overlapping decomposition: A systemtheoretic method for modeling and analysis of comples manufacturing
IEEE Transactions on Automation Science and Engineering
2
40 
53
DOI : 10.1109/TASE.2004.835576
Li J.
,
Blumenfeld D.E.
,
Huang N.
,
Alden J.M.
(2009)
Throughput analysis of production systems: recent advances and future topics
Interational Journal of Production Research
47
3823 
3851
DOI : 10.1080/00207540701829752
Li J.
,
Meerkov S.M.
2009
Production Systems Engineering
Springer
Liu J.
,
Yang S.
,
Wu A.
,
Hu S.J.
(2012)
Multistage throughput analysis of a twostage manufacturing system with parallel unreliable machines and a finite buffer
European Journal of Operational Research
219
296 
304
DOI : 10.1016/j.ejor.2011.12.025
Papadopoulos H.T.
,
Heavey C.
(1996)
Queueing theory in manufacturing systems analysis and design: A classification of models for production and transfer lines
European Journal of Operational Research
92
1 
27
DOI : 10.1016/03772217(95)003789
Perros H.G.
1994
Queueing Networks with Blocking
Oxford University Press
Shin Y.W.
(2011)
Algorithmic solution forM/M/cretrial queue withPH2retrial times
J. Appl. Math. & Informatics
29
803 
811
Shin Y.W.
,
Moon D.H.
(2014)
Approximation of throughput in tandem queues with multiple servers and blocking
Applied Mathematical Modelling
38
6122 
6132
DOI : 10.1016/j.apm.2014.05.015
van Vuuren M.
,
Adan I.J.B.F.
,
ResingSassen S.A.E.
(2005)
Performance analysis of multi server tandem queues with finite buffers and blocking
OR Spectrum
26
315 
338
DOI : 10.1007/s002910040189z
Vidalis M.I.
,
Papadopoulos H.T.
(2001)
A redursive algorithm for generating the transition matrices of multistation multiserver exponential reliable queueing networks
Computers & Operations Research
28
853 
883
DOI : 10.1016/S03050548(00)000125