Advanced
THROUGHPUT ANALYSIS OF TWO-STAGE MANUFACTURING SYSTEMS WITH MERGE AND BLOCKING†
THROUGHPUT ANALYSIS OF TWO-STAGE MANUFACTURING SYSTEMS WITH MERGE AND BLOCKING†
Journal of Applied Mathematics & Informatics. 2015. Jan, 33(1_2): 77-87
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : July 03, 2014
  • Accepted : October 17, 2014
  • Published : January 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
YANG WOO SHIN
AND DUG HEE MOON

Abstract
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 multi-server two-stage 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 quasi-birth-and-death (LDQBD) process. AMS Mathematics Subject Classification : 60K25, 68M20.
Keywords
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 multi-server 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 multi-server two-stage networks with merge configuration and blocking which will be a building block for analysis of multi-server-finite-buffer 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 quasi-birth-and-death (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 two-stage open queueing network in which the first stage consists of J multi-server 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 Mi with mi parallel identical servers and a buffer Bi of size bi and let Ii = mi + bi , 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 Mi 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 blocking-after-service (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 , · · · , yJ ) 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 yi servers blocked at node i, i = 1, 2, . . . , J . A customer who has completed service at node 0 leaves the system.
PPT Slide
Lager Image
A two-stage queueing network with merge configuration
Let Xi be the number of customers at node i which includes the customers being served at Mi and waiting requests at Bi but does not include the customers blocked to enter node 0 and Yi the number of blocked servers at Mi , 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
PPT Slide
Lager Image
Let X = ( X 1 , · · · , XJ ) and Y = ( Y 1 , · · · , YJ ). Then the state space of ( X 0 , X , Y ) is S = S 0 S 1 , where
PPT Slide
Lager Image
and
PPT Slide
Lager Image
where x = ( x 1 , · · · , xJ ), y = ( y 1 , · · · , yJ ) 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 mi , bi 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 two-node queue denoted by Li 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
PPT Slide
Lager Image
respectively. The node
PPT Slide
Lager Image
is the same as node i of the original system and has a service station, that is, there are mi exponential servers with rate µi in parallel and a finite buffer of size bi . The BAS blocking rule is assumed in the system. The node
PPT Slide
Lager Image
consists of a service station M 0 with m 0 exponential servers with rate µ 0 in parallel and a buffer
PPT Slide
Lager Image
of size b 0 . In order to reflect the effects of node j, j i , we assume that
PPT Slide
Lager Image
has J − 1 virtual buffers
PPT Slide
Lager Image
whose size is of mj , j = 1, 2, · · · , J , j i and type j customers arrive from outside to queue
PPT Slide
Lager Image
. If a type j customer finds that the queue
PPT Slide
Lager Image
is full upon arrival, the customer is blocked and stayed at the virtual buffer
PPT Slide
Lager Image
until the queue
PPT Slide
Lager Image
can accommodate the customer. We assume that the distribution of inter-arrival time of type j, j i customer is exponential with rate γj ( h , y ) that depends not only on the state h of
PPT Slide
Lager Image
but also on the state y = ( y 1 , · · · , yJ ) of the number of blocked customers Y . We assume that the arrivals of type j are blocked when Yj = mj , that is, γj ( h , y ) = 0 for yj = mj . If buffer
PPT Slide
Lager Image
is full upon type j arrival, we let Yj increase by 1. The state of Yj s decreased by 1 with probability αj ( y ) upon a service completion
PPT Slide
Lager Image
The arrival rate γj ( h , y ) will be approximated by iteration in the later.
PPT Slide
Lager Image
Two-node tandem queue Li with virtual buffers and external arrivals to the second node
Let
PPT Slide
Lager Image
be the number of customers excluding the blocked one and
PPT Slide
Lager Image
the number of blocked customers at
PPT Slide
Lager Image
at time t . Denote by
PPT Slide
Lager Image
the number of type j, j i customers blocked and by
PPT Slide
Lager Image
the sum of the number of customers at
PPT Slide
Lager Image
and
PPT Slide
Lager Image
the number of blocked customers at time t . Then the stochastic process
PPT Slide
Lager Image
and
PPT Slide
Lager Image
is a Markov chain on the state space
PPT Slide
Lager Image
where h = {( h, n, 0 ), 0 ≤ n li }, h = 0, 1, · · · , l 0 and for h = l 0 + k, k = 1, 2, · · · , m , h = {( h, n, y ),
PPT Slide
Lager Image
It can be easily seen that the Markov chain
PPT Slide
Lager Image
is a level dependent quasi-birth-and-death (LDQBD) process whose generator Qi is of the form
PPT Slide
Lager Image
The block matrix
PPT Slide
Lager Image
is the square matrix of size | h |, the number of states of level h , h = 0, 1, 2, · · · , H and whose component
PPT Slide
Lager Image
are given as follows:
PPT Slide
Lager Image
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
PPT Slide
Lager Image
are given as follows: for 0 ≤ h l 0 − 1,
PPT Slide
Lager Image
and for l 0 h H − 1,
PPT Slide
Lager Image
where e k is the J -dimensional vector whose i th component is 1 and others are all 0 and µi ( n , yi ) = min( n , mi yi ) µi is the service rate at node Si when
PPT Slide
Lager Image
The components of
PPT Slide
Lager Image
are given as follows: for 1 ≤ h l 0 ,
PPT Slide
Lager Image
and for l 0 + 1 ≤ h H ,
PPT Slide
Lager Image
Let
PPT Slide
Lager Image
and Y * be the stationary version of
PPT Slide
Lager Image
and Y *( t ), respectively and
PPT Slide
Lager Image
The stationary distribution π i = ( π i (0), π i (1), · · · , π i ( H )) satisfies the following equations
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is obtained recursively as follows
PPT Slide
Lager Image
The vector π i (0) is the unique solution of the equations
PPT Slide
Lager Image
Noting that the number Ψ i of busy servers at
PPT Slide
Lager Image
once π i is given, we can calculate the approximation formulae for arrival rate from node i to node 0 given
PPT Slide
Lager Image
as follows :
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and the arrival rate from node i to node 0 given
PPT Slide
Lager Image
PPT Slide
Lager Image
where Si ( h , y ) = { y : y e = max( h l 0 , 0)} and
PPT Slide
Lager Image
We use the iterative algorithm to determine the parameters and calculate the throughput.
PPT Slide
Lager Image
be the system Li in the k th iteration and
PPT Slide
Lager Image
be the arrival rate to
PPT Slide
Lager Image
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
PPT Slide
Lager Image
  • 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
PPT Slide
Lager Image
  • 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
PPT Slide
Lager Image
and service rate µ 0 and calculate throughput (TP)
PPT Slide
Lager Image
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
PPT Slide
Lager Image
of blocked customers. The selection probability is used as
PPT Slide
Lager Image
where y = max 1≤iJ yi . Note that
PPT Slide
Lager Image
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 , · · · , mJ ) and b = ( b 0 , · · · , bJ ) denote the server allocation and buffer size allocation, respectively. The total service rate allocation is denoted by = ( m 0 µ 0 , · · · , mJ µ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 = (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)
PPT Slide
Lager Image
Approximation results for the system with J = 2, m = (4, 3, 2), = (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), = (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 warm-up 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 2-4 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)
PPT Slide
Lager Image
The throughput for the system with J = 3, m = (5, 4, 3, 2), = (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)
PPT Slide
Lager Image
E[X0] for the system with J = 3, m = (5, 4, 3, 2), = (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)
PPT Slide
Lager Image
E[Y] for the system with J = 3, m = (5, 4, 3, 2), = (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 multi-server two-stage 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 641-773, 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 641-773, Korea.
dhmoon@changwon.ac.kr
References
ltiok A 1997 Performance Analysis of Manufacturing Systems Springer New York
Buzacott J.A. , Shantikumar J.G. 1993 Stochastic Models of Manufacturing Systems Prentice-Hall 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 two-workstation one-buffer 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 parallel-machine stations IIE Transactions 39 361 - 375    DOI : 10.1080/07408170600838423
Fadiloglu M.M. , Yeralan S. (2002) Models of production lines as quasi-birth-death processes Mathematics and Computer Modeling 35 913 - 930    DOI : 10.1016/S0895-7177(02)00059-6
Gershwin S.B. 1994 Manufacturing Systems Engineering Prentice-Hall 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/0305-0548(94)90092-2
Kelton W. D. , Sadowski R. P. , Sadowski D. A. 1998 Simulation with ARENA 2nd Ed. McGraw-Hill New York
Li J. (2005) Overlapping decomposition: A system-theoretic 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) Multi-stage throughput analysis of a two-stage 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/0377-2217(95)00378-9
Perros H.G. 1994 Queueing Networks with Blocking Oxford University Press
Shin Y.W. (2011) Algorithmic solution forM/M/cretrial queue withPH2-retrial 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. , Resing-Sassen S.A.E. (2005) Performance analysis of multi- server tandem queues with finite buffers and blocking OR Spectrum 26 315 - 338    DOI : 10.1007/s00291-004-0189-z
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/S0305-0548(00)00012-5