Performance analysis of production systems with rework loops.

1. Introduction

This paper studies production systems with rework loops. In many manufacturing plants, rework loops are often included for the repair and multiple processing of jobs. In the rework loops, defective parts are repaired and sent back to the production line for reprocessing.

Due to machine breakdowns, the number of parts produced by the production system during a fixed time interval is a random variable. Often, it can be characterized by the system production rate, i.e., the number of parts produced by the production system per unit of time. The performance evaluation of production systems with unreliable machines and finite buffers has attracted tremendous attentions (see the reviews by Dallery and Gershwin (1992), Papadopoulos and Heavey (1996) and the monographs by Buzacott and Shanthikumar (1993), Gershwin (1994) and Altiok (1997)). Among these studies, serial production lines have been studied intensively. By extending the results obtained for serial lines, assembly/disassembly lines, parallel-machine lines, etc., have been analyzed (see the representative papers by Gershwin (1987, 1991), Dallery et al. (1989), Mascolo et al. (1991), Jacobs and Meerkov (1995), Kuo et al. (1997), Chiang, Kuo, Lim and Meerkov (2000), Chiang, Kuo and Meerkov (2000) and Patchong and Willaeys (2001)).

In practice, more complex production systems exist and need accurate analysis. For instance, in automotive paint shops, defective parts are repaired in the rework loop and sent back to the painting booth for repainting. Analysis of production systems with rework loops is still an open problem. Although some analytical methods have been developed to approximate the throughput of closed queueing networks with blocking (see the reviews by Onvural (1990) and Suri et al. (1993)), the results on closed loop production systems with unreliable machines and finite buffers are quite limited. Lim and Meerkov (1993), Frein et al. (1996) and Gershwin et al. (2001) have studied closed-loop serial production lines with a constant number of carriers, where parts are loaded and attached on the pallets at the first machine to undergo all the operations. Upon completion of these operations, finished parts are unloaded and the pallets are released and sent back to the first machine. Lim and Meerkov (1993) analyze an asymptotically reliable two-machine two-buffer closed serial line. Expressions for production rate and work-in-process are derived and a case study on a paint shop is described where the optimized choice of the number of carriers and the capacity of the feedback buffer in the system leads to substantial improvement in the system's performance. Frein et al. (1996) present a decomposition approach to approximate the system production rate for homogeneous production lines (i.e., machines that have identical cycle times). The optimal number of carriers is also investigated. Gershwin et al. (2001) extend the study and takes into account the correlation between the number of pallets in the buffers. The algorithm can be applied to both small and large loops. In addition, Yerelan and Tan (1997) develop a flexible decomposition framework and extend it to the analysis of a work cell consisting of one workstation, one rework station and finite buffers fed by a Poisson stream of discrete parts. All these contributions, however, have not directly addressed production systems with rework loops. To the best of our knowledge, there are no analytical methods available in the literature to analyze the performance of production systems with rework loops.

The main contribution of this paper is a convergent recursive procedure, which approximates the production rate of a production system with a rework loop.

The remainder of this paper is structured as follows. Section 2 formulates the problem. The ideas behind the overlapping decomposition method are introduced in Section 3. Section 4 describes an aggregation procedure to calculate the production rate of a serial line. Using it, the recursive procedure to analyze the system with a rework loop is presented in Section 5. The convergence of the procedure and uniqueness of the solution are proved analytically. Section 6 describes a case study at an automotive assembly plant. The conclusions are formulated in Section 7. All proofs are presented in the Appendix.

2. Problem formulation

The production system studied in this paper is shown in Fig. 1. The circles represent the machines and the rectangles are the buffers.

For convenience, the following notations are used throughout this paper:

M = number of machines in the main line, i.e., the line without rework loop;

[M.sub.r] = number of machines in the rework loop;

[alpha] = rework rate, i.e., the probability that a part requires rework (0 [less than or equal to] [alpha] < 1);

[m.sub.i] = i = 1,..., M, machines in the main line, i = r1, r2,..., r [M.sub.r], machines in the rework loop;

[m.sub.k] = split machine;

[m.sub.j] = merge machine;

[FIGURE 1 OMITTED]

[B.sub.i] = i = 1,..., M - 1, buffers in the main line;

i = r1, r2,..., r([M.sub.r] + 1), buffers in the rework loop;

[N.sub.i] = capacity of buffer [B.sub.i], i = 1,..., M - 1, r1,..., r([M.sub.r] + 1).

The system consists of a main production line (machines [m.sub.1],..., [m.sub.M], buffers [B.sub.1],..., [B.sub.M-1]) and a rework loop (machines [m.sub.r1],..., [m.sub.rM.sub.r], buffers [B.sub.r1],..., [B.sub.r([M.sub.r]+1)]). Machines [m.sub.k] and [m.sub.j] are the splitting and merging machines of the rework loop.

The following assumptions pertaining the machines, buffers and their interactions are introduced to model a production system with a rework loop in this paper:

1. Each machine [m.sub.i], i = 1,..., M, r1,..., r[M.sub.r], has two states: up and down. When up, the machine is capable of producing at the rate of one part per unit of time (cycle); when the machine is down, no production takes place.

Remark 1. Assumption 1 on the identical cycle time is introduced to simplify the analysis. However, in many large volume manufacturing systems, lines with automated material handling are well balanced, in this case, this assumption is valid. The system with unequal machine speeds will be addressed in future work.

2. The uptime and the downtime of each machine [m.sub.i], i = 1,..., M, r1,..., r[M.sub.r], are random variables distributed exponentially with parameters [p.sub.i] and [r.sub.i], respectively.

Remark 2. Assumption 2 implies that 1/[p.sub.i] and 1/[r.sub.i] are the average up-and downtime of machine [m.sub.i], respectively. An investigation into the validity of exponential assumptions in production system research is presented in Inman 1999. In future work, systems with nonexponential machines will be studied.

3. Each buffer [B.sub.i], i = 1,..., M - 1, r1,..., r([M.sub.r] + 1), is characterized by its capacity [N.sub.i], 0 [less than or equal to] [N.sub.i] < [infinity].

4. Machine [m.sub.i] is starved at time t if buffer [B.sub.i-1] is empty at time t. Machine [m.sub.1] is never starved. Note that machine [m.sub.j] is starved if both [B.sub.j-1] and [B.sub.r([M.sub.r]+1)] are empty.

5. Machine [m.sub.i] is blocked at time t if [B.sub.i] is full at time t. Machine [m.sub.M] is never blocked. In particular, machine [m.sub.k] is blocked by the main line if it produces a good part and [B.sub.k] is full, while [m.sub.k] is blocked by the rework loop if it produces a defective part and [B.sub.r1] is full.

6. After processing by machine [m.sub.k], a part has a probability [alpha], 0 [less than or equal to] [alpha] < 1, of being defective. A defective part is sent to [B.sub.r1] if it is not full. The good (non-defective) part will be sent to [B.sub.k] if it is not full. The probability [alpha] is referred to as the rework rate.

Remark 3. Assumption 6 does not have any constraint on the number of times that a defective part can be repaired. In other words, a part will continue to circulate in the system until it satisfies the quality requirements. This may not be the case in practice. For instance, in many automotive paint shops, a job usually can be repaired at most three times. However, since the rework rate, [alpha], is usually small, the error introduced by this assumption is negligable. For instance, if [alpha] = 0.2, the probability that a part is still defective after three repairs is 0.0016. In such situations, this assumption works well.

7. Machine [m.sub.j] takes a part from [B.sub.r([M.sub.r]+1)] if it is not empty; otherwise it takes part from [B.sub.j-1] given it is not empty.

Remark 4. Assumption 7 indicates that the rework loop (buffer [B.sub.r([M.sub.r]+1)]) has a higher priority than the main line (buffer [B.sub.j-1]) in releasing parts to machine [m.sub.j]. This assumption is introduced to avoid possible deadlock. Consider the situation when this assumption is relaxed. If machine [m.sub.k] is producing a defective part, and [B.sub.r1] is full, then [m.sub.k] is blocked. If machine [m.sub.j] takes parts from [B.sub.j-1] first and [B.sub.j-1] is always non-empty, then eventually [m.sub.j] will also be blocked and the system will be in deadlock. Therefore, assumption 7 is necessary.

[FIGURE 2 OMITTED]

The problem addressed in this paper is as follows: Given the production system defined by assumptions 1-7 develop a method for evaluating the production rate as a function of the system parameters. A solution to the problem is given in Section 5.

3. The ideas behind the overlapping decomposition approach

Due to the complexity of a system with a rework loop, direct analysis is impossible. Therefore, we introduce approximations. The idea of the approximation used in this paper is referred to as overlapping decomposition, i.e., to decompose the production system of assumptions 1-7 into four serial lines, as illustrated in Fig. 2(a and b). Machines [m.sub.1] through [m.sub.j] and buffers [B.sub.1] through [B.sub.j-1] constitute line 1; [m.sub.j] to [m.sub.k] and [B.sub.j] to [B.sub.k-1] constitute line 2; line 3 consists of [m.sub.k] to [m.sub.M] and [B.sub.k] to [B.sub.M-1]; line 4 is represented by the rework loop, i.e., it consists of machines [m.sub.k], [m.sub.r1] through [m.sub.r[M.sub.r]], [m.sub.j], and buffers [B.sub.r1] through [B.sub.r([M.sub.r]+1)]. Since machines [m.sub.j] and [m.sub.k] are included in multiple serial lines, this decomposition is overlapping.

Consider the serial production lines 1-4 in Fig. 2(b). If we know the production rate of each line, the system production rate is readily obtained (i.e., the production rate of line 3). A convergent recursive procedure for evaluating the production rates of these lines is developed in Section 4. In order to use this procedure, the first and last machines must not be starved or blocked, respectively. Therefore, for each of the serial lines 1 to 4, the parameters of machines [m.sub.k] and [m.sub.j] are modified so as to account for the existence of machines and buffers in other lines. Specifically, for line 4, we introduce fictitious machines, denoted by [m'.sub.k] and [m'.sub.j] (i.e., the first and last machines of line 4) with parameters [p'.sub.k], [r'.sub.k], [p'.sub.j] and [r'.sub.j] defined by:

[r'.sub.k] = [r.sub.k][alpha](1 - prob{[m.sub.k] is starved});

[p'.sub.k] = [p.sub.k] + [r.sub.k][1 - [alpha](1 - prob{[m.sub.k] is starved})];

[r'.sub.j] = [r.sub.j](1 - prob{[m.sub.j] is blocked});

[p'.sub.j] = [p.sub.j] + [r.sub.j]prob{[m.sub.j] is blocked}.

Remark 5. From the point of view of machine [m.sub.r1], [m.sub.k] is "not producing" if it is down, starved or producing a good part. Therefore, this starvation time and time to produce a good part can both be considered as [m'.sub.k]'s downtime, which can be equivalent to 1/[r.sub.k][alpha](1 - pr{[m.sub.k.sub.r] is starved}). Analogously, the blockage time of [m.sub.j] can also be considered as the downtime of [m'.sub.j] from the point of view of machine [m.sub.[rM.sub.r]]. [p'.sub.k] and [p'.sub.j] are selected by following the conservation of flow such that:

[r'.sub.k]/[r'.sub.k] + [p'.sub.k] = [[r.sub.k][alpha]/[p.sub.k] + [r.sub.k]](1 - prob{[m.sub.k] is starved}),

[r'.sub.j]/[r'.sub.j] + [p'.sub.j] = [[r.sub.j]/[p.sub.j] + [r.sub.j]](1 - prob{[m.sub.j] is blocked}).

Similar principles are used for all subsequent modifications of machines [m.sub.k] and [m.sub.j].

If prob{[m.sub.k] is starved} and prob{[m.sub.j] is blocked} are known, using the serial line analysis procedure, the production rate of line 4 can be calculated. Analogously, if we know the probabilities that machine [m.sub.k] is starved by [B.sub.k - 1], by modifying machine [m.sub.k] we can calculate the production rate of line 3. The production rate of line 1 can be calculated similarly if the probabilities that machine [m.sub.j] is starved by [B.sub.r([M.sub.r]+1)] and [m.sub.j] is blocked by [B.sub.j] are known. Finally, the production rate of line 2 depends on the probabilities that machine [m.sub.k] is blocked by [B.sub.k] and [B.sub.r1] and the probabilities that machine [m.sub.j] is starved by [B.sub.r([M.sub.r]+1)] and [B.sub.j - 1], respectively. Then, the production rate of the system (which equals the production rate of line 3) can be obtained. Since these probabilities are unknown, we introduce iterations, as described below.

As the first step, assume that prob{[m.sub.k] is starved} and prob{[m.sub.j] is blocked} are zero and one, respectively. First consider line 4 and modify machines [m.sub.k] and [m.sub.j] to [m'.sub.k] and [m'.sub.j] with parameters defined as above, using the serial line procedure, calculate prob{[m.sub.k] is blocked by [B.sub.r1]} and prob{[m.sub.j] is starved by [B.sub.r([M.sub.r]+1)]}.

Next, consider line 3 and modify machine [m.sub.k] to [m".sub.k] with parameters defined by:

[r".sub.k] = [r.sub.k](1 - [alpha])[1 - prob{[m.sub.k] is starved}],

[p".sub.k] = [p.sub.k] + [r.sub.k][1 - (1 - [alpha])(1 - prob{[m.sub.k] is starved})].

Using the serial line procedure, prob{[m.sub.k] is blocked by [B.sub.k]} is calculated. Similarly, consider line 1, adjust machine [m.sub.j] to [m".sub.j] with parameters:

[r".sub.j] = [r.sub.j]prob{[m.sub.j] is starved by [B.sub.r([M.sub.r]+1)]} X (1 - prob{[m.sub.j] is blocked}),

[p".sub.j] = [p.sub.j] + [r.sub.j][1 - prob{[m.sub.j] is starved by [B.sub.r([M.sub.r]+1)]} X (1 - prob{[m.sub.j] is blocked})].

Again, prob{[m.sub.j] is starved by [B.sub.j - 1]} can be calculated.

Finally, for line 2, introduce the fictitious machines [m"'.sub.j] and [m"'.sub.k], with parameters defined by:

[r"'.sub.j] = [r.sub.j](1 - prob{[m.sub.j] is starved by [B.sub.j-1]} X prob{[m.sub.j] is starved by [B.sub.r([M.sub.r]+1)]}),

[p"'.sub.j] = [p.sub.j] + [r.sub.j]prob{[m.sub.j] is starved by [B.sub.j-1]} X prob{[m.sub.j] is starved by [B.sub.r([M.sub.r]+1)]},

[r"'.sub.k] = [r.sub.k][1 - [alpha]prob{[m.sub.k] is blocked by [B.sub.r1]} - (1 - [alpha])prob{[m.sub.k] is blocked by [B.sub.k]}],

[p"'.sub.k] = [p.sub.k] + [r.sub.k][[alpha]prob{[m.sub.k] is blocked by [B.sub.r1]} + (1 - [alpha])prob{[m.sub.k] is blocked by [B.sub.k]}].

and using the serial line procedure again, prob{[m.sub.k] is starved} and prob{[m.sub.j] is blocked} are obtained. We now use these probabilities for the second iteration in the analysis of line 4 and continue this process, alternating among lines 1 through 4. As is shown in Section 5, the iterations are convergent and result in the estimate of the system production rate.

4. Performance evaluation of serial lines

To adopt the ideas introduced above, an estimation of the production rate of a serial line is needed. In this work, a novel aggregation procedure is used. Compared to the similar approach presented in Chiang, Kuo and Meerkov (2000), this procedure modifies the machine downtime parameters (instead of uptime parameters) to accommodate blockage and starvation information. In addition, the procedure provides the possibility to prove the convergence of the aggregation procedures as well as the uniqueness of the solutions for both serial lines and systems with rework loops. We now outline the procedure.

Consider a serial production line with M machines (Fig. 3) defined by assumptions 1-5 without a rework loop. First, we aggregate the first two machines into a single machine, [m.sub.2.sup.f], with parameters [p.sub.2.sup.f] and [r.sub.2.sup.f]. Next, [m.sub.2.sup.f] is aggregated with [m.sub.3] to result in [m.sub.3.sup.f], and so on until all M machines are aggregated in a single one, [m.sub.M.sup.f]. This constitutes the forward aggregation (the superscript "f" is used to denote this fact). Then, in the backward aggregation, the last machine, [m.sub.M], is aggregated with [m.sub.M - 1.sup.f] to result in [m.sub.M - 1.sup.b] and so on until all machines are again aggregated in a single machine, [m.sub.1.sup.b] (the superscript "b" denotes backward). The procedure is repeated until a convergence criteria is satisfied. Formally, this process is represented as follows:

[FIGURE 3 OMITTED]

Procedure 1.

[r.sub.i.sup.b](s + 1) = [r.sub.i] - [r.sub.i]Q([p.sub.i+1.sup.b](s + 1), [r.sub.i+1.sup.b](s + 1), [p.sub.i.sup.f](s), [r.sub.i.sup.f](s), [N.sub.i]), i = 1,..., M - 1,

[p.sub.i.sup.b](s + 1) = [p.sub.i] + [r.sub.i]Q([p.sub.i+1.sup.b](s + 1), [r.sub.i+1.sup.b](s + 1), [p.sub.i.sup.f](s), [r.sub.i.sup.f](s), [N.sub.i]), i = 1,..., M - 1, (1)

[r.sub.i.sup.f](s + 1) = [r.sub.i] - [r.sub.i]Q([p.sub.i-1.sup.f](s + 1), [r.sub.i-1.sup.f](s + 1), [p.sub.i.sup.b](s + 1), [r.sub.i.sup.b](s + 1), [N.sub.i - 1]), i = 2,..., M,

[p.sub.i.sup.f](s + 1) = [p.sub.i] + [r.sub.i]Q([p.sub.i-1.sup.f](s + 1), [r.sub.i-1.sup.f](s + 1), [p.sub.i.sup.b](s + 1), [r.sub.i.sup.b](s + 1), [N.sub.i - 1]), i = 2,..., M,

with boundary conditions

[p.sub.1.sup.f](s) = [p.sub.1], [r.sub.1.sup.f](s) = [r.sub.1], [p.sub.M.sup.b](s) = [p.sub.M],

[r.sub.M.sup.b](s) = [r.sub.M], s = 0, 1, 2,...,

and initial conditions

[p.sub.i.sup.f](0) = [p.sub.i], [r.sub.i.sup.f](0) = [r.sub.i], i = 2,..., M - 1,

where function Q(*) is defined as follows (Chiang, Kuo and Meerkov, 2000):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[beta] = ([p.sub.1] + [p.sub.2] + [r.sub.1] + [r.sub.2])([p.sub.1][r.sub.2] - [p.sub.2][r.sub.1])/([p.sub.1] + [p.sub.2])([r.sub.1] + [r.sub.2]),

[phi] = [e.sub.1](1 - [e.sub.2])/[e.sub.2](1 - [e.sub.1]),

[e.sub.i] = [r.sub.i]/[p.sub.i] + [r.sub.i], i = 1, 2. (3)

Theorem 1. Recursive procedure 1 is convergent and has a unique solution, therefore, the following limits exist:

[lim.[s[right arrow][infinity]]][p.sub.i.sup.f](s) = [p.sub.i.sup.f], [lim.[s[right arrow][infinity]]][p.sub.i.sup.b](s) = [p.sub.i.sup.b],

[lim.[s[right arrow][infinity]]][r.sub.i.sup.f](s) = [r.sub.i.sup.f], [lim.[s[right arrow][infinity]]][r.sub.i.sup.b](s) = [r.sub.i.sup.b], i = 1, 2,..., M. (4)

Proof. See the Appendix. [black square]

The limits in Equation (4) can be used to approximate the line production rate:

[^.PR]([p.sub.1], [r.sub.1],..., [p.sub.M], [r.sub.M], [N.sub.1],..., [N.sub.M-1]) = [r.sub.M.sup.f]/[p.sub.M.sup.f] + [r.sub.M.sup.f] = [r.sub.1.sup.b]/[p.sub.1.sup.b] + [r.sub.1.sup.b]. (5)

In addition, we also introduce the operators [[PHI].sub.1] and [[PHI].sub.2], which are used to calculate the probabilities that the first machine is blocked and the last machine is starved, respectively. They are defined as follows:

[[PHI].sub.1]([p.sub.1], [r.sub.1],..., [p.sub.M], [r.sub.M], [N.sub.1],..., [N.sub.M-1]) = 1 - [[r.sub.1.sup.b]/[[p.sub.1.sup.b] + [r.sub.1.sup.b]]] X [[[p.sub.1] + [r.sub.1]]/[r.sub.1]],

[[PHI].sub.2]([p.sub.1], [r.sub.1],..., [p.sub.M], [r.sub.M], [N.sub.1],..., [N.sub.M-1]) = 1 - [[r.sub.M.sup.f]/[[p.sub.M.sup.f] + [r.sub.M.sup.f]]] X [[[p.sub.M] + [r.sub.M]]/[r.sub.M]]. (6)

Using procedure 1 and operators [[PHI].sub.1] and [[PHI].sub.2], the recursive procedure for analyzing a system with a rework loop is introduced in the following section.

5. Recursive procedure for lines with a rework loop

5.1. Procedure

For simplification, we introduce the following notation.

[b.sub.j] = prob{machine [m.sub.j] is blocked};

[s.sub.k] = prob{machine [m.sub.k] is starved};

[b.sub.k.sub.1], [b.sub.k.sub.2] = prob{machine [m.sub.k] is blocked by [B.sub.k] and [B.sub.r1], respectively};

[s.sub.j.sub.1], [s.sub.j.sub.2] = prob{machine [m.sub.j] is starved by [B.sub.j-1] and [B.sub.r([M.sub.r]+1)], respectively};

[^.PR.sub.i] = production rate estimation of line i, i = 1, 2, 3, 4.

Formally, using [^.PR](*) defined in Equation (5), and [[PHI].sub.1](*) and [[PHI].sub.2](*) in Equation (6), the recursive procedure is:

Procedure 2.

Line 4

[r'.sub.k](n + 1) = [r.sub.k][alpha][1 - [s.sub.k](n)],

[p'.sub.k](n + 1) = [p.sub.k] + [r.sub.k](1 - [alpha][1 - [s.sub.k](n)]),

[r'.sub.j](n + 1) = [r.sub.j][1 - [b.sub.j](n)],

[p'.sub.j](n + 1) = [p.sub.j] + [r.sub.j][b.sub.j](n), (7)

[^.PR.sub.4](n + 1) = [^.PR]([p'.sub.k](n + 1), [r'.sub.k](n + 1), [p.sub.r1], [r.sub.r1],..., [p.sub.r[M.sub.r]], [r.sub.r[M.sub.r]], [p'.sub.j](n + 1), [r'.sub.j](n + 1), [N.sub.r1],..., [N.sub.r([M.sub.r] + 1)]),

[b.sub.k.sub.2](n + 1) = [[PHI].sub.1]([p'.sub.k](n + 1), [r'.sub.k](n + 1), [p.sub.r1], [r.sub.r1],..., [p.sub.r[M.sub.r]], [r.sub.r[M.sub.r]], [p'.sub.j](n + 1), [r'.sub.j](n + 1), [N.sub.r1],..., [N.sub.r([M.sub.r] + 1)]),

[s.sub.j.sub.2](n + 1) = [[PHI].sub.2]([p'.sub.k](n + 1), [r'.sub.k](n + 1), [p.sub.r1], [r.sub.r1],..., [p.sub.r[M.sub.r]], [r.sub.r[M.sub.r]], [p'.sub.j](n + 1), [r'.sub.j](n + 1), [N.sub.r1],..., [N.sub.r([M.sub.r] + 1)]).

Line 3

[r".sub.k](n + 1) = [r.sub.k][1 - [s.sub.k](n)](1 - [alpha]),

[p".sub.k](n + 1) = [p.sub.k] + [r.sub.k](1 - (1 - [alpha])[1 - [s.sub.k](n)]), (8)

[^.PR.sub.3](n + 1) = [^.PR]([p".sub.k](n + 1), [r".sub.k](n + 1), [p.sub.k+1], [r.sub.k+1],..., [p.sub.M], [r.sub.M], [N.sub.k],..., [N.sub.M-1]),

[b.sub.[k.sub.1]](n + 1) = [[PHI].sub.1]([p".sub.k](n + 1), [r".sub.k](n + 1), [p.sub.k+1], [r.sub.k+1],..., [p.sub.M], [r.sub.M], [N.sub.k],..., [N.sub.M-1]),

Line 1

[r".sub.j](n + 1) = [r.sub.j][s.sub.[j.sub.2]](n + 1)[1 - [b.sub.j](n)],

[p".sub.j](n + 1) = [p.sub.j] + [r.sub.j](1 - [s.sub.[j.sub.2]](n + 1)[1 - [b.sub.j](n)]). (9)

[^.PR.sub.1](n + 1) = [^.PR]([p.sub.1], [r.sub.1],..., [p.sub.j-1], [r.sub.j-1], [p".sub.j](n + 1), [r".sub.j](n + 1), [N.sub.1],..., [N.sub.j-1],

[s.sub.[j.sub.1]](n + 1) = [[PHI].sub.2]([p.sub.1], [r.sub.1],..., [p.sub.j-1], [r.sub.j-1], [p".sub.j](n + 1), [r".sub.j](n + 1), [N.sub.1],..., [N.sub.j-1].

Line 2

[r.sub.j.sup.m](n + 1) = [r.sub.j][1 - [s.sub.[j.sub.1]](n + 1)[s.sub.[j.sub.2]](n + 1)],

[p.sub.j.sup.m](n + 1) = [p.sub.j] + [r.sub.j][s.sub.[j.sub.1]](n + 1)[s.sub.[j.sub.2]](n + 1),

[r.sub.k.sup.m](n + 1) = [r.sub.k][1 - [alpha][b.sub.[k.sub.2]](n + 1) - (1 - [alpha])[b.sub.[k.sub.1]](n + 1)],

[p.sub.k.sup.m](n + 1) = [p.sub.k] + [r.sub.k][[alpha][b.sub.[k.sub.2]](n + 1) + (1 - [alpha])[b.sub.[k.sub.1]](n + 1)], (10)

[^.PR.sub.2](n + 1) = [^.PR]([p.sub.j.sup.m](n + 1), [r.sub.j.sup.m](n + 1), [p.sub.j+1], [r.sub.j+1],..., [p.sub.k-1], [r.sub.k-1], [p.sub.k.sup.m](n + 1), [r.sub.k.sup.m](n + 1), [N.sub.j],..., [N.sub.k-1]),

[b.sub.j](n + 1) = [[PHI].sub.1][^.PR]([p.sub.j.sup.m](n + 1), [r.sub.j.sup.m](n + 1), [p.sub.j+1], [r.sub.j+1],..., [p.sub.k-1], [r.sub.k-1], [p.sub.k.sup.m](n + 1), [r.sub.k.sup.m](n + 1), [N.sub.j],..., [N.sub.k-1][^.PR]),

[s.sub.k](n + 1) = [[PHI].sub.2][^.PR]([p.sub.j.sup.m](n + 1), [r.sub.j.sup.m](n + 1), [p.sub.j+1], [r.sub.j+1],..., [p.sub.k-1], [r.sub.k-1], [p.sub.k.sup.m](n + 1), [r.sub.k.sup.m](n + 1), [N.sub.j],..., [N.sub.k-1][^.PR]), n = 0, 1, 2,...,

with initial conditions

[s.sub.k](0) = 0, [b.sub.j](0) = 1.

Remark 6. The initial values of [s.sub.k] and [b.sub.j] are used to prove the convergence only. The convergence takes place for any [s.sub.k] and [b.sub.j] between zero and one.

5.2. Convergence

The questions of convergence and uniqueness of the solution are answered below:

Theorem 2. Under assumptions 1-7, recursive procedure 2 is convergent, i.e.,

[lim. (n[right arrow][infinity])][^.PR.sub.i](n) = [^.PR.sub.i], i = 1, 2, 3, 4, [lim. (n[right arrow][infinity])][b.sub.j](n) = [b.sub.j], [lim. (n[right arrow][infinity])][s.sub.k](n) = [s.sub.k], (11)

[lim. (n[right arrow][infinity])][b.sub.[k.sub.i]](n) = [b.sub.[k.sub.i]], [lim. (n[right arrow][infinity])][s.sub.[j.sub.i]](n) = [s.sub.[j.sub.i]], i = 1, 2.

Proof. See the Appendix. [black square]

By the conservation of flow, the following relationships hold:

Corollary 1. Under assumptions 1-7:

[^.PR.sub.1] = [^.PR.sub.3],

[^.PR.sub.2] = [^.PR.sub.1] + [^.PR.sub.4]. (12)

Moreover,

Corollary 2. The steady-state equations of recursive procedure 2 have a unique solution.

Proof. See the Appendix. [black square]

Using the limits in Equation (11), the system production rate can be evaluated as:

[^.PR] = [^.PR.sub.3] = PR([p".sub.k], [r".sub.k], [p.sub.k+1], [r.sub.k+1],..., [p.sub.M], [r.sub.M], [N.sub.k],..., [N.sub.M-1]). (13)

Remark 7. The convergence of procedure 2 is independent of the order, in which lines 1-4 are analyzed. Moreover, other serial line analysis methods can also be applied (to replace procedure 1). However, the convergence of the algorithm depends on the convergence of the serial line analysis method.

5.3. Accuracy

The accuracy of the estimate defined by Equation (13) is investigated numerically. Over 60 systems defined by assumptions 1-7 with various machine and buffer parameter settings (based on operational, randomly and specifically selected data) are simulated. In each simulation run, a zero initial occupancy of all buffers has been assumed, and a 5000 time slot warm up period has been carried out. The next 50 000 slots of the stationary regime have been used to statistically evaluate the production rate. The 95% confidence intervals have been calculated with 20 runs and are consistently around [+ or -]0.001, while the maximum was [+ or -]0.0017. Most examples result in an accuracy within 4%. Fifteen of these examples are shown in Table 1, where PR denotes the actual production rate obtained by simulation, [^.PR] denotes the estimate of the production rate calculated according to Equation (13). As shown in Table 1, the estimates of the production rate have a relatively high precision.

Remark 8. From Table 1 and based on our experiences, the accuracy of Equation (13) is not sensitive to most parameter settings (for instance, machine efficiency, buffer capacity, rework rate, etc.). Only when [p.sub.i] is large, does the accuracy drop over 3%, however, in most practical cases, it is acceptable.

6. Case study

Recursive procedure 2 has been applied to several automotive assembly plants to analyze system performance and to provide guidance for continuous improvement processes. Experimental results show that the method works well in estimating the system production rate using actual operational data (with errors less than 3% among all the studies). We now introduce a case study (see Fig. 4). Due to confidentiality, the system layout and parameters have been modified appropriately, they are used for illustration only.

In this model, the rework loop begins at Op. 12 and rejoins the line at Op. 8. The identified machine and buffer parameters are summarized in Table 2. All machines have an identical processing rate of one part per unit of time. The rework rate is [alpha] = 0.12.

[FIGURE 4 OMITTED]

Using procedure 2, we evaluate the performance of a production system with a rework loop. The estimated production rate is 0.717 parts per unit of time. Compared to actual production rate, the difference is 1.6%. Therefore, the model has an acceptable accuracy and can be used to guide the continuous improvement process.

7. Conclusions

Modeling and analysis of production systems with rework loops are important for the design and continuous improvement of such systems. This paper presents an aggregation procedure using an overlapping decomposition method to calculate the production rate of systems with rework loops. The convergence of the procedure and the uniqueness of the solution are proved analytically and the accuracy is justified by numerical examples. In addition, this method has been applied to automotive assembly plants to evaluate the system performance and provide recommendations for continuous improvements.

Future work will be directed to inhomogeneous production lines systems with multiple rework loops. Nonexponential machine reliability, continuous improvement and optimization of system performance (through bottleneck identification and buffer reallocation, etc.) will also be addressed.

Appendix

Proofs of Theorems 1 and 2 and corollary 2. Due to space limitation, we only proivde sketches of the proofs. The complete proofs can be found in Li (2001).

The idea to prove the convergence part of Theorem 1 is similar to that of Theorem 3.1 in Chiang, Kuo and Meerkov (2000). To prove Theorem 1, Lemmas A1-A5 are needed. The proof of Lemma A1 can be found in Chiang, Kuo and Meerkov (2000).

Lemma A1. Function Q([p.sub.1], [r.sub.1], [p.sub.2], [r.sub.2], N) is monotonically increasing with respect to [p.sub.1] and [r.sub.2], and monotonically decreasing with respect to [r.sub.1], [p.sub.2] and N, and, it takes values in (0, 1).

Lemma A2. Consider [p.sub.i.sup.f](s), [r.sub.i.sup.f](s), [p.sub.i.sup.b](s) and [r.sub.i.sup.b](s), i = 1,..., M, defined by recursive procedure 1. If for all j = 2,..., M, [r.sub.j.sup.f](s) < [r.sub.j.sup.f](s - 1) and [p.sub.j.sup.f](s) > [p.sub.j.sup.f](s - 1), then for all j = 1,..., M - 1, [r.sub.j.sup.b](s) > [r.sub.j.sup.b](s - 1) and [p.sub.j.sup.b](s) < [p.sub.j.sup.b](s - 1).

Proof. By induction.

Step 1. Under the above assumption, for j = M - 1, from Lemma A1 and recursive procedure 1, we can show that:

[r.sub.M-1.sup.b](s + 1) > [r.sub.M-1.sup.b](s), [p.sub.M-1.sup.b](s + 1) < [p.sub.M-1.sup.b](s).

Step 2. For j = M - 2, M - 3,...,2, 1, using Lemma A1 and similar arguments, we obtain:

[r.sub.j.sup.b](s + 1) > [r.sub.j.sup.b](s), [p.sub.j.sup.b](s + 1) < [p.sub.j.sup.b](s), j = M - 2, M - 3,..., 1. [black square]

Lemma A3. If for all j = 1,..., M - 1, [r.sub.j.sup.b](s + 1) > [r.sub.j.sup.b](s) and [p.sub.j.sup.b](s + 1) < [p.sub.j.sup.b](s), then for all j = 2,..., M, [r.sub.j.sup.f](s + 1) < [r.sub.j.sup.f](s) and [p.sub.j.sup.f](s + 1) > [p.sub.j.sup.f](s).

Proof. Similar to that of Lemma A2. [black square]

Lemma A4. Sequences [p.sub.j.sup.f](s) and [p.sub.j.sup.b](s) are monotonically increasing and sequences [r.sub.j.sup.f](s) and [r.sub.j.sup.b](s) are monotonically decreasing.

Proof. By induction.

Step 1. For s = 0, from Lemma A1, we have:

[r.sub.j.sup.f](1) < [r.sub.j] = [r.sub.j.sup.f](0), [p.sub.j.sup.f](1) > [p.sub.j] = [p.sub.j.sup.f](0), 2 [less than or equal to] j [less than or equal to] M.

Step 2. Assume that s > 0:

[p.sub.j.sup.f](s) > [p.sub.j.sup.f](s - 1), [r.sub.j.sup.f](s) < [r.sub.j.sup.f](s - 1), 2 [less than or equal to] j [less than or equal to] M.

Step 3. By Lemmas A2 and A3, we obtain:

[p.sub.j.sup.b](s + 1) < [p.sub.j.sup.b](s), [r.sub.j.sup.b](s + 1) > [r.sub.j.sup.b](s), 1 [less than or equal to] j [less than or equal to] M - 1, [p.sub.j.sup.f](s + 1) > [p.sub.j.sup.f](s), [r.sub.j.sup.f](s + 1) < [r.sub.j.sup.f](s), 2 [less than or equal to] j [less than or equal to] M. [black square]

Introduce (M - 1) two-machine one-buffer production lines [L.sub.i], i = 1,..., M - 1, where the first machine has uptime parameter [p.sub.i.sup.f] and downtime parameter [r.sub.i.sup.f], the second [p.sub.i+1.sup.b] and [r.sub.i+1.sup.b], and the buffer capacity is [N.sub.i]. Define:

[e.sub.i.sup.f] = [r.sub.i.sup.f]/[[r.sub.i.sup.f] + [p.sub.i.sup.f]], [e.sub.i.sup.b] = [r.sub.i.sup.b]/[[r.sub.i.sup.b] + [p.sub.i.sup.b]], i = 1,..., M.

Lemma A5. Let P[R.sub.i] be the production rate of line [L.sub.i], i = 1,..., M - 1, and let P[R.sub.M] = [e.sub.M.sup.f]. Then the following properties hold:

P[R.sub.i] = [[e.sub.i.sup.f][e.sub.i.sup.f]]/[e.sub.i], i = 1,..., M, P[R.sub.i] = P[R.sub.j], [for all]i [not equal to] j. (A1)

Proof.

Step 1. From the steady-state equations of recursive procedure 1, we obtain:

[e.sub.i.sup.b] = [e.sub.i][1 - Q([p.sub.i+1.sup.b], [r.sub.i+1.sup.b], [p.sub.i.sup.f], [r.sub.i.sup.f], [N.sub.i])], 1 [less than or equal to] i [less than or equal to] M - 1, [e.sub.i.sup.f] = [e.sub.i][1 - Q([p.sub.i-1.sup.f], [r.sub.i-1.sup.f], [p.sub.i.sup.b], [r.sub.i.sup.b], [N.sub.i-1])], 2 [less than or equal to] i [less than or equal to] M,

[e.sub.1.sup.f] = [e.sub.1], [e.sub.M.sup.b] = [e.sub.M]. (A2)

where the function Q(*) is defined in Equation (2)

Step 2. Using Equation (A2), we can show that:

P[R.sub.i] = [e.sub.i.sup.f][1 - Q([p.sub.i+1.sup.b], [r.sub.i+1.sup.b], [p.sub.i.sup.f], [r.sub.i.sup.f], [N.sub.i])] X [e.sub.i]/[e.sub.i], = [[e.sub.i.sup.f][e.sub.i.sup.b]]/[e.sub.i], 1 [less than or equal to] i [less than or equal to] M - 1. (A3)

P[R.sub.M] = [e.sub.M.sup.f] = [[e.sub.M.sup.f][e.sub.M]]/[e.sub.M] = [[e.sub.M.sup.f][e.sub.M.sup.b]]/[e.sub.M].

Step 3. From Equation (A2):

P[R.sub.i] = [[e.sub.i.sup.f][e.sub.i.sup.b]]/[e.sub.i] = [[e.sub.i.sup.b]/[e.sub.i]][e.sub.i][1 - Q([p.sub.i-1.sup.f], [r.sub.i-1.sup.f], [p.sub.i.sup.b], [r.sub.i.sup.b], [N.sub.i-1])] = [e.sub.i.sup.b][1 - Q([p.sub.i-1.sup.f], [r.sub.i-1.sup.f], [p.sub.i.sup.b], [r.sub.i.sup.b], [N.sub.i-1])], = P[R.sub.i-1], i = 2,..., M. (A4)

[black square]

Proof of Theorem 1. Since the sequences [p.sub.i.sup.f](s), [r.sub.i.sup.f](s), [p.sub.i.sup.b](s) and [r.sub.i.sup.b](s), i [less than or equal to] j [less than or equal to] M, are monotonic (Lemma A4) and bounded from above and below (Lemma A1), they are convergent. This proves the convergence.

To prove the uniqueness, consider the steady-state equations of recursive procedure 1. Assume that along with the solution [S.sub.agg] = [[p.sub.1.sup.f], [r.sub.1.sup.f],..., [p.sub.M.sup.f], [r.sub.M.sup.f], [p.sub.1.sup.b], [r.sub.1.sup.b],..., [p.sub.M.sup.b], [r.sub.M.sup.b]][.sup.T], there exists another solution denoted by [bar.S.sub.agg] = [[bar.P.sub.1.sup.f], [bar.r.sub.1.sup.f],..., [bar.p.sub.M.sup.f], [bar.r.sub.M.sup.f], [bar.p.sub.1.sup.b], [bar.r.sub.1.sup.b],..., [bar.p.sub.M.sup.b], [bar.r.sub.M.sup.b]][.sup.T].

Step 1. Suppose that [bar.p.sub.1.sup.b] > [p.sub.1.sup.b].

1.1. We obtain [r.sub.1.sup.b] > [bar.r.sub.1.sup.b]. From Lemma A5:

P[R.sub.j] > [bar.PR.sub.j], j = 1,..., M. (A5)

1.2. The following property can be proved by contradiction:

[p.sub.2.sup.b] < [bar.p.sub.2.sup.b], [r.sub.2.sup.b] > [bar.r.sub.2.sup.b].

1.3. The following relationships are obtained:

[p.sub.2.sup.f] > [bar.p.sub.2.sup.f], [r.sub.2.sup.f] < [bar.r.sub.2.sup.f].

1.4. Now proceed inductively. Assume [p.sub.j.sup.f] > [bar.p.sub.j.sup.f]. The base case (j = 2) has already been established. By Equation (A5), we must have:

[p.sub.j.sup.b] < [bar.p.sub.j.sup.b], [r.sub.j.sup.b] > [bar.r.sub.j.sup.b],

It can be shown that the following relationship holds:

[p.sub.j+1.sup.f] > [bar.p.sub.j+1.sup.f].

Thus, the inductive hypothesis is established, and [p.sub.j.sup.f] > [bar.p.sub.j.sup.f], 2 [less than or equal to] i [less than or equal to] M. In particular, [p.sub.M.sup.f] > [bar.p.sub.M.sup.f].

1.5. It implies that P[R.sub.M] < [bar.PR.sub.M], which contradicts Equation (A5). We therefore conclude that [p.sub.1.sup.b] [greater than or equal to] [bar.p.sub.1.sup.b].

Step 2. Assuming that [p.sub.1.sup.b] > [bar.p.sub.1.sup.b], and proceeding analogously, yields [p.sub.1.sup.b] [less than or equal to] [bar.p.sub.1.sup.b]. Therefore, [p.sub.1.sup.b] = [bar.p.sub.1.sup.b].

Step 3. The equality of the remaining components of [S.sub.agg] = [bar.S.sub.agg] will be shown by induction.

3.1. Note that [p.sub.1.sup.f] = [p.sub.1] = [bar.p.sub.1.sup.f], [r.sub.1.sup.f] = [r.sub.1] = [bar.r.sub.1.sup.f], and that [p.sub.1.sup.b] = [bar.p.sub.1.sup.b] and [r.sub.1.sup.b] = [bar.r.sub.1.sup.b].

3.2. Assume that [p.sub.j.sup.b] = [bar.p.sub.j.sup.b], [p.sub.j.sup.f] = [bar.p.sub.j.sup.[bar.f]], which implies [r.sub.j.sup.b] = [bar.r.sub.j.sup.b] and [r.sub.j.sup.f] = [bar.r.sub.j.sup.f]. We can obtain that:

[p.sub.j+1.sup.f] = [bar.p.sub.j+1.sup.f], [r.sub.j+1.sup.f] = [bar.r.sub.j+1.sup.f].

The inductive hypothesis is established. There is a unique solution. [black square]

To prove Theorem 2, Lemmas A6-A8 are needed.

Lemma A6. Operator [[PHI].sub.1] ([p.sub.1], [r.sub.1], S,..., [p.sub.M], [r.sub.M], S, [N.sub.1],..., [N.sub.M-1]) is monotonically decreasing with respect to [p.sub.1] and increasing with respect to [r.sub.1].

Proof. Assume there exists another serial line denoted by {[bar.p.sub.1], [r.sub.1], [p.sub.2], [r.sub.2],..., [p.sub.M], [r.sub.M], [N.sub.1],..., [N.sub.M-1]}, with production rate [bar.PR], and aggregation parameters [bar.p.sub.i.sup.f], [bar.p.sub.i.sup.b] and [bar.r.sub.i.sup.f], [bar.r.sub.i.sup.b], i = 1,..., M.

Step 1. Assume [p.sub.1] < [bar.p.sub.1]. Then the following property can be proved by contradiction:

[bar.p.sub.M-1.sup.f] > [p.sub.M-1.sup.f], [bar.r.sub.M-1.sup.f] < [r.sub.M-1.sup.f]. (A6)

Step 2. From Lemma A1, it can be shown that:

[bar.r.sub.M-1.sup.b] > [r.sub.M-1.sup.b], [bar.p.sub.M-1.sup.b] < [p.sub.M-1.sup.b]

Step 3. Repeatly performing the similar analysis, finally we have:

[bar.r.sub.2.sup.b] > [r.sub.2.sup.b], [bar.p.sub.2.sup.b] < [p.sub.2.sup.b].

Step 4. It implies that:

[[PHI].sub.1]([bar.p.sub.1], [r.sub.1], S,..., [p.sub.M], [r.sub.M], S, [N.sub.1],..., [N.sub.M-1]) < [[PHI].sub.1]([p.sub.1], [r.sub.1], S,..., [p.sub.M], [r.sub.M], S, [N.sub.1],..., [N.sub.M-1]).

Step 5. Similarly, we can show that operator [[PHI].sub.1]([p.sub.1], [r.sub.1], S,..., [p.sub.M], [r.sub.M], S, [N.sub.1],..., [N.sub.M-1]) is monotonically increasing with respect to [r.sub.1]. [black square]

Lemma A7. Operator [[PHI].sub.2]([p.sub.1], [r.sub.1], S,..., [p.sub.M], [r.sub.M], S, [N.sub.1],..., [N.sub.M-1]) is monotonically decreasing with respect to [p.sub.M], and increasing with respect to [r.sub.M].

Proof. By reversibility, Lemma A7 is proved. [black square]

Lemma A8. In recursive procedure 2 if [s.sub.k](n) > [s.sub.k](n - 1) and [b.sub.j](n) < [b.sub.j](n - 1), then [s.sub.k](n + 1) > [s.sub.k](n) and [b.sub.j](n + 1) < [b.sub.j](n).

Proof.

Step 1. If [s.sub.k](n) > [s.sub.k](n - 1) and [b.sub.j](n) < [b.sub.j](n - 1), from Equation (7) and Lemmas A6 and A7 we obtain:

[b.sub.k.sub.2](n + 1) < [b.sub.k.sub.2](n), [s.sub.j.sub.2](n + 1) > [s.sub.j.sub.2](n). (A7)

Step 2. From Equations (8) and Lemma A6, we have:

[b.sub.k.sub.1](n + 1) < [b.sub.k.sub.1](n). (A8)

Step 3. From Equations (9), (A7) and Lemma A7, it leads to:

[s.sub.j.sub.1](n + 1) < [s.sub.j.sub.1](n). (A9)

Step 4. From Equations (10), (A7)-(A9) and Lemmas A6 and A7, it follows that:

[b.sub.j](n + 1) < [b.sub.j](n), [s.sub.k](n + 1) > [s.sub.k](n). [black square]

Proof of Theorem 2. By induction.

Step 1. For n = 0, [s.sub.k](0) = 0 and [b.sub.j](0) = 1. For lines 4, 3, 1 and 2, from (7)-(10), we obtain:

[b.sub.k.sub.2](1) = 1, [s.sub.j.sub.2](1) = 0,

0 < [b.sub.k.sub.1](1) < 1, [s.sub.j.sub.1](1) = 0,

0 < [b.sub.j](1) < 1, 0 < [s.sub.k](1) < 1.

Therefore, the base case, [s.sub.k](1) > [s.sub.k](0) and [b.sub.j](1) < [b.sub.j](0), is obtained.

Step 2. Assume now n > 0, [s.sub.k](n) > [s.sub.k](n - 1) and [b.sub.j](n) < [b.sub.j](n - 1). From Lemma A8 we have:

[s.sub.k](n + 1) > [s.sub.k](n), [b.sub.j](n + 1) < [b.sub.j](n).

Step 3. Therefore, [s.sub.k](n) and [b.sub.j](n) are monotonically increasing or decreasing, respectively. Since they are bounded by zero and one, they are convergent. [black square]

Proof of Corollary 2. By contradiction. Let [S.sub.agg] = [[s.sub.k], [s.sub.j.sub.1], [s.sub.j.sub.2], [b.sub.k.sub.1], [b.sub.k.sub.2], [b.sub.j]][.sup.T] be the convergent solution to the steadystate equations of recursive procedure 2. Assume that along with this solution, there exists another solution denoted by [bar.S.sub.agg] = [[bar.s.sub.k], [bar.s.sub.j.sub.1], [bar.s.sub.j.sub.2], [bar.b.sub.k.sub.1], [bar.b.sub.k.sub.2], [bar.b.sub.j]][.sup.T].

Step 1. Suppose that [s.sub.k] > [bar.s.sub.k].

1.1. From corollary 1 we can obtain:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[b.sub.k.sub.1] < [bar.b.sub.k.sub.1], [s.sub.j.sub.1] < [bar.s.sub.j.sub.1], [s.sub.j.sub.2](1 - [b.sub.j]) < [bar.s.sub.j.sub.2](1 - [bar.b.sub.j]).

1.2. By contradiction, we can prove that [r'.sub.k] < [bar.r'.sub.k] and [r'.sub.j] < [bar.r'.sub.j]. This leads to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

1.3. From Corollary 1 we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. There exists four possible combinations of relationship between [r"'.sub.k] and [bar.r"'.sub.k], [r"'.sub.j] and [bar.r"'.sub.j], respectively.

Case 1 [r"'.sub.k] [greater than or equal to] [bar.r"'.sub.k], [r"'.sub.j] [greater than or equal to] [bar.r"'.sub.j]. It follows that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which is a contradiction.

Case 2 [r"'.sub.k] [greater than or equal to] [bar.r"'.sub.k], [r"'.sub.j] < [bar.r"'.sub.j]. It implies that [b.sub.j] [greater than or equal to] [bar.b.sub.j], which is a contradiction.

Case 3 [r"'.sub.k] < [bar.r"'.sub.k], [r"'.sub.j] [greater than or equal to] [bar.r"'.sub.j]. It leads to [s.sub.k] < [bar.s.sub.k], which again is a contradiction.

Case 4 [r"'.sub.k] < [bar.r"'.sub.k], [r"'.sub.j] < [bar.r"'.sub.j]. After some manipulations, we can show that again this is a contradiction.

Therefore, we conclude that [s.sub.k] [less than or equal to] [bar.s.sub.k].

Step 2. Assuming that [s.sub.k] < [bar.s.sub.k], and proceeding analogously, yields [s.sub.k] [greater than or equal to] [bar.s.sub.k].

Step 3. Therefore, [s.sub.k] = [bar.s.sub.k].

3.1 From corollary 1, we can show that:

[b.sub.k.sub.1] = [bar.b.sub.k.sub.1], [s.sub.j.sub.1] = [bar.s.sub.j.sub.1].

3.2 By contradiction, we show that [b.sub.j] = [bar.b.sub.j].

3.3 It follows that:

[b.sub.k.sub.2] = [bar.b.sub.k.sub.2], [s.sub.j.sub.2] = [bar.s.sub.j.sub.2].

Hence, [S.sub.agg] = [bar.S.sub.agg]. There is a unique solution. [black square]

Table 1. Accuracy of production rate estimation in production system
with rework loop (err% = (|PR - [^.PR]|/PR) X 100%)

                         Main line                      Rework line
Example  [p.sub.i]       [r.sub.i]       [N.sub.i]  [p.sub.i]  [r.sub.i]

 1       0.09 0.12       0.6 0.67        3 4
         0.06 0.05       0.77 0.78       3 3        0.07       0.7
         0.11 0.1        0.65 0.63       2
 2       0.1 0.1         0.7 0.7         1 1        0.08       0.73
         0.05 0.05       0.75 0.75       1 1        0.07       0.72
         0.1 0.1         0.7 0.7         3
 3       0.06 0.07       0.75 0.74       2 3
         0.03 0.02       0.88 0.86       3 4        0.04       0.85
         0.08 0.06       0.81 0.8        2
 4       0.2 0.15        0.9 0.8         3 4        0.1        0.7
         0.1 0.05 0.1    0.7 0.6 0.7     5 5        0.15       0.8
         0.15 0.2        0.8 0.9         4 3        0.1        0.7
 5       0.1 0.12        0.7 0.8         3 2        0.1        0.7
         0.15 0.11       0.75 0.9        3 4        0.12       0.78
         0.09 0.14       0.72 0.8        3
 6       0.1 0.12        0.7 0.8         1 1        0.1        0.7
         0.15 0.11       0.75 0.9        1 1        0.12       0.78
         0.09 0.14       0.72 0.8        1
 7       0.01 0.01       0.1 0.1         4 4        0.01       0.1
         0.01 0.01       0.1 0.1         4 4        0.01       0.1
         0.01 0.01       0.1 0.1         4
 8       0.1 0.1 0.1     0.8 0.8 0.8     3 3        0.1        0.8
         0.1 0.1         0.8 0.8         3 3        0.1        0.8
         0.1 0.1         0.8 0.8         3 3
 9       0.01 0.01 0.02  0.6 0.6 0.55    3 3
         0.03 0.02       0.6 0.55        2 2        0.02       0.6
         0.01 0.01       0.6 0.6         3 3
10       0.1 0.15 0.12   0.22 0.3 0.26   2 3        0.22       0.28
         0.08 0.11       0.25 0.25       4 3        0.1        0.32
         0.05 0.16       0.28 0.35       2 3
11       0.2 0.22 0.25   0.83 0.86 0.85  2 2 3      0.14       0.87
         0.1 0.15 0.17   0.94 0.93 0.95  2 2        0.18       0.95
         0.23 0.24       0.86 0.84       3 3        0.2        0.9
12       0.25 0.35 0.3   0.86 0.85 0.87  3 2 3      0.28       0.93
         0.1 0.17 0.14   0.93 0.96 0.92  4 3        0.3        0.89
         0.26 0.23       0.84 0.83       3 2
13       0.1 0.12 0.08   0.6 0.67 0.68   3 4 3      0.11       0.75
         0.1 0.11 0.09   0.79 0.73 0.72  2 4        0.1        0.7
         0.12 0.13       0.71 0.69       3 3
14       0.08 0.09 0.06  0.71 0.72 0.73  3 4 2      0.06       0.76
         0.07 0.05 0.04  0.74 0.76 0.77  3 4 3      0.07       0.77
         0.07 0.06 0.08  0.75 0.78 0.72  2 4        0.06       0.79
15       0.05 0.15 0.2   0.6 0.75 0.8    3 2 3      0.1        0.8
         0.25 0.2 0.1    0.79 0.68 0.65  4 3        0.2        0.75
         0.3 0.18        0.9 0.85        3 5        0.3        0.9
         0.12 0.08       0.77 0.89       4 3        0.1        0.85

         Rework line
Example  [N.sub.i]    j  k  [alpha]  PR      [^.PR]  err %

1        3
         3            3  4  0.25     0.6430  0.6415  0.23
2        1
         1            3  4  0.35     0.5140  0.5057  1.61
         1
3        3
         3            3  4  0.18     0.7723  0.7650  0.95
4        3 4
         4            3  5  0.8      0.1760  0.1695  3.69
         3
5        3
         2            2  4  0.75     0.1961  0.1946  0.76
         3
6        1
         1            2  4  0.25     0.4929  0.4977  0.97
         1
7        4
         4            3  5  0.1      0.6116  0.6196  1.31
         4
8        3
         3            3  5  0.26     0.5998  0.6001  0.05
         3
9        3
         3            3  5  0.32     0.6264  0.6230  0.54
10       2
         3            2  5  0.25     0.2718  0.2744  0.96
         2
11       4 3
         3            4  7  0.15     0.5760  0.5950  3.30
         2
12       4
         3            4  6  0.21     0.5660  0.5760  1.77
         2
13       3
         3            3  6  0.22     0.5901  0.6012  1.88
         3
14       4 3
         3            4  6  0.14     0.7363  0.7399  0.49
         4
15       2 4
         4            3  5  0.65     0.2259  0.2283  1.06
         2
         3

Table 2. System parameters

           Op.1   Op.2    Op.3    Op.4    Op.5    Op.6    Op.7    Op.8

[p.sub.i]  0.206   0.047   0.025   0.081   0.002   0.001   0.110   0.050
[r.sub.i]  0.941   0.264   0.185   0.374   0.050   0.020   0.558   0.324
[N.sub.i]  8      13      10      21      10      20      55      16

           Op.9    Op.10   Op.11    Op.12   Op.13   Op.14

[p.sub.i]   0.106   0.027    0.002   0.016   0.025   0.045
[r.sub.i]   0.653   0.213    0.050   0.168   0.410   0.315
[N.sub.i]  20      12      140      75              34, 65

Acknowledgements

The author thanks Professor Semyon M. Meerkov of the University of Michigan, Dr. Jeffrey M. Alden and Dr. Dennis E. Blumenfeld from the General Motors Research & Development Center and the anonymous reviewers for their valuable comments and suggestions.

Received December 2001 and accepted February 2004

References

Altiok, T. (1997) Performance Analysis of Manufacturing Systems, Springer, New York.

Buzacott, J.A. and Shanthikumar, J.G. (1993) Stochastic Models of Manufacturing Systems, Prentice Hall, Englewood Cliffs, NJ.

Chiang, S.-Y., Kuo, C.-T., Lim, J.-T. and Meerkov, S.M. (2000) Improvability of assembly systems I: problem for mulation and performance evaluation. Mathematical Problems in Engineering, 6, 359-393.

Chiang, S.-Y., Kuo, C.-T. and Meerkov, S.M. (2000) DT-bottlenecks in serial production line: theory and application. IEEE Transactions on Robotics and Automation, 16, 567-580.

Dallery, Y., David, R. and Xie, X.-L. (1989) Approximate analysis of transfer lines with unreliable machines and finite buffers. IEEE Transactions on Automatic Control, 34, 943-953.

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

Frein, Y., Commault, C. and Dallery, Y. (1996) Modeling and analysis of closed-loop production lines with unreliable machines and finite buffers. IIE Transactions, 28, 545-554.

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

Gershwin, S.B. (1991) Assembly/disassembly systems: an efficient decomposition algorithm for tree-structured networks. IIE Transactions, 23, 302-314.

Gershwin, S.B. (1994) Manufacturing Systems Engineering, Prentice Hall, Englewood Cliffs, NJ.

Gershwin, S.B., Maggio, N., Matta, A., Tolio, T. and Werner, L.M. (2001) Analysis of loop networks by decomposition, in Procedings of the 3rd Aegean International Conference on Design and Analysis of Manufacturing Systems, Tinos Island, Greece, pp. 239-248.

Inman, R.R. (1999) Empirical evaluation of exponential and independence assumptions in queueing models of manufacturing systems. Production and Operations Management, 8, 409-432.

Jacobs, D.A. and Meerkov, S.M. (1997) A system-theoretic property of serial production lines: improvability. International Journal of System Sciences, 26, 95-137.

Kuo, C.-T., Lim. J.-T., Meerkov, S.M. and Park, E. (1997) Improvability theory for assembly systems: two component--one assembly machine case. Mathematical Problems in Engineering, 3, 95-171.

Li, J. (2001) Performance analysis of production system with rework loops. Report R & D-9225, General Motors Research & Development Center, Warren, MI.

Lim, J.-T. and Meerkov, S.M. (1993) On asymptotic reliable closed serial production lines. Control Engineering Practices, 1, 147-152.

Mascolo, M.D., David, R. and Dallery, Y. (1991) Modeling and analysis of assembly systems with unreliable machines and finite buffers. IIE Transactions, 23, 315-330.

Onvural, R.O. (1990) A survey of closed queueing networks with blocking. ACM Computing Surveys, 22, 83-121.

Papadopoulos, H.T. and 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.

Patchong, A. and Willaeys, D. (2001) Modeling and analysis of an unreliable flow line composed of parallel-machine stages. IIE Transactions, 33, 559-568.

Suri, R., Sanders, J.L. and Kamath, M. (1993) Performance evaluation of production networks, in Handbooks in OR & MS: Volume 4, Graves S.C., Rinnooy Kan A.G., Zip Kin P. (eds.), Elsevier Science, Amsterdam, pp. 199-286.

Yerelan, S. and Tan, B. (1997) Analysis of multistation production systems with limited buffer capacity part 2: the decomposition method. Mathematics and Computer Modeling, 25, 109-123.

JINGSHAN LI

Manufacturing Systems Research Laboratory, General Motors Research & Development Center, Mail Code 480-106-359, 30500 Mound Road, Warren, MI 48090-9055, USA

E-mail: jingshan.li@gm.com

Biography

Jingshan Li received his Bachelor's degree from the Department of Automation, Tsinghua University. Beijing, China, in 1989 and a Master's degree from the Institute of Automation, Chinese Academy of Sciences, Beijing, China in 1992. He received his Ph.D. in Electrical Engineering--Systems from the University of Michigan, Ann Arbor, MI in 2000. From 2000, he has been a Senior Research Engineer at the Manufacturing Systems Research Laboratory, General Motors Research & Development Center, Warren, MI. His primary research interests are in the modeling and analysis of complex production systems. He is a member of IIE.

Contributed by the Manufacturing Systems Department