Analysis of two-machine lines with multiple failure modes.

**********

Tullio Tolio (1)

Andrer MattA (1)

Stanley B. Gershwin (2)

This paper presents an analytical method for evaluating the performance of production lines with a finite buffer and two unreliable machines. Unlike in earlier papers, each machine can

fail in more than one way. For each failure mode, geometrically distributed times to failure and times to repair are specified. The method evaluates the steady-state probabilities of the states of the system with a computational effort that depends only on the number of failure modes considered and not on the capacity of the buffer. A comparison of performance of the method with those obtained with existing techniques that consider only one failure mode is reported.

1. Introduction

The paper presents an analytical evaluation of the performance of two-machine lines with deterministic processing times, multiple failure modes, and finite buffer capacity.

The expression 'multiple failure modes' means that each machine of the line can fail in different ways. Each mode of failure is characterized by a specific MTTF (Mean Time between Two successive Failures) and MTTR (Mean Time to Repair a Failure). This situation is common in practice because machines are made of components which fail more or less frequently producing more or less severe failures. In automatic assembly lines this consideration is even more apparent because each assembly station is normally composed of different devices which co-operate to complete the operation assigned to the station. A station may be comprised of insertion and fastening devices, feeding devices and a manipulator to move the subassemblies. The reliabilities of these devices are different and the ways they are repaired once failed are also different. These considerations motivate the introduction of multiple failure modes explicitly in the model. Alternatively one could deal with the problem of different failure modes by averag ing the effects of the various types of failure. However, since most analytical models assume exponentially or geometrically distributed MTBF and MTTR, by considering the averages of these parameters over the different failure modes, we obtain the correct means but totally wrong variances. This error on the variances associated with MTBF and MTTR can adversely affect the applicability of the model especially when the buffer capacity between the machines is not very large.

There have been many models of two-machine lines with deterministic processing times, finite buffers and machine failures (Ignall and Silver, 1977; Shantikumar and Tien, 1983; Jafari and Shantikumar, 1987). The earliest was by Buzacott (1967). The model described here is an extension of the deterministic processing time model described in Gershwin (1994), which itself was a modification of Buzacott's model.

Although this model is limited to two-machine, one buffer systems, it is worth investigating because such simple systems have been used as the building blocks of decomposition analyses of larger systems (Gershwin, 1987; Dallery et al., 1988; Tolio and Matta, 1998). Different types of building blocks to be used in decomposition of long lines have been proposed by Gershwin and Schick (1983) and by Yeralan and Tan (1997). For surveys of various methods proposed to analyze queuing networks with blocking, refer to Perros (1988), Dallery and Gershwin (1992) and Gershwin (1994).

The model is based on the following assumptions:

* Each part enters the system at the first machine, then goes to the buffer, then the second machine and then exits the system (see Fig. 1).

* The two machines have equal and constant processing times. Time is scaled so that the machine cycle takes one time unit. Transportation takes negligible time compared to machining times. The machines start their operations at the same instant.

* The buffer between the machines has finite capacity.

* A machine whose upstream buffer is empty is said to be starved. A machine whose downstream buffer is full is said to be blocked.

* The upstream machine is never starved and the downstream machine is never blocked.

* A machine which is not processing a workpiece (i.e., which is starved or blocked) cannot fail.

* Whenever a machine begins processing a workpiece, there is a constant probability that it fails in each mode.

* A machine cannot be failed in more than one mode at the same time.

* If a machine is failed in a given mode at the beginning of a cycle there is a constant probability that it is repaired during that cycle.

* By convention, repairs and failures occur at the beginning of time units and changes in buffer levels take place at the end of the time units.

* Workpieces are not destroyed or rejected at any stage in the line. Partly processed workpieces are not added into the line. When a machine breaks down, the workpiece it was operating on is returned to the upstream storage to wait for the machine to be repaired so that processing can resume.

2. Notation

The state of the system is (n, [[alpha].sub.1] [[alpha].sub.2]) where n is the buffer level (0 [less than or equal to] n [less than or equal to] N), [[alpha].sub.1] is the repair state of the upstream machine, and [[alpha].sub.2] is the repair state of the downstream machine. If the upstream machine is operational, [[alpha].sub.1] = 1. Otherwise [[alpha].sub.1] = [u.sub.i] for some i = 1, ... , s, where [u.sub.i] represents the failure mode of the machine. Similarly [[alpha].sub.2] can assume the values 1, [d.sub.1], ... , [d.sub.t] The steady-state probability of the system being in state (n,[[alpha].sub.1],[[alpha].sub.2]) is indicated by p(n,[[alpha].sub.1], [[alpha].sub.2]).

Since repairs and failures occur at the beginning of time units and changes in buffer level take place at the end of the time units, n ([tau] + 1) the level of the buffer at the time [tau] + 1 is:

n([tau] + 1) = n([tau]) + [I.sub.1]([tau] + 1) - [I.sub.2] ([tau] + 1), (1)

where

[I.sub.1] ([tau] + 1) = {1 if [[alpha].sub.1] ([tau] + 1) = 1 and n (tau) < N, 0 otherwise

[I.sub.2] ([tau] + 1) = {1 if [[alpha].sub.2] ([tau] + 1) = 1 and n ([tau]) > 0, 0 otherwise

where [tau] is the time step. If the upstream machine is operational, it can fail in mode [u.sub.i], with probability [p.sup.[u.sub.i]] while attempting to perform an operation. When the upstream machine is failed in mode [u.sub.i], it can get repaired during a time unit with probability [r.sup.[u.sub.i]]. Similarly [p.sup.[d.sub.j]] and [r.sup.[d.sub.j]] represent respectively failure and repair probabilities for the failure modes of the downstream machine. The total failure probability [P.sup.U] of the upstream machine, i.e., the probability of failure regardless of the mode in which the machine fails, is given by [P.sup.U] = [summation over (s/i=1)][p.sup.[u.sub.i]]. Similarly, the total failure probability [P.sup.D] of the downstream machine is [P.sup.D] = [summation over (t/j=1)][p.sup.[d.sub.j]]. The sets of parameters [p.sup.[u.sub.i]] and [p.sup.[d.sub.j]] must be such that [P.sup.U] < 1 and [P.sup.D] < 1.

3. Performance measures

The most important performance measures are the production rate and the average inventory of the system. The production rate [E.sub.2], in parts per time step, is the steadystate probability that the second machine successfully produces a part. Because flow is conserved, it is also equal to [E.sub.1], the steady-state probability that the first machine successfully produces a part.

The average production rate is defined (Gershwin, 1994) as:

[E.sub.1] = prob([[alpha].sub.1]([tau] + 1) = 1 and n([tau]) < N),

and

[E.sub.2] = prob([[alpha].sub.2]([tau] + 1) = 1 and n([tau]) > 0),

where [tau] is the time step. These expressions are equivalent to

[E.sub.1] = prob([[alpha].sub.1] = 1 and n < N)

= [FORMULA NOT REPRODUCIBLE IN ASCII] (2)

and

[E.sub.2] = prob([[alpha].sub.2] = 1 and n > 0)

= [FORMULA NOT REPRODUCIBLE IN ASCII]

The average buffer level is given by

[FORMULA NOT REPRODUCIBLE IN ASCII] (4)

Therefore in order to evaluate the performance measures of the system we must know all the steady-state probabilities.

4. Solution methodology

The total number of states of the system is M = (s + 1)(t + 1)(N + 1). Therefore, in order to find the probabilities of the various states it is necessary to solve a Markov chain with M states. This task can be accomplished by solving a linear system of M equations in M unknowns. This approach, however, can easily become impractical unless N is very small. Therefore the paper presents a solution methodology which entails only the evaluation of the roots of a polynomial of degree s + t (i.e., the total number of failure modes of the two machines) and the solution of a linear system of s + t - 1 equations. Therefore the computational effort depends only on the number of failure modes considered and not on N, the capacity of the buffer.

The solution methodology proposed is an extension to the case of multiple failure modes described in Gershwin (1994). The basic idea is to analyze the Markov chain (Fig. 2) and make a guess of the form that internal state probabilities should assume. By substituting this guess into the internal equations (i.e., those with 2 [less than or equal to] n [less than or equal to] N - 2), a set of t + s solutions (i.e., vectors that satisfy the internal equations) can be found. If the guess is correct, it must then be possible to find a linear combination of these solutions that also satisfies the boundary conditions. If this is the case the solution of the Markov chain has been found.

4.1. Internal states

Internal states are those in which 2 [less than or equal to] n [less than or equal to] N - 2. For these states, we can write the internal equations listed in the following (Fig. 2).

4.1.1. Internal equations

p(n, [u.sub.i], [d.sub.j]) = p(n, [u.sub.i], [d.sub.j])(1 - [r.sup.[u.sub.i]])(1 - [r.sup.[d.sub.j]]) + p(n, [u.sub.i], 1)(1 - [r.sup.[u.sub.i]])[p.sup.[d.sub.j]] + p(n, 1, [d.sub.j])[p.sup.[u.sub.i]](1 - [r.sup.[d.sub.j]]) + p(n, 1, 1)[p.sup.[u.sub.i]][p.sup.[d.sub.j]]. (5)

[FORMULA NOT REPRODUCIBLE IN ASCII] (6)

[FORMULA NOT REPRODUCIBLE IN ASCII] (7)

[FORMULA NOT REPRODUCIBLE IN ASCII] (8)

4.1.2. Solution of the internal equations

We guess that the internal state probabilities assume the form

p(n, 1, 1) = [X.sup.n],

p(n, 1, [d.sub.j]) = [X.sup.n][D.sub.j],

p(n, [u.sub.i], 1]) = [X.sup.n][U.sub.i],

p(n, [u.sub.i], [d.sub.j]) = [X.sup.n][U.sub.i][D.sub.j], i = 1,...,s, j = 1,..., t,

2 [less than or equal to] n [less than or equal to] N - 2, (9)

where X, [U.sub.i], and [D.sub.j] are 1 + s + t constants to be evaluated. By substituting (9) into (5), (6), (7), and (8), we obtain:

[X.sup.n][U.sub.i][D.sub.j] = [X.sup.n][U.sub.i][D.sub.j](1 - [r.sup.[u.sub.i]]) (1 - [r.sup.[d.sub.j]]) + [X.sup.n][U.sub.i] (1 - [r.sup.[u.sub.i]])[p.sup.[d.sub.j]] + [X.sup.n][D.sub.j][p.sup.[u.sub.i]] (1 - [r.sup.[d.sub.j]]) + [X.sup.n][p.sup.[u.sub.i]][p.sup.[d.sub.j]],

i = 1,...,s; j = 1,...,t. (10)

[FORMULA NOT REPRODUCIBLE IN ASCII] (11)

[FORMULA NOT REPRODUCIBLE IN ASCII] (12)

[FORMULA NOT REPRODUCIBLE IN ASCII] (13)

After some manipulations Equations (10), (11), (12) and (13) can be written as:

[U.sub.i][D.sub.j] = [[U.sub.i](1 - [r.sup.[u.sub.i]]) + [p.sup.[u.sub.i]]][[D.sub.j](1 - [r.sup.[d.sub.j]]) + [p.sup.[d.sub.j]]],

i = 1,...,s; j = 1,...,t. (14)

1 = [1 - [P.sup.U] + [summation over (s/i=1)] [U.sub.i][r.sup.[u.sub.i]]][1 - [P.sup.D] + [summation over (t/j=1)] [D.sub.j][r.sup.[d.sub.j]]]. (15)

[U.sub.i]/X = [[U.sub.i](1 - [r.sup.[u.sub.i]]) + [p.sup.[u.sub.i]]] [1 - [P.sup.D] + [summation over (t/j=1)][D.sub.j][r.sup.[d.sub.j]]],

i = 1,...,s. (16)

[D.sub.j]X = [1 - [P.sup.U] + [summation over (s/i=1)] [U.sub.i][r.sup.[u.sub.i]]][[D.sub.j])1 - [r.sup.[d.sub.j]]) + [p.sup.[d.sub.j]],

j = 1,...,t. (17)

As already mentioned, [U.sub.i], [D.sub.j] and X form a set of s + t + 1 unknowns. Since Equation (14) is the product of (16) and (17), there is the same number of equations.

Equation (14) can be written

1 = [[U.sub.i](1 - [r.sup.[u.sub.i]]) + [p.sup.[u.sub.i]]/[U.sub.i]] [[D.sub.j](1 - [r.sup.[d.sub.j]]) + [p.sup.[d.sub.j]]/[D.sub.j]],

i = 1,...,s; j = 1,...,t, (18)

and implies that:

[[U.sub.i](1 - [r.sup.[u.sub.i]]) + [p.sup.[u.sub.i]]/[U.sub.i]] = K, i = 1,...,s (19)

[[D.sub.j](1 - [r.sup.[d.sub.j]]) + [p.sup.[d.sub.j]]/[D.sub.j]] = 1/K, j = 1,...,t, (20)

in which K is not a function of I or j. From (19) and (20) we can write

[U.sub.i] = [p.sup.[u.sub.i]]/K - 1 + [r.sup.[u.sub.i]], i = 1,...s. (21)

[D.sub.j] = [p.sup.[d.sub.j]]/(1/K) - 1 + [r.sup.[d.sub.j]], j = 1,...,t. (22)

By introducing these expressions into (15) we obtain:

1 = [1 - [P.sup.U] + [summation over(s/i=1)] [p.sup.[u.sub.i]][r.sup.[u.sub.i]]/K - 1 + [r.sup.[u.sub.i]]] X [1 - [P.sup.D] + [summation over (t/j=1)] [p.sup.[d.sub.j]][r.sup.[d.sub.j]]/(1/K) - 1 + [r.sup.[d.sub.j]]]. (23)

This is an R = s + t order polynomial in K. If we define with [K.sub.m] (m = 1,...,s + t) to be the mth root of the polynomial, we can find the corresponding values of [U.sub.i,m], [D.sub.j,m] and [X.sub.m] by means of (21), (22) and (17) which can be rewritten as:

[X.sub.m] = [1 - [P.sup.U] + [summation over (s/i=1)] [p.sup.[u.sub.i]][r.sup.[u.sub.i]]/[K.sub.m] - 1 + [r.sup.[u.sub.i]]] 1/[K.sub.m],

m = 1,...,s+ t.

[U.sub.i,m] = [p.sup.[u.sub.i]]/[K.sub.m] - 1 + [r.sup.[u.sub.i]], i = 1,...,s.

[D.sub.j,m] = [p.sup.[d.sub.j]]/(1/[K.sub.m]) - 1 + [r.sup.[d.sub.j]], j = 1,...,t. (24)

An assumption we are making here is that all the roots [K.sub.m], of the polynomial are real. This is important because if some roots were complex the steady-state probabilities would show a periodic pattern not consistent with the real behavior of the system. We demonstrate that this assumption is true in Appendix A.

It is simple to demonstrate that one of the roots of (23) is equal to one and we call this root [K.sub.R]. If we substitute [K.sub.R] into (21), (22) and (24), we obtain

[U.sub.i,R] = [p.sup.[u.sub.i]]/[r.sup.[u.sub.i]], [D.sub.j,R] = [p.sup.[d.sub.j]]/[r.sup.[d.sub.j]], [x.sub.R] = 1. (25)

Since it is possible to find parameters such that the guess made in (9) satisfies the internal equations, the next step is to verify if it is possible to find a linear combination of these solutions that also satisfies the boundary conditions.

4.2. Boundary states

The assumptions of the model imply that certain boundary states are transient, that is, that they have zero steady-state probability. Transient states cannot be reached from any state except possibly other transient states.

1. The states (0,1, [d.sub.j]) and (0,1,1) are transient because they cannot be reached from any state.

2. The state (0, [u.sub.i], [d.sub.j]) is transient because it can be reached only from itself or (0, 1, [d.sub.j]).

3. The state (1, 1, [d.sub.j]) is transient because it can be reached only from (0, [u.sub.i], [d.sub.j] or (0, 1, [d.sub.j].

Similarly, (N, [u.sub.i], [d.sub.j]), (N, [u.sub.i], 1), (N, 1,1), and (N - 1, [u.sub.i], 1) are transient. The following is a list of all the transient states:

(0,1,1) (N, 1,1)

(0,1,[d.sub.j]) (1, 1, [d.sub.j]) j = 1,...,t,

(N - 1, [u.sub.i], 1) (N, [u.sub.i], 1) I = 1,..., s,

(0, [u.sub.i], [d.sub.j]) (N, [u.sub.i], [d.sub.j]) I = 1,...,s, j = 1,...,t. (26)

For the remaining boundary states (i.e., those that are not transient) we can write the boundary transition equations.

4.2.1 Lower boundary equations

[FORMULA NOT REPRODUCIBLE IN ASCII] (27)

[FORMULA NOT REPRODUCIBLE IN ASCII] (28)

[FORMULA NOT REPRODUCIBLE IN ASCII] (29)

[FORMULA NOT REPRODUCIBLE IN ASCII] (30)

4.2.2 Upper boundary equations

[FORMULA NOT REPRODUCIBLE IN ASCII] (31)

[FORMULA NOT REPRODUCIBLE IN ASCII] (32)

[FORMULA NOT REPRODUCIBLE IN ASCII] (33)

[FORMULA NOT REPRODUCIBLE IN ASCII] (34)

4.2.3. Solution of the boundary equations

If guess (9) is correct, it must be possible to find a linear combination of the R different solutions found for the internal equations that satisfies all the boundary conditions (in total there are 2st + 3s + 3t + 2 boundary equations). In other words, the values of the probabilities of the internal states must assume the form:

p(n, 1,1) = [simmuation over (R/m=1)] [C.sub.m][X.sup.n.sub.m],

p(n, 1, [d.sub.j]) = [simmuation over (R/m=1)] [C.sub.m][X.sup.n.sub.m][D.sub.j,m],

p(n, [u.sub.i], 1) = [simmuation over (R/m=1)] [C.sub.m][X.sup.n.sub.m][U.sub.i,m],

p(n, [u.sub.i], [d.sub.j]) = [simmuation over (R/m=1)] [C.sub.m][X.sup.n.sub.m][U.sub.i,m][D.sub.j,m],

where m = 1,...,R,

i = 1...s,

j = j...t,

2 [less than or equal to] n [less than or equal to] N - 2, (35)

where the values of [C.sub.m], m = 1,... , R, are chosen so that the boundary conditions are satisfied.

The probabilities p(1,[u.sub.i], 1) and p(N - 1, 1, [d.sub.j]), being the right members of (29) and (32) composed of only internal steady-state probabilities, can be expressed as internal solutions. Therefore it is possible, by using (27), (28), (29), (31), (32) and (34) to express the probabilities of the boundary states as a function of the constants [C.sub.1],... , [C.sub.m] as shown below (notice that (30) and (33) are still not used):

p(0, [u.sub.i], [d.sub.j]) = 0, i = 1,..., s, j = 1,..., t. (36)

[FORMULA NOT REPRODUCIBLE IN ASCII] (37)

p(0, 1, [d.sub.j]) = 0, j = 1,..., t. (38)

p(0, 1, 1,) = 0. (39)

[FORMULA NOT REPRODUCIBLE IN ASCII] (40)

[FORMULA NOT REPRODUCIBLE IN ASCII] (41)

p(1, 1, [d.sub.j]) = 0, j = 1,..., t. (42)

[FORMULA NOT REPRODUCIBLE IN ASCII] (43)

[FORMULA NOT REPRODUCIBLE IN ASCII] (44)

p(N - 1, [u.sub.j], 1) = 0, I = 1,...,s. (45)

[FORMULA NOT REPRODUCIBLE IN ASCII] (46)

[FORMULA NOT REPRODUCIBLE IN ASCII] (47)

p(N, [u.sub.j], [d.sub.j]) = 0. j = 1,...,t. (48)

p(N, [u.sub.j], 1) = 0, i = 1,...,s. (49)

[FORMULA NOT REPRODUCIBLE IN ASCII] (50)

p(N, 1, 1) = 0. (51)

Therefore the constants [C.sub.m] are the only unknowns (in total s + t) that we must evaluate. Notice that Equations (37) and (43) are true for any j = 1, ... , t while (47) and (50) are true for any i = 1,...,s.

If we add Equations (27), (28), (30), and P(2, 1, [d.sub.j]) for i= 1,...,s, j = 1,...,t, and we cancel everything that can be canceled we obtain:

[FORMULA NOT REPRODUCIBLE IN ASCII] (52)

Similarly if we add Equations (31), (33), (34) and p(N-2,[u.sub.i],1) for i= 1,...,s, j = l,...,t, and we cancel everything that can be canceled we obtain:

[FORMULA NOT REPRODUCIBLE IN ASCII] (53)

Substituting Equations (35) and (41) into (52) we find:

[FORMULA NOT REPRODUCIBLE IN ASCII] (54)

Similarly, substituting Equations (35) and (46) into (53) we find:

[FORMULA NOT REPRODUCIBLE IN ASCII] (55)

We show in Appendix B that for i = 1,...,s we obtain:

[FORMULA NOT REPRODUCIBLE IN ASCII]

By substituting this equation and (20) into (17) and by using the results of Appendix B, it is possible to demonstrate the following relationship:

[FORMULA NOT REPRODUCIBLE IN ASCII] (56)

(For p = R, the solution is given in (25) in the previous section.) As a consequence, if we divide Equation (54) by [X.sub.R] and Equation (55) by [X.sup.N-2.sub.R], both equations reduce to:

[FORMULA NOT REPRODUCIBLE IN ASCII] (57)

By considering (25), we find that if the two machines are not identical,

[FORMULA NOT REPRODUCIBLE IN ASCII] (58)

This fact together with (57) implies that [C.sub.R] = 0. Therefore the Rth solution of the polynomial obtained from the internal equations can be discarded and the number of unknowns is reduced to s + t - 1.

By substituting the probabilities of the boundary states (36)-(51) into (30) and (33) we obtain:

[FORMULA NOT REPRODUCIBLE IN ASCII] (59)

and

[FORMULA NOT REPRODUCIBLE IN ASCII] (60)

Finally, the sum of all the state probabilities must satisfy the normalization equation:

[FORMULA NOT REPRODUCIBLE IN ASCII] (61)

(59), (60) and (61) is a linear system of s + t + 1 equations in s + t - 1 unknowns but only s + t - 1 equations are linearly independent (in particular we cannot consider one equation of (59) and one of (60)). By solving the linear system we obtain the constants [C.sub.m] (m = 1,..., s + t - 1), therefore we are able to evaluate the steady-state probabilities and the performance measures by using (2) or (3) and (4).

5. Algorithm

On the basis of the analysis carried out so far, to assess the performance of a deterministic two-machine line with multiple failure modes, the following steps must be performed:

Step 1. Numerical evaluation of the roots [K.sub.m] (m = 1,..., R) of the polynomial (23). One of the roots is given by (25).

Step 2. For each root [K.sub.m] evaluation of the constants [U.sub.i,m] (i = 1,..., s) [D.sub.j,m] (j = 1,..., t) and [X.sub.m] by means of (21), (22), (24) respectively.

Step 3. Solution of the linear system based on (59), (60) and (61) where expressions (35), (36)-(51) have been substituted. This is a system of s + t - 1 equations in the unknowns [C.sub.m] (m = 1,... R - 1).

Step 4. Evaluation of the steady-state probabilities of all the states. For the internal states they are given by (35) and for the boundary states by (36)-(51).

Step 5. Evaluation of the performance measures (throughput, buffer level) from the expressions (2) or (3) and (4) in Section 3.

6. Numerical examples

The possibility of defining different failure modes for each machine leads to a better evaluation of the average throughput and the average buffer level of two-machine line systems where machines can break down in more than one mode. In this section we compare the method described in this paper with the one proposed by Gershwin (1994), that considers only one failure mode for each machine. With this last method, if a given machine of the real system has different ways to fail and get repaired, a simplified representation of the machine with only one "average" failure mode must be introduced. This average failure mode is chosen so that the efficiency of the machine in isolation is preserved.

The two methods can be compared by analyzing the behavior of a transfer line composed of two machines: the upstream machine can fail into two failure modes while the downstream machine can fail only into one. Let [p.sup.[u.sub.1]] and [p.sup.[u.sub.2]] be the probabilities of failure of the upstream machine, [r.sup.[u.sub.1]], [r.sup.[u.sub.2]] the corresponding probabilities of repair of the upstream machine and [p.sub.d], [r.sup.d] the probabilities of failure and repair of the downstream machine. The efficiency in isolation mode of a machine with F failure modes is given by:

e = 1/1 + [simmuation over (F/i=1)] ([p.sub.i]/[r.sub.i]). (62)

Therefore the efficiencies in isolation mode of the machines are:

[e.sup.u] = 1/[p.sup.[u.sub.1]]/[r.sup.[u.sub.1]])+([P.sup.[u.sub.2]]/[r.sup.[u.s ub.2]], [e.sup.d] = 1/1 + ([p.sub.d]/[r.sup.d])

The model of Gershwin considers machines which can fail into one failure mode, so the failures of the upstream machine are collected into one average failure (1) preserving the efficiency in isolation mode, as shown in the following equations:

[P.sup.u] = [P.sup.[u.sub.1]] + [P.sup.[u.sub.2]],

1/[r.sup.u] = [p.sup.[u.sub.1]]/[p.sup.[u.sub.1]]+[p.sup.[u.sub.2]]/1/[r.sup.[u.sub .1]] + [p.sup.[u.sub.2]]/[p.sup.[u.sub.2]]+[p.sup.[u.sub.2]] 1/[r.sup.[u.sub.2]] (63)

Since this simplification can lead to approximated estimates of the performance of the system, the purpose of this section is to quantify the gap between the method of Gershwin that must introduce this approximation and the method proposed in the paper that keeps the various failure modes separated. In particular we investigate various cases obtained by keeping constant the efficiency in isolation and the failure probabilities of both the upstream and downstream machines while changing the repair probabilities of the two failure modes of the upstream machine. The average production rate of the system as a function of [r.sup.[u.sub.1]] is shown in Fig. 3. As [r.sup.[u.sub.1]] increases [r.sup.[u.sub.2]] must decrease because [e.sup.u] is constant. It can be seen that when [r.sup.u] = [r.sup.[u.sub.1]] = [r.sup.[u.sub.2]] = 0.09 both the Gershwin and the proposed model give the same results. In all the other cases the Gershwin model overestimates the average production rate (in the right scale of the graph the percentage difference between the t wo models is provided [DELTA]% = 100 x ([[theta].sub.P] - [[theta].sub.G] /[[theta].sub.P). This behavior is due to the fact that when [r.sub.[u.sup.1]] [not equal to] [r.sup.[u.sup.2]] (even if the efficiency is kept constant) one of the two modes has a repair probability lower than [r.sub.u] which means a longer MTTR and high probability of starvation for the downstream machine.

As already mentioned the curves of Fig. 3 and Fig. 4 are obtained by keeping constant [e.sub.u],[p.sub.[u.sup.1]],[p.sub.[u.sup.2]] and the characteristics of the downstream machine. Keeping the same value of [e.sub.u] and choosing different values for [p.sub.[u.sup.1]] and [p.sub.[u.sup.2]] we obtain similar curves to the ones already shown. In particular Fig. 5 shows a family of curves obtained with the same [e.sub.u] as before but with different combination of [p.sub.[u.sup.1]] and [p.sub.[u.sup.2]] so that [p.sub.[u.sup.1]] + [p.sub.[u.sup.2]] is constant. Again Gershwin's method gives the same estimates for all the cases considered because in all the cases [e.sup.u] and [e.sup.d] are kept constant.

Other problems obtained by varying the values of [e.sup.u] and [e.sup.d] have been studied obtaining similar results. On the whole it is possible to say that on the basis of the analysis carried out, the simplification introduced by the model with only one failure mode leads to a percentage error of 1.5% in the worst case as far as regards the average production rate, and of 18% as far as regards the average buffer level.

7. Conclusions

A method has been proposed to evaluate the performance of a two-machine line with deterministic processing times, finite buffer capacity and unreliable machines that can fail in different modes. The method provides in output the exact values of the performance measures of the system, in particular throughput and average buffer capacity.

A comparison with an existing technique that does not consider different failure modes has shown the importance of considering explicitly the different types of failures to obtain a good estimate of the performances.

Given the low computational effort required, the method can be applied as a building block for new decomposition techniques for the analysis of the behavior of long transfer lines and assembly/disassembly networks (Tolio and Matta, 1998).

(1.) Dipartimento di Meccanica, Politecnico di Milano, via Bonardi 9, 20133, Milano, Italy

(2) Department of Mechanical Engineering, Massachusetts Institute of Technology, 77 Massachusetts A venue, Cambridge, MA 02139, USA

(1.) In this particular example Gershwin's model does not make any simplification of the downstream machine because it has only one failure mode.

References

Buzacott, J. (1967) Markov chain analysis of automatic transfer line with buffer stock. PhD thesis, University of Birmingham.

Dallery, Y., David, R. and Xie, X.L. (1988) An efficient algorithm for analysis of transfer lines with unreliable machines and finite buffers. lIE Transactions.

Dallery, Y. and Gershwin, S.B. (1992) Manufacturing flow line systems: a review of models and analytical results. Queueing Systems Theory and Applications, 12(1-2), 3--94.

Gershwin, S. (1987) An efficient decomposition method for the approximate evaluation of tandem queues with finite storage space and blocking. Operations Research, 35(2), 291-304.

Gershwin, S. (1994) Manufacturing Systems Engineering, Prentice Hall, pp. 76--93.

Gershwin, S. and Schick, I. (1983) Modeling and analysis of three stage transfer lines with unreliable machines and finite buffers. Operations Research, 31(2), 354--377.

Ignall, E. and Silver, A. (1977) The output of a two-stage system with unreliable machines and limited storage. AJIE Transactions, 9(2), 183--188.

Jafari, M. and Shantikumar, J. (1987) Exact and approximate solutions to two-stage transfer lines with general uptime and downtime distributions. II E Transactions, 19(4), 412-419.

Perros, H. (1988) A survey of two-node queuing networks with blocking, Technical Report 88-06, CS Dept., North Carolina State University, Raleigh, NC.

Shantikumar, J. and Tien, C. (1983) An algorithmic solution to two-stage transfer lines with possible scrapping of units. Management Science, 29(9), 1069-1086.

Syrowicz, D. (1999) Decomposition analysis of a deterministic, multiple-part-type, multiple-failure-mode production line. Master's thesis, EECS Department, Massachusetts Institute of Technology, Cambridge, MA.

Tolio, T. and Matta, A. (1998) A method for performance evaluation of automated flow lines. Annals of CIRP.

Yeralan, S. and Tan, B. (1997) A station model for continuous material flow production systems. International Journal of Production Research, 35(9), 2525-2541.

[Figure 2 omitted]

[Figure 3 omitted]

[Figure 4 omitted]

[Figure 5 omitted]

[Figure A1 omitted]

Appendices

Appendix A: roots of the polynomial (23)

The polynomial in the equation (23)

[FORMULA NOT REPRODUCIBLE IN ASCII]

has all real roots.

Proof. Finding the roots of the polynomial means calculating the intersections of the function F(K) with the K axis. The polynomial has a particular structure since it is composed of two terms that depend only on the parameters of the upstream and downstream machines respectively (Syrowicz, 1999). By analyzing the poles of the polynomial it is possible to draw some important conclusions on the intersections of F(K) with the K axis.

It is simple to demonstrate that the number of poles of the polynomial are R = s + t and are equal to:

[[rho].sup.[u.sub.i]] = 1 [r.sup.[u.sub.i]] for I = j,..., s and 0 < K < 1,

[[rho].sup.[d.sub.j]] = 1/1 - [r.sup.[d.sub.j]] for j = 1,..., t and for K > 1.

In particular the poles originated by the upstream machine are in the interval K [psi] [0,1] while those originated by the downstream machine are in the interval K [member of] [1, [infinity]). Also it is possible to write for any s [greater than or equal to] 1 and t [greater than or equal to] 1 of the upstream and downstream machines the following limits:

[FORMULA NOT REPRODUCIBLE IN ASCII]

where the quantity [K.sub.[infinity]] is always negative. Therefore it is possible to draw for any polynomial of the form (23) a graph similar to that shown in Fig. Al. The curve F(K) has always one intersection with the K axis between two adjacent poles except for the interval between the last pole of the upstream machine and the first pole of the downstream machine where the curve has two intersections: one of the two intersections is always K = 1 (see Appendix B). In the extreme areas exterior to the poles the curve F(K) goes to the horizontal asymptote [K.sub.[infinity]] and therefore there are no roots in these regions. As a consequence the sum of the intersections with the K axis is always equal to R = s + t and we can conclude that the R roots of the polynomial are all real.

Appendix B

The solution of the internal equations gives either K = 1 or

[FORMULA NOT REPRODUCIBLE IN ASCII]

Proof. Adding up Equations (19) for i = 1,..., s we obtain:

[FORMULA NOT REPRODUCIBLE IN ASCII] (A1)

Similarly for Equations (20) for j = l,..., t we obtain:

[FORMULA NOT REPRODUCIBLE IN ASCII] (A2)

By substituting (A1) and (A2) into (15), after some manipulations we obtain the equation:

[FORMUL NOT REPRODUCIBLE IN ASCII] (A3)

which has the following two solutions:

[FORMUL NOT REPRODUCIBLE IN ASCII] (A4)

This is true for any out of the R = s + t roots of the polynomial (8). Besides by substituting (A4) and (A2) into (16) after some manipulations we obtain:

[FORMUL NOT REPRODUCIBLE IN ASCII] (68)