APPROXIMATE ANALYSIS FOR THE MERGE CONFIGURATION OF AN OPEN QUEUEING NETWORK WITH BLOCKING Hyo-Seong Lee Stephen M. Follock Technical Report #87-11 Department of Industrial and Operations Engineering The University of Michigan 1205 Beal Avenue Ann Arbor, Michigan 48109-2117 (313) 764-6474

ABSTRACT A merge configuration of open queueing networks with exponential service times and finite buffers is analysed. We offer an iterative algorithm to approximate the steady-state probabilities for each queue of the system. The procedure decomposes the queueing network into individual queues and analyses each individual queue in isolation. An M/M/1/ N or M/G/1/N model is used for the analysis of the merging queues; An M/M/1/N with state dependent arrival rate model is used for the receiving queue. The approximation method is easy to implement requires little memory, is computationally fast and yields very accurate results.

1.Introduction Queuing networks, where the output of one server is the input to others, are useful in modeling manufacturing systems, computer systems, telecommunications, etc. This is particularly true when the buffer space between facilities is finite, so that an upstream server can be blocked due to unavailability of space in the destination server. In general, queueing systems with blocking are difficult to analyse, and only under very limited conditions can the exact solutions be obtained. Therefore, most analyses available are based on approximation or simulation methods. There are three basic structural configurations in networks of queues: tandem, split and merge, combinations of which can represent a general network. For open queueing networks (i.e., where units do not re-circulate continually), among these three the tandem configuration has been most frequently analysed. It has been studied by Hillier and Boling[11], Caseau and Pujolle[7], Altiok[2], Perros and Altiok[15], Bocharov and Rokhas[4], Brandwajn and Jow[6], Foster and Perros[8], Gershwin[9], Pollock, Birge and Alden[18]. The split and merge configurations have been reported by Boxma and Konheim[5] and Altiok and Perros[3]. Combinations of these configurations to form open queueing networks with blocking have been studied by Takahashi, Miyahara and Hasegawa[21], Labetoulle and Pujolle[12], Perros and Altiok[16] and Perros and Snyder[17]. For closed queueing networks with blocking, approximation algorithms have been reported by Suri and Diehl[19,20], Yao and Buzacott[22], Akyildiz[l] and Onvural and Perros[13]. A detailed literature survey can be found in Perros[14]. In this paper, we present an approximation method to analyse the merge configuration of an open queueing network with blocking. This algorithm is based on an earlier algorithm (SIMP) proposed by Pollock, Birge and Alden[18] to analyse tandem queues with blocking. It is also similar to the algorithm of Altiok and Perros [3], but differs in that we 1

2 describe the state of the merged queue by considering the sequence of blocked units. Our algorithm also uses a fundamentally different approximation for the effective service time distribution of the merging queues. 2.The Merge Configuration The network we consider is identical to that in Altiok and Perros[3]. It consists of K parallel single server queues, each feeding the same single server queue (see Fig.1). We will call each of the K parallel queues (queue 1,2,-,K) a merging queue; the queue receiving the output of these merging queues is the merged queue (or queue 0). The service time at queue i follows an exponential distribution with rate.i; Arrivals to queue i are independent Poisson Processes with rate A.. There is no external arrival to the merged queue. The buffer size of the i-th merging queue is N. (including the one in service). N - N is the buffer size of the queue 0, and i E= o is service rate at queue 0. Arrivals to any queue are served in a FIFO manner. If an arrival encounters a merging queue when it is full, the arrival is lost. When a unit, completes service at the i-th queue (i= 1, —,K), it proceeds to queue 0 only if space is available. However if queue 0 is full at that time, the unit waits in the i-th server until it can enter queue 0. During this time the i-th server cannot serve other units that might be waiting in its buffer: in this case, the i-th server is said to be blocked and queue 0 is blocking. Thus, the merging queues cannot be blocking, and the merged queue cannot be blocked. Since K queues feed into queue 0, there might be more than one queue blocked at any instant; in the worse case, obviously, there can be K blocked queues. In the multiple blocking case, we assume blocked units enter queue 0 on a "First-Blocked-First-Enter" basis [3].

3 < Insert Fig. 1> 3. Analysis of the Model 3.1. Approach and General Relationships Our general approach is to decompose the queueing network into individual queues, and then analyse each individual queue separately. We will make important use of the fact that the time for a unit to clear service in a merging queue has two components; the actual service time plus the delay caused by being (possibly) blocked by queue 0. In particular, we make the following approximate assumptions about what is in reality an extremely complicated system: a) There are Poisson arrivals, with rate A. (i 1,.,K) fiom queue i to queue 0 as long as the i-th queue is not blocked. When the i-th queue is blocked, there is of course no arrival from queue i to queue 0. b) The buffer size of queue 0 is augmented by K so that the total buffer of queue 0 is N+K. Assumption b) is simply a modelling convenience made possible by noting that a blocked unit is ready to proceed to queue 0 whenever there is space in queue 0. Thus, such a unit is effectively waiting in line to be served by server 0. The key to our approach is thus to take advantage of the fact that queue 0 is never blocked, and its service time is exponentially distributed with rate.t, so that it can be analysed by using M/M/1/N+K analysis, using approximation a). The second part of our approach is to use seperate M/G/1/N1 analyses in each merging queue i, in order to obtain

4 the values of A. used in approximation a). In order to proceed, we define (where, unless otherwise stated, the index i always runs from 1 to K) T. = clearance time for server i, i.e., the time between when a unit enters service in queue i, and when it arrives at queue 0, Si,(S) = service time at server i (server 0), (excluding any delay due to blocking) A. - arrival rate to queue 0 from queue i as long as queue i is not blocked, K, A E S A. i=l 1 P.(k), [P(k)] = steady state probability that there are k units at queue i [queue O], b.(n) - probability that queue i is blocked and the number of units at queue 0 is N+n, a.(k) - conditional probability that, upon service completion at server i, there are k units at queue 0, f. Probability {i-th queue is full} = P.(N.) These definitions, and the structure of the system, produce the following relationships. a) The contribution of queue i to the total system throughput, A., is given by (3.1) A = A(1-fi) 1 1 1 b) The total system throughput, A, is K = S A. i=l c) The clearance time for queue i is a random variable represented by

5 K-1 S. with probability 1 - a. (N+j) T. -j=o (3.2) S + SO+l) with probability a.(N+j) j=0,,K- 1 where S is a gamma-distributed random variable that is the sum of j + 1 service times j+1 at queue 0. In particular, as will be used later on, E[ S ] = - Note that the bottom line of (3.2) follows because 1) the residual service time of a unit in queue 0 is exponential by the memoryless property of exponential distribution, and 2) given that a unit sees j other units blocked at the instant of service completion at queue i, it must wait j independent service times and one residual service time at queue 0 before it feeds into queue 0. By 1) the distribution of this blocking time is the convolution of j+ 1 independent exponentially distributed random variables with parameter /, which is gamma distributed random variable with parameters (j + 1,/). 3.2. Analysis of Queue 0 Before we analyse queue 0 in general, we first consider the special case of K=2. Suppose we know the values of Al, XA Define the state of queue 0 to be i if there are i units in queue 0 and there is no blocking. If there is blocking, the state of queue 0 is ( N+n,v) where N+n is the number of units in queue 0 (including n blocked units), and v is an n-component vector representing, in order, the units which are being blocked. For example, the state { N+ 1, 1 } {queue 1 is blocked by queue 0}; { N+ 1, 2 } - {queue 2 is blocked by queue 0}; { N+2, 12 } - {queue 1 and 2 are blocked by queue 0 in that order};

6 { N+ 2, 21 } {queue 2 and 1 are blocked by queue 0 in that order} The resulting state transition diagram of queue 0 is shown in Fig. 2. We are interested in computing the (steady state) occupancy probabilities of these states. We will find these. however, by looking at a smaller set of aggregated states. In particular, define {N+ 1} {N+ 1, 1} U {N+ 1, 2} {N+2} -{N+2, 12} U {N+2, 21} These new aggregated states {N+i}, i=1,2, represent, simply, N+i units in queue 0 - including those blocked and thus waiting in their respective merging queue. We also define A (i) to be the arrival rate from state i to state i + 1 in the aggregated a system. Figure 3 shows the transition diagram for this (smaller) state space. It is straightforward to show that the following equations of balance hold for the system in figure 2: 1i P(N+1 i) =- P(N+i) i= 1,2 (3.3) 1 P(N+2, 12) = P(N+2, 21) = -P(N+2) (3.4) 2 where A A + A Since this new process is a simple birth and death process, it is almost trivial to find P(i) for i=0, *e,N+2. From (3.3), (3,4) we can obtain the occupancy probabilities for the original (unaggregated) queue 0. < Insert Fig. 2, Fig. 3>

7 This idea can be readily extended to the general system with K merging queues. As in the above, the state of queue 0 is i, the number of units in the system. If there is blocking, the state of queue 0 is (N+n,v), n= 1,",K, where N+n represents the number of units in queue 0, including blocked ones, and v is the n-component vector representing the units which are being blocked, in order. Unfortunately since the order of blocked units is part of the state description, the total number of states increases geometrically in K. However, if we are able to disregard the order of units being blocked, states which have the same number of units can be aggregated into one state, and the total number of states will be only N+K+ 1. We now define the states of such an aggregation indexed by i, the number of units in queue 0 (i=0,.-,N+K). Recalling that we have defined A (i) to be the arrival rate to state i+1 from state i in the aggregated system, the following theorems hold. Theorem 3.1. The aggregated queue 0 is equivalent (in terms of producing identical P(i) to the original queue 0 if the arrival rate to each aggregated states is: (3.5) (i) = A ~ for i=0,-.,N Aa(N+n) = for n= 1,?K~a~Q n k - where Qk = S n A., i. E {1,-.,K} il<...<i i= J * Note that if the merging queues are symmetric, then A (N+n) satisfies the simple expression K-n A (N+n) = - A for n= 1,,K- (3.7) K

8 Theorem 3.2. The relationship between the steady-state probabilities of the original queue 0 and those of aggregated queue 0 is: n \i II AL j=1 J P(N+n.i i ) = P(N+n) 1 n n! n (3.8) for n=l —,K (The proof is in the appendix ) To use (3.8) we note that the aggregated occupancy probability P(i) can be found from i a(i P(i)=P(0) I - i=1,2, -,N+K j=1 H. N+K P(i) = 1 (3.8.a) i=O In order to use these results however, we need to know the values of A.. Suppose we have available the values of A. and b.(n). To find the A., we can use the following equation. equation. K A.(1 - E b.(n)) = A. I I 1 n = 1 (3.9) Equation (3.9) is a conservation equation which yields the value of the arrival rate A. needed in order to produce the given value of throughput A.. 3.3 Analysis of Merging Queues The above analysis depended upon known values of b.(n) and A.. But b.(n) can be 1 ~ ~ ~ ~~ 1

9 obtained directly from P(i), as will be explained later. Also, from b.(n), ca(k) can be straightforwardly found. Once values of a. (k) are obtained, we can find the clearance time distribution at merging queues using equation (3.2), which makes it possible to analyse each merging queue by separate M/M/1/N. or M/G/1/N. analyses. Then we obtain the full 1 1 " probability f. at each merging queue, which produces A.. Given A, and b.(n), we once more find an updated Ai using equation (3.9). This procedure is used iteratively until the expected clearance times at merging queues (or other appropriate variable values) converge. We now examine each merging queue to find bi(n), the probability {queue i is blocked and the number of units at queue 0 is N+n}, b.(n) = E P(N+n,i -i ) 1 1' By simply inserting equation (3.8) into the above, one can show that: A f] 1 n- 1\l b.(n) = P(N+n) i=1, —,K j=0, —,K (3.10) Q n-1 where = 1 A i, i. { 1,,i-l,i+ 1.,K} <... <i n-1j=1 J Note that if we sum (3.9) over the merging queues i using equation (3.10), we obtain the following conservation flow equation for the aggregated system. N+K-1 E A (i)P(i) = A (3.11) i=0 We now find the conditional probability ai(k) that, upon service completion at server i, a unit is blocked and there are k units at queue 0. To do this, we will assume that a unit

10 at server i, at the instant service is completed, sees queue 0 in steady state. From this assumption and the fact that there can be no service completion at queue i if it is blocked, we see that a.(N +j) is the conditional probability that there are NT+j units at queue 0 given that queue i is not blocked. Here, the steady state probability that queue i is blocked K is E b.(n) since b.(n) is the probability that there are n blocked units at queue 0 including n=1 one from queue i. From these, a.(N+j) can be obtained: P(N +j)-bi j) a (N+j) = K i= 1,.,K j=0,. -,K (3.12) 1- E b.(n) n=l where b.(O) is defined to be 0. We now can use this value of a.(N+j) in equation (3.2) to obtain the distribution of T., 1 1 the clearance time at queue i. This, in turn, allows us to analyse queue i by using M/M!'1/ N or M/G/i/N methods, since the arrivals to each are Poissons. Which of these we use depends upon the approximation assumption we are willing to make about the distribution of T.: I Approximation 1: Approximation 2: Model each merging queue i (i=1,,Kj as an M/M/1/N system. To do this, we assume the clearance time T. is exponentially distributed, with an equivalent service rate equal to the reciprocal of the expected clearance time. Model each merging queue i (i= 1,..,K) as an M/G/1/N system, using (3.2) to describe the random variable T.. Both of these lead to iterative algorithms that use queue 0 analysis to produce values of a.i() and queue i analysis to produce A.. ~~~~~~~~~~~~~~~~~1

11 3.3.1. M/M/1/N Analysis If we assume that the clearance time at server i has an exponential distribution, the information needed to analyse the queue is only the arrival rate and the expected clearance time. But the arrival rate is given as A., and the expected clearance time can be obtained from (3.2), 1 K-1 j+1 E(T) = - + S.(N+j) - i= l,-,K (3.13) i= -0 An approximate solution to the system's steady state probabilities is then gotten from the following iterative algorithm. 0. (Set-up) Set the values of A., Yi, Ni for i=O,-0-,K 1. (Initialization - The conditions here are as if all queues are unblocked.) 1 Set. E(T.) = - p. = A. E(Ti) for il.K 1 i 1 Find Ai A. (l-f) for i= l.-,K where N. (1-Pi.)i' f. = ------ (3.14) 1N.+1 1 - Pi 1 Set A. =,. for i= 1,.,K K A= A., A = A i=1 2. (Find full and blocking probabilities of queue 0) Find A (i) using equations (3.5), (3.6) for i=0, -.,N+K-1 P(i) using birth and death equations (3.8.a) for i=0,,N+K bi(n) using equation (3.10) for i=l,.,K, n= O,.,K

12 Q.(N+j) using equation (3.12) for i= 1,,K, j=0, -.,K 3. (Find expected clearance times at each merging queues. ) Solve for E(T.) using equation (3.13) and set Pi = A.E(T.) for i= 1,,K. 4. (Convergence check) If updated values of E(Ti) show little change from the previous ones for all i (i.e., convergence) go to step 6. Else, go to step 5. 5. ( Find full probabilities of merging queues and A ) Obtain full probabilities for each of the merging queues using equation (3.14) Find A. using equation (3.1) for i= 1. -,K K _ Set A = A. i=l Find A. and A using equation (3.9). Go to step 2. 6. (Calculate occupancy probabilities) For queue 0, these have already been obtained in step 2. For queue 1 through K, (1 - pJi)P P.(n) = for i 1,..K, n=0.....N. (3.15) N.+1 1-Pi 3.3.2 M/G/1/N Analysis The clearance time of each merging queue is in fact not exponentially distributed (as assumed in the section above) since there might be delay due to blocking. Therefore, in order to get a more accurate analysis, we can treat the clearance time of a merging queue as having a general distribution, which requires replacing the M/M/1/N analysis of step 3

13 of algorithm 1 with an M/G/1/N analysis. The standard approach for M/G/1/N analysis is to consider the state occupancies only at departure epochs. Following this approach, define for each queue i the following; n a. - Probability of n arrivals during a clearance time, n t7r = steady state probability of n units in queue i, pj(t) - p.d.f. of Ti, h.(t), [h(t)] - p.d.f. of S. [S],.(n) (n) X (s), [h (s)] - n-th derivatives of Laplace transforms of ~i(t),[hi(t)], i i Then, (see Pollock et.al [18] for details ). n n ]i (n) (3.16) a. = 6 (A.) 1 i 1 n! In order to evaluate the right hand side of (3.16) we note that, from (3.2), K- 1 K-1 J.(s) ={ - E aj(N+j) }h (s) + E a.(N+j){h (s){h (s)} } (3.17) j=0 j=o Taking the n-th derivative of both sides of (3.17).: (n) K-1 n), (s) = { 1 - Qo.(N+j) }h. (s) j=0 K-l 1 n (n"- k) + + E O(N+j) O (k)h (s){(h (s)) (3.18) j=0 k=0 which allows (3.16) to be evaluated by setting s=A.. n n Once the values of a. are obtained, the steady state probabilities 7i. follow from the usual M/G/1/N analysis. (see, e.g., Gross and Harris[10])

14 The steps in the resulting algorithm are as follows: 0,1,2. (See algorithm 1) 3. (Find expected clearance times at each merging queues.) (n) n Calculate X (Ai) using equation (3.18) and calculate a. using equation (3.16) for i I ] i=1,-,K and n=0,-,N....(1) Set E(Ti) = -i (0) for i= 1,.,K 4. (Convergence check) If updated values of E(T.) show little change from the previous ones for all i (i.e., convergence) go to step 6. Else, go to step 5. 5. ( Find full probabilities of merging queues and A. ) N. Use AM/G/1/N analysis to solve for N, 1 N. Set f. = 7r. for i=l,,N. Find A. using equation (3.1) for i 1,..,K K Set A -= A. i=l Find A. and A using equation (3.9). Go to step 2. 6. (Calculate occupancy probabilities) For queue 0, these have already been obtained in step 2. For queue 1 through K, use M/G/1/N analysis to obtain the occupancy probabilities. If the merging queues have infinite buffer spaces, since A. is simply equal to A. at 1 1

15 every iteration, the iterative procedure becomes simpler. For stability conditions when merging queues have infinite buffers, see Altiok and Perros[3]. 5. Computational Results The two approximation methods were tested for their accuracy in estimating steady state occupancy probabilities. In those cases where analytic solutions are not available the results are compared with simulations. Tables 1-6 shows a comparison with the method of Altiok and Perros [3], for systems consisting of from 2 to 4 merging queues. Tables 1 through 4 treat problems with finite buffers for the merging queues, and table 5 and 6 treat the problems with infinite buffers for the merging queues. Each table gives average and maximum absolute deviations of the approximate values from the exact or simulation ones. In all experiments we have conducted, the number of iterations needed for convergence was under 7 and CPU time required was under 0.05 seconds on an IBM 3090-400. We should note that the Altiok and Perros method always overestimates the probability of queue 0 being full. Ours does not, and usually gives more accurate values. This is due to the fact that, in analysing queue 0, Altiok and Perros do not consider a reduction of arrival rates for the states where blocking exists, which fact our method takes into account. As can be seen in the tables, both algorithm 1 and algorithm 2 give better results than those of Altiok and Perros, in both average and maximum absolute deviations. We can also see that algorithm 2 yields only slightly improved results over algorithm 1. This suggests that the exponential approximation for the clearance time is not unacceptable, at least for the cases we examined. This also suggests that a great part of the error may come from the (fundamentally faulty) Poisson assumption about the input

16 process to queue 0, not from the exponential assumption for the clearance time. Algorithm 2 does, however, have the distinct advantage of allowing the service time distribution at the merging queues to be non-exponential, although this paper does not present numerical results for such cases. 6. Conclusions We presented two approximation algorithms for analysing a merge configuration of queueing networks with blocking. These algorithms converge rapidly acceptably. Considering the simplicity of algorithm 1, we are optimistic about using it as a "building block" in the analysis of more general configurations of open queueing networks with blocking. It remains to be seen whether we can provide any error bounds, or provide explicit advice on parameter values for which the approximation is unequivocally recommended. Acknowledgement This study was supported in part by a contract from the General Motors Corporation to the University of Michigan, for the development of analytical tools for production systems. We wish, in particular, to thank Jeff Alden and Larry Burns, of G.M., for their continuing interest and support.

17 < Appendix > (Proof of Theorem 3.1, 3.2) Suppose we set A (i) as in (3.5).(3.6) and solved for P(i), i=O," —,N+K. Also suppose we obtained P(N+n,i1.i ) from (3.8). If the P(N +n,il. i) obtained thus satisfy the n'1 n balance equation of the original system, then Theorem 3.1 and 3.2 must be true. The balance equations of the original system are (A.1) A P(O) = pP(1) i=O (A.2) (A +,U)P(i) = A P(i-1) + P(i + 1) i= l,,NK (A +,u)P(i)= A P(i-1) +, E P(N+l,j) i=N (A.3) j=1 P(N+n,i i ){ 2 A. + /} = A, P(N + n-1, i1i _ 1 P(N + n{i i'in j C {i1..,i} + ES P(N+n+ 1, ji..-i ) 1n<K-1 (A.4 j C{i 1' "'in}:!: P(N+Ki iK). = Ai P(N+K-i,i..i) n=K (A.5), ~ ~1 K 11^. 1 K- 1 We now show equation (A.4) is satisfied by the solution of the aggregated system together with relationship (3.8). It is trivial to show that the balance equations of the aggregated system lead to the solutions a(n) A. 6) P(k) = P(k-1) —- k = 1,iN+K since the aggregated system is a simple birth-and-death process. If we insert (A.6) together with the relationship (3.8) into (A.4), it is easily proved that (A.4) is satisfied. For the other balance equations,,i.e., (A. 1), (A.2), (A.3), (A.5), the same

18 procedure is used. *

NI K fm N < Fig. 1 > The Merge Configuration

x* 1* x* A rN+1 *0o *' X <tN+1r,2i ( < Fig. 2> State Transition Diagram for Queue 0 * * (O )(1).. rIi~Z...... - * * %* x* 24kX2 CI IC ) < Fig. 3 > Aggregated State Transition Diagram

Table 1. Problem Description Ni=4 N2 N =4; X4-4 2=2; =5 p2=3 i =7 Measure Exact Altiok Algo.l Algo.2 P (0) 0.2408 0.2470 0.2519 0.2494 Que (1) 0.2196 0.2219 0.2228 0.2237 Queue 1 p (2) 0.2004 0.1986 0.1970 0.1989 1 (3) 0.1835 0.1772 0.1742 0.1761 I? (4) 0.1556 0.1553 0.1541 0.1521 uP2(0) 0.4392 0.4621 0.4449 0.4422 Queue 2 I P(1) 0.3312 0.3200 0.3220 0.3275 P (2) 0.2296 0.2179 0.2332 0.2302 P (0) 0.2820 0.2939 0.2975 0.2955 P (1) 0.2214 0.2183 0.2231 0.2224 Queue P (2) 0.1708 0.1621 0.1672 0.1673 0 P (3) 0.1294 0.1204 0.1254 0.1259 P (4) 0.1963 0.2053 0.1869 0.1888 max. abs. deviation 0.0000 0.0229 0.0155 0.0135 avg. abs. deviation 0.0000 0.0080 0.0062 0.0047 throughput 4.9184 4.9430 4.9174 4.9314

Table 2 Problem | =N2=2, N=3 \=~=2, g =g2=3, g -=4 Description Measure Exact Altiok Algo. 1 Algo. 2 P (0) 0.3921 0.4205 0.4008 0.3972 Queue P (1) 0.3425 0.3283 0.3291 0.3353 i=1,2 1 t (2) 0.2653 0.2512 0.2702 0.2674 P (0) 0.2551 0.2512 0.2702 0.2674 Queue P (1) 0.2248 0.2091 0.2222 0.2212 Queue 0 P (2) 0.1891 0.1740 0.1828 0.1830 p (3) 0.3310 0.3657 0.3248 0.3284 max. abs. deviation 0.0000 0.0347 0.0151 0.0123 avg. abs. deviation 0.0000 0.0180 0.0082 0.0056 throughput 2.9388 2.9952 2.9193 2.9303

Table 3 Problem E =N2 =N3=N4=3 N =5 =20 Description =2 =3 d =4 =5 =4 g2 5 p3=6 4 =7 Measure Simulation Altiok Algo. 1 Algo. 2 Queue P(0)0.5200 0.5314 0.5255 0.5250 1 P (1) 0.2720 0.2673 0.2680 0.2695 P (2) 0.1399 0.1341 0.1367 0.1368 P_(3) 0.0680 0.0672 0.0697 0.0687 IPji'i) T?0.4466 0.4558 0.4501 0.4492 Queue P2(1) Queue P21) 0.2706 0.2764 0.2763 0.2779 2 P() 0.1732 0.1671 0.1696 0.1702 ~2 0.1094 0.1006 0.1041 0.1028 Queue P3(0) 0.4116 0.4095 0.4046 0.4036 3 P(1) 0.2741 0.2774 0.2767 0.2783 P3(2) 0.1937 0.1873 0.1892 0.1901 3(_____ 0.1204 0.1257 0.1294 0.1280 P4(0) 0.3765 0.3780 0.3745 0.3734 Queue P4(1) 0.2780 0.2760 0.2751 0.2765 4 P4 () 0.1990 0.2009 0.2020 0.2031 4 P,3 0.1462 0.1451 0.1484 0.1470 P (0) 0.3715 0.3833 0.3856 0.3847 Q ueuP (1) 0.2468 0.2376 0.2404 0.2402 Queue P (2) 0.1547 0.1473 0.1498 0.1500 0 ( 0.1094 0.0913 0.0934 0.0936 P ^(4) 0.0563 0.0566 0.0582 0.0585 P (5 0.0619 0.0839 0.0726 0.0731 P(6) max. abs. deviation 0.0000 0.0220 0.0160 0.0158 avg. abs. deviation 0.0000 0.0066 0.0054 0.0053 throughput 12.3232 12.3355 12.2886 12.3070 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ii,

Table 4 Problem Ni =5 (i=0,1,2,3,4) X1=X3=2 X2=4=1 Description A, =L=3 = =Ui=2 i =8 Measure Simulation Altiok Algo. 1 Algo. 2 Queue Pi(0) 0.3239 0.3436 0.3334 0.3314 i=1,3 Pi(1) 0.2531 0.2380 0.2364 0.2388 Pi(2) 0.1649 0.1667 0.1676 0.1693 Pi(3) 0.1157 0.1155 0.1188 0.1193 Pi (4) 0.0857 0.0798 0.0842 0.0838 Pi (5) 0.0563 0.0545 0.0597 0.0574 Pi(0) 0.5002 0.5012 0.4846 0.4837 Queue P, (1) 0.2627 0.2550 0.2547 0.2580 i=,4 P, (2) 0.1355 0.1291 0.1339 0.1345 PF (3) 0.0599 0.0652 0.0704 0.0696 P1 (4) 0.0299 0.0329 0.0370 0.0360 P, (5) 0.0113 0.0165 0.0194 0.0182 P (0) 0.2675 0.2814 0.2847 0.2833 P (1) 0.2183 0.2057 0.2110 0.2104 Queue P (2) 0.1721 0.1503 0.1564 0.1563 0 PP (3) 0.1049 0.1099 0.1159 0.1161 P (4) 0.0911 0.0803 0.0859 0.0863 P (5) 0.1457 0.1725 0.1462 0.1476 max. abs. deviation 0.0000 0.0268 0.0172 0.0165 avg. abs. deviation 0.0000 0.0091 0.0080 0.0075 throughput 5.7522 5.7490 5.7224 5.7340

Table 5 Problem 1 1 = N = oo N =3 i1 =k 2= =2 2 -1 Description 2 2-3 21-t2 iL=1 Measure Simulation Altiok Algo. 1 Algo. 2 P (0) 0.2563 0.2824 0.2545 0.2545 P. (1) 0.1999 0.2055 0.1898 0.1949 Queue,e P (2) 0.1412 0.1476 0.1415 0.1454 i=1,2 Pi (3) 0.1077 0.1053 0.1055 0.1074 P (4) 0.0676 0.0750 0.0786 0.0791 P (5) 0.0600 0.0533 0.0586 0.0581 P (0) 0.3419 0.3333 0.3333 0.3333 Queue P (1) 0.2374 0.2363 0.2412 0.2412 0 PP (2) 0.1704 0.1676 0.1746 0.1746 P (3) 0.2500 0.2628 0.2509 0.2509 max. abs. deviation 0.0000 0.0261 0.0110 0.0115 avg. abs. deviation 0.0000 0.0080 0.0044 0.0042 throughput 0.6667 0.6667 0.6667 0.6667

Table 6 Problem Ni =o (=1,2,3,4) N =5 ==2 =1 Description = s^ =3 = = =2 g =8 Measure Simulation Altiok Algo. 1 Algo. 2 Queue Pi(0) 0.2899 0.2985 0.2824 0.2821 i=1,3 Pi(1) 0.2154 0.2110 0.2031 0.2068 Pi(2) 0.1355 0.1481 0.1460 0.1487 Pi(3) 0.1070 0.1036 0.1050 0.1061 Pi(4) 0.0747 0.0723 0.0755 0.0755 Pi (5) 0.0600 0.0504 0.0543 0.0536 Pi(O) 0.4712 0.4913 0.4677 0.4676 Queue P (1) 0.2570 0.2509 0.2490 0.2534 i=2,4 PI (2) 0.1269 0.1274 0.1325 0.1335 P (3) 0.0691 0.0645 0.0706 0.0697 Pl (4) 0.0379 0.0326 0.0376 0.0363 _ (5) 0.0185 0.0165 0.0200 0.0189 P (0) 0.2588 0.2500 0.2510 0.2509 P (1) 0.1874 0.1919 0.1970 0.1970 Queue P (2) 0.1508 0.1474 0.1546 0.1546 0 P (3) 0.1056 0.1132 0.1214 0.1214 P (4) 0.0957 0.0868 0.0953 0.0953 P (5) 0.2014 0.2107 0.1807 0.1809 max. abs. deviation 0.0000 0.0201 0.0207 0.0205 avg. abs. deviation 0.0000 0.0068 0.0065 0.0062 throughput 6.0000 6.0000 6.0000 6.0000

19 REFERENCES [1] Akyildiz,I.F., "Analysis of Closed Queuing Networks with Blocking", CS Dept., 85022(1985),Lousiana State Univ.,1985 [2] Altiok,T.,"Approximate Analysis of Exponential Tandem Queues with Blocking",Europ. J. Oper. Res. 11, 390-398,1982 [3] Altiok,T.,and H.G. Perros, "Open Networks of Queues with Blocking: Split and Merge Configurations",AIIE Trans. 18,251-261,1986 [4] Bocharov,P.P. and G.P. Rokhas, "On an Exponential Queueing System in Series with Blocking", Problems of Control and Information Theory 9,441-455,1980 [5] Boxma.O.J. and A.G.Konheim, "Approximate Analysis of Exponential Queueing Systems with Blocking,"Acta Informatica 15,19-66,1981 [6] Brandwajn,A. and Y.L.Jow. "An Approximate Method foi- Tandem Queues with Blocking",Manuscript,Amdahl Corp.,1985 [7] Caseau,P. and G.Pujolle, "Throughput Capacity of a Sequence of Queues with Blocking due to Finite Waiting Room."IEEE Trans. Soft. Eng. SE-5,631-642.1979 [8] Foster,F.G. and H.G. Perros, "On the Blocking Process in Queue Networks". Europ. J. Oper. Res. 5,276-283,1980 [9] GershwinS.B., "An Efficient Decomposition Method for the Approximate Evaluation of Tandem Queues with Finite Storage and Blocking", Manuscript,Lab. for Information and Decision Sciences,MIT,1983 [10] Gross,D., and C.M.Harris, Fundamentals of Queueing Theory, New York, John Wiley and Sons, 1985 [11] Hillier,F.S. and R. Boling, "Finite Queues in Series with Exponential or Erlang Service Times - Numerical Approach", Oper. Res. 15,286-303,1967 [12] Labetoulle,J.and G.Pujolle, "Isolation Method in a Networks of Queues", IEEE

UNIVERSITY OF MICHIGAN 39015 04732 7120 20 Trans. Soft. Eng. SE-6,1980 [13] Onvural,R.O. and H.G. Perros, "On Equivalencies of Blocking Mechanisms in Queueing Networks with Blocking", Oper. Res. Letter 5.293-297,1986 [14] Perros,H.G., "A Servey of Queueing Networks with Blocking-Part I", Computer Science Report,N.C.State Univ.,1986 [15] Peross,H.G. and T. Altiok, "Approximate Analysis of Open Networks of Queues with Blocking: Tandem Configurations",IEEE Trans on Soft. Eng., SE-12,1986 [16J Perros.H.G. and T. Altiok, "Approximate Analysis of Arbitrary Configurations of Open Queueing Networks with Blocking",to Appear in the Annals of OR [17] Perros,H.G. and P.M. Snyder, "A Computationally Efficient Approximation Algorithm for Analyzing Open Queueing Networks with Blocking",Manuscrlpt. CS Dept., N.C. State Univ.,1986 [18] Pollock,S.M.,J.R.Birge and J.M.Alden, "Approximation Analysis for Open Tandem Queues with Blocking: Exponential and General Service Distributions". Technical Rcport,IOE Dept..85-30, Univ. of Michigan, 1985 [19] Suri,R. and G.W.Diehl, "A Variable Buffer-size Model and its use in Analytic Closed Queueing Networks with Blocking,"Proc. ACM SIGMETRICS on Measurement and Modelling of Computer Systems, 134-142,1984 [20] Suri,R. and G.W.Diehl, "A Variable Buffer-size Model and its use in Analyzing Closed Queueing Networks with Blocking",Management Sci.,Vol 32, No.2.1986 [21] Takahashi,Y,H.Miyahara and T.Hasegawa, "An Approximation Method for Open Restricted Queueing Networks",J.Oper. Res. 28,594-602,1980 [22] Yao,D. and J.A.Buzacott, "Modelling a Class of Flexible Manufacturing Systems with Reversible Routing",Manuscript,I.E.Dept., Columbia Univ.,1983