Performance analysis of assembly/disassembly systems with unreliable machines and random...

1. Introduction

This paper presents an approximate analytic method to estimate throughput rate and average buffer levels of assembly/disassembly (AD) systems. In this paper an AD system is defined as a manufacturing system in which some machines perform assembly operations and other

machines perform disassembly operations. An assembly operation is one by which two or more parts or subassemblies are brought together to form a single unit. A disassembly operation is one by which a single unit is separated into two or more parts or subassemblies. Such AD systems are used in many electronics and automobile manufacturing companies.

Various methods have been proposed for performance evaluation of AD systems. Harrison [1], Crane [2], Heidelberger and Trivedi [3], Duda and Czachorski [4], Baccelli et al. [5,6], and Liu and Perros [7,8] use queuing theories for the analysis of the performance of AD systems (they often call AD systems as split and match or fork-join systems). Most of these research articles deal with computer systems with an infinite buffer capacity and reliable processors (machines). Gershwin [9] proposes a decomposition algorithm for an approximate evaluation of the performance of AD systems with a limited buffer capacity and unreliable machines. However, the algorithm can deal with only homogenous systems in which processing times are constant and equal for all machines. A decomposition algorithm proposed by Mascolo et al. [10] deals with non-homogenous systems with different but constant processing times at the machines. This algorithm analyzes a non-homogenous system by transforming the system into a homogenous system in such a way that the performances of the two systems are close to each other. These two methods are extensions of earlier works on transfer lines that use decomposition methods. Note that a transfer line is a special form of AD systems.

The decomposition method is suggested by Gershwin [11] for an approximate evaluation of performance of transfer lines composed of multiple machines. The method is based on decomposition of a transfer line with multiple machines into a set of two-machine lines. Two-machine lines and three-machine lines can be evaluated with exact analytical models of Gershwin and Berman [12] and Gershwin and Schick [13], respectively. The original iterative algorithm of Gershwin [11] for transfer lines gives very accurate results, but it is fairly complex and unreliable (it may fail to converge) as noted by Mascolo et al. [10]. Other methods have been proposed to avoid such drawbacks. Dallery et al. [14] and Xie [15] give efficient algorithms for systems in which processing times are constant and equal on all machines (homogenous systems). Other researchers deal with systems in which processing times may be different on different machines (non-homogenous systems). For example, Dallery et al. [16], Glassey and Hong [17], and Alvarez-Vergas et al. [18] consider systems in which processing times are (unequal) constants, and Choong and Gershwin [19] and Hong et al. [20] assume that processing times are exponentially distributed. (See Dallery and Gershwin [21] and Gershwin [22] for further reviews of various methods for estimating performance of flow line systems).

In this paper we propose a decomposition method for performance evaluation of AD systems in which sizes of buffers are finite, and the times between failures and the times to repair are exponentially distributed. Unlike previous works of Gershwin [9] and Mascolo et al. [10], we consider non-homogenous AD systems with exponential processing times. Studies on systems with such characteristics may be more practicable for unpaced AD systems that have different processing times at different machines, because it is difficult to balance workloads perfectly in such systems. Moreover, if multiple products or multiple models are produced in a system, processing times on the same machine may be different for different items. In addition to this, stochasticity of processing times may be caused by minor disturbances (excluding machine breakdowns) in the manufacturing system such as tool breakage, shortage of lubricating oil, or variability of human workers.

The proposed method decomposes a K-machine tree-structured AD system to a system of K - 1 two-machine lines and then finds the processing rates, failure rates, and repair rates of the machines in the decomposed system that make performances of the two systems close to each other. To determine the unknown parameters (rates) in the decomposed system, we derive equations based on interruption of flow, resumption of flow, and flow rate-idle time relations, and propose two methods that use the equations differently. Performance of these two methods is analyzed through extensive computational experiments.

This paper is organized as follows. First we describe the AD system to be considered in this paper in the next section. In Section 3 we describe the decomposition method and derive equations needed for analyzing the AD system with the method. These equations are used in two computational algorithms suggested for performance evaluation of the AD system. To show the performance of the methods, computational tests are done on a real manufacturing system and a number of hypothetical systems with randomly generated data, and test results are reported in Section 4, which is followed by conclusions in Section 5.

2. The AD system

AD systems consist of machines in which assembly and/ or disassembly operations take place, and buffers that connect the machines. This paper focuses on tree-structured AD systems, in which any two machines are connected by exactly one path (sequence of machines and buffers), i.e., each buffer connects exactly two machines (an upstream machine and a downstream machine). Therefore, there are K - 1 buffers in a tree-structured AD system with K machines. A tree-structured AD system is illustrated in Fig. 1, in which [M.sub.i] denotes machine i and [B.sub.i,j] denotes the buffer having [M.sub.i] as the upstream machine and Ms as the downstream machine. A machine with two or more upstream buffers performs assembly operations and is called an assembly machine. When it does an operation it takes one part from each of its upstream buffers. A machine with two or more downstream buffers is called a disassembly machine. When it completes an operation it adds one part to each of its downstream buffers. In an AD system there are several input machines, which do not have any upstream buffer, and output machines, which do not have any downstream buffer. In the example given in Fig. 1, machines [M.sub.3] and [M.sub.8] are assembly machines, machine [M.sub.4] is a disassembly machine, machines [M.sub.1], [M.sub.2], [M.sub.5], and [M.sub.6] are input machines, and machines [M.sub.7] and [M.sub.8] are output machines.

[Figure 1 ILLUSTRATION OMITTED]

A machine is blocked if any one of its downstream buffers is full when it finishes processing a unit. Similarly, a machine is starved if any one of its upstream buffers is empty when it discharges a processed unit. A machine is blocked or starved mainly owing to failure(s) of its downstream or upstream machines, but it may also be so even when machines are operational, owing to the variability of processing times on downstream or upstream machines. It is assumed that input machines are never starved and output machines are never blocked.

Each machine in the system is characterized by three parameters: the time between failures, the time to repair, and the processing time. It is assumed that these are exponentially distributed random variables with known means. Each buffer in the system is characterized by storage capacity. In this paper these parameters are denoted as follows:

[[Lambda].sub.i]: failure rate of machine [M.sub.i];

[[micro].sub.i]: repair rate of machine [M.sub.i];

[[Rho].sub.i]: processing rate of machine [M.sub.i];

[C.sub.i,j]: storage capacity of buffer [B.sub.i,j].

The machines can be in one of four states: operational, under repair, blocked, or starved. Let [m.sub.i] denote the state of machine [M.sub.i], i.e., [m.sub.i] = 1, 0, B, and S when [M.sub.i] is operational (processing a unit), under repair, blocked, and starved, respectively. Also, let [b.sub.i,j] denote the state of buffer [B.sub.i,j], i.e., the number of items in the buffer. It is assumed that a machine does not fail when it is blocked or starved, that is, a machine can fail only when it is processing a unit. When a machine fails, the unit being processed remains at that machine until the machine is repaired, then the machine resumes processing the same unit.

3. Decomposition methods

Although AD systems with a small number of stations can be analyzed exactly using Markov chain models, most real AD systems cannot be because there exist an extremely large number of system states for a system of a practical size. Decomposition methods divide a large system into many small ones. Here, the small systems are two-machine lines each of which consists of a buffer, an upstream machine and a downstream machine. Parameters that specify characteristics of these machines are chosen so that the behavior of material flow in a buffer of a two-machine line closely matches that of its corresponding buffer in the large system. In this section we present a decomposition method for analyzing the tree-structured AD systems described in the previous section.

Because of the tree structure, there are K - 1 buffers in a K-machine AD system. We decompose the system into K - 1 two-machine lines as shown in Fig. 2. Let [L.sub.i,j] denote the two-machine line consisting of buffer [B.sub.i,j] and machines [M.sub.u(i,j)] and [M.sub.d(i,j)], which represent the upstream and downstream of the buffer, respectively, as shown in Fig. 1. Since [M.sub.u(i,j)] is the input machine and [M.sub.d(i,j)] is the output machine in decomposed line [L.sub.(i,j)], [M.sub.u(i,j)] cannot be starved and [M.sub.d(i,j)] cannot be blocked. Therefore, there are three states for machine [M.sub.u(i,j)], i.e., operational ([m.sub.u(i,j)] = 1), under repair ([m.sub.u(i,j)] = 0), and blocked ([m.sub.u(i,j)] = B). Similarly, three states exist for [M.sub.d(i,j)], i.e., operational ([m.sub.d(i,j)] = 1), under repair ([m.sub.d(i,j)] = 0), and starved ([m.sub.d(i,j)] = S). It is assumed that [M.sub.u(i,j)] and [M.sub.d(i,j)] can be characterized by three exponential variables with parameters

[[Lambda].sub.u(i,j)], [[micro].sub.u(i,j)], [[Rho].sub.u(i,j): failure, repair, and processing rates of [M.sub.u(i,j)], respectively;

[[Lambda].sub.d(i,j)],[[micro].sub.d(i,j)], [[Rho].sub.d(i,j)]: failure, repair, and processing rates of [M.sub.d(i,j)], respectively.

[Figure 2 ILLUSTRATION OMITTED]

Fig. 3 illustrates an AD system and corresponding decomposed two-machine lines. When Mi is operational, both its outflow rate (into [B.sub.i,m]) and its inflow rate (from [B.sub.j,i] are [[Rho].sub.i]. In the approximation method suggested in this paper, the flow rate from [M.sub.u(i,m)] to [B.sub.i,m] in decomposed line [L.sub.i,m] is set to be equal to the flow rate from [M.sub.i] to [B.sub.i.m] in the original system. Similarly, the flow rate from [B.sub.j,i] to [M.sub.d(j,i)] in decomposed line [L.sub.j,i] is set to be equal to the flow rate from [B.sub.j,i] to [M.sub.i] in the original system. Therefore, we have

(1) [[Rho].sub.u(i,m)] = [[Rho].sub.d(j,i) = [[Rho].sub.i]

From (1) we can determine [[Rho].sub.u(i,j)] and [[Rho].sub.d(i,j)], but four more parameters in each decomposed line still remain undetermined. Therefore, we have to derive 4(K- 1) more equations to determine these unknown parameters of K - 1 decomposed lines, which are [[Lambda].sub.u(i,j)], [[Lambda].sub.d(i,j)], [[micro].sub.u(i,j)], and [[micro].sub.d(i,j)].

[Figure 3 ILLUSTRATION OMITTED]

3.1. Conservation of flow

Since items cannot be created or destroyed during the process in the AD system, flow is conserved. Therefore, we have

(2) E = [E.sub.1] = [E.sub.2] = ... = [E.sub.K],

where E and [E.sub.i] denote the steady-state throughput rates of the AD system and machine [M.sub.i], respectively.

Let [E.sub.u(i,m)] and [E.sub.d(j,i)] denote the steady-state throughput rates of machines [M.sub.u(i,m)] and [M.sub.d(j,i)], respectively. Here, the steady-state throughput rates of machines [M.sub.u(i,m)] and [M.sub.d(j,i) in the decomposed lines are set to be equal to that of machine [M.sub.i] in the original system, that is, conservation of flow is represented by

(3) [E.sub.u(i,m)] = [E.sub.d(j,i)] = [E.sub.i] = E, [inverted]Ai.

3.2. Flow rate-idle time relations

The isolated throughput rate of machine [M.sub.i] is given by [[Rho].sub.i][[micro].sub.i]([[Lambda].sub.i] + [[micro].sub.i]) if the effects of other machines and buffers (on machine [M.sub.i]) are ignored. However, the actual throughput rate is lower than the isolated throughput rate because of idle times due to blocking or starvation. The actual steady-state throughput rates of machines [M.sub.i], [M.sub.d(k,i)] and [M.sub.u(i,n)] can be written as

(4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [U.sub.i] be the set of machines that are directly connected with upstream buffers of machine [M.sub.i] and [D.sub.i] be the set of machines that are directly connected with downstream buffers of machine [M.sub.i]. Also, let [PS.sub.k,i] denote the probability that machine [M.SUB.i] is starved by buffer [B.sub.k,i] and [PB.sub.i,n] denote the probability that machine [M.sub.i]. is blocked by buffer [B.sub.i,n]. The probability that [M.sub.i] is starved because two or more upstream buffers are empty at the same time can be considered to be small, and so can be the probability that [M.sub.i] is blocked because two or more downstream buffers are full at the same time. Therefore, prob{[m.sub.i] = S} can be approximated by [[Sigma].sub.k[element of][U.sub.i]] [PS.sub.k,i] and prob{[m.sub.i] = B} can be approximated by [[Sigma].sub.n[element of][D.sub.i]], [PB.sub.i,n]. With this approximation, we have

(7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

To make the performances of the original and the decomposed systems close to each other, the probability that machine [M.sub.d(k,i)] is starved is set equal to [PS.sub.k,i], and the probability that machine [M.sub.u(i,n)] is blocked is set equal to [PB.sub.i,n]. Then, [E.sub.i] can be rewritten as

(8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Additionally, from (5) and (6), we have

(9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

With (9) and (10), (8) becomes

(11) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [E.sub.d(k,i)] = [E.sub.u(i,n)] = [E.sub.i] = E, the above equation can be written as

(12) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [u.sub.i] and [d.sub.i] denote the number of upstream and downstream buffers of machine [M.sub.i], respectively, or [u.sub.i] = |[U.sub.i]| and [d.sub.i] = |[D.sub.i]| (|A| represents the cardinality of set A).

From (12) we can obtain the following equations:

(13) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(14) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In the above equations, E can be replaced by the average of [E.sub.d(k,i)] and [E.sub.u(i.n)] [inverted] A k [element of] [U.sub.i] and n [element of] [D.sub.i] since all decomposed lines are supposed to have the same throughput rate.

3.3. Interruption of flow

Failure of a machine in the decomposed line corresponds to interruption of flow into or out of its corresponding machine in the AD system caused by failure, starvation, or blocking. Therefore, failure rates of the machines in the decomposed lines can be obtained as follows. Let [m.sub.d(j,i)] (t) be the state of machine [M.sub.d(j,i)] at time t. Failure rate [[Lambda].sub.d(j,i)] of machine [M.sub.d(j,i)] can be defined with

(15) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

or equivalently,

(16) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The state that [M.sub.d(j,i)] is down ([m.sub.d(j,i)] = 0) can be interpreted as one of the following three mutually disjoint sets of states: (1) failure of [M.sub.i] itself ([m.sub.i] = 0); (2) [M.sub.i] is starved because of one or more of buffers [B.sub.k,i] for k [element of] [U.sub.i], k [is not equal to] ([U.sub.k [element of] [U.sub.i], [k [is not equal to] j] {[m.sub.d(k,i)]: S}); and (3) [M.sub.i] is blocked because of one or more of buffers [B.sub.i,n] for n [element of] [D.sub.i] (([U.sub.n [element of] [D.sub.i] {[m.sub.u(i,n)] =B}). Since the probabilities that [M.sub.i] is starved because of two or more buffers at the same time and that [M.sub.i] is blocked because of two or more buffers at the same time can be considered to be small, failure rate of [M.sub.d(j,i)] can be approximated with the following equation

(17) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The right-hand side of (17) can be simplified as follows. [M.sub.i] is under repair at time t + [Delta]t given that [M.sub.d(j,i)] is operational at time t, only if [M.sub.i] fails during time interval It, t + [Delta]t]. Therefore, the first term at the right-hand side of (17) can be written as

(18) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Consider the second term at the right-hand side of (17). If [B.sub.k,i] is not empty at time t, [M.sub.d(k,i)] cannot be starved at time t + [Delta]t. Therefore, when [m.sub.d(k,i)](t + [Delta]t) = S, [b.sub.k,i] (t) = 0, where [b.sub.k,i] (t) denotes the state of buffer [B.sub.k,i] at time t. Additionally, in the approximation method suggested in this paper, the state that [M.sub.d(j,i)] is operational ([m.sub.d(j,i)] = 1) is set to be equivalent to the state that [M.sub.i] is operational ([m.sub.i]: l). Therefore, we have

(19) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The last equality holds because [M.sub.d(k,i)] is starved at time t + [Delta]t given that [B.sub.k,i] is empty at time t and [M.sub.i] is operational at time t, only if [M.sub.i] finishes a unit during time interval [t, t + [Delta]t].

Finally, if [B.sub.i,n] is not full at time t, [M.sub.u(i,n)] cannot be blocked at time t+ [Delta]t. In other words, when [m.sub.u(i,n)] (t + [Delta]t)= B, [b.sub.i,n] (t) = [C.sub.i,n] where [C.sub.i,n] is the capacity of buffer [B.sub.i,n] as defined earlier. Since the state that [M.sub.d(j,i)] is operational ([m.sub.d(j,i)] = 1) is set to be equivalent to the state that [M.sub.i] is operational ([m.sub.i] = 1), the third term can be simplified as follows:

(20) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The last equality holds because [M.sub.u(i,n)] is blocked at time t + [Delta]t given that [B.sub.i,n] is full at time t and [M.sub.i] is operational at time t only if [M.sub.i]. finishes a unit during time interval [t, t + [Delta]t].

From (17)-(20), we have

(21) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since in the decomposition method, prob {[b.sub.k,i] = 0, [m.sub.i] = 1} and prob{[b.sub.i,n] = [C.sub.i,n], [m.sub.i] = 1 } are replaced by prob {[b.sub.k,i] = 0, [m.sub.d(k,i)] = 1} and prob {[b.sub.i,n] = [C.sub.i,n], [m.sub.u(i,n)] = 1 }, respectively, failure rate of [M.sub.d(j,i)] is given by

(22) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Similarly, failure rate of [M.sub.u(i,m)] can be written as

(23) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.4. Resumption of flow

Repair of a machine in the decomposed line corresponds to resumption of flow into or out of its corresponding machine in the AD system caused by repair, termination of starvation, or termination of blocking. Therefore, repair rates of the machines in the decomposed lines can be obtained (approximated) as follows. Repair rate [[Mu].sub.d(j,i)] of machine [M.sub.d(j,i)] can be defined with

(24) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

or equivalently,

(25) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In a method similar to that for deriving failure rates of decomposed lines, repair rate of [M.sub.d(j,i)] can be approximated with

(26) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The right-hand side of (26) can be simplified as follows. First, [M.sub.d(j,i)] is operational at time t + [Delta]t given that [M.sub.i] is under repair at time t, only if [M.sub.i] is repaired during time interval [t, t + [Delta]t]. Therefore, the first term at the right-hand side of (26) can be written as

(27) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Consider the second term at the right-hand side of (26). In the approximation method suggested in this paper, the state [m.sub.d(k,i)] = S is set to be equivalent to the state that [M.sub.i] is starved because of [B.sub.k,i]([b.sub.k,i] = 0, [m.sub.i] = S). In this case, [M.sub.d(j,i)] is considered to be nonoperational (under repair) at time t in the decomposed method. Therefore, [M.sub.d(j,i)] can be operational at time t + [Delta]t, only if [M.sub.i] becomes operational during time interval [t, t + [Delta]t]. For [M.sub.i] to be operational at time t + [Delta]t, [M.sub.k] must be operational at time t, because [M.sub.k] should finish a unit during time interval [t, t + [Delta]t] and send the finished unit to [M.sub.i]. Therefore, we have

(28) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The last equality holds because [M.sub.d(j,i)] is operational at time t + [Delta]t given that [M.sub.k] is operational at time t, [B.sub.k,i] is empty at time t, and [M.sub.i] is starved at time t, only if [M.sub.k] finishes a unit during time interval It, t + [Delta]t].

Now consider the third term at the right-hand side of (26). In the approximation method suggested in this paper, the state [m.sub.u(i,n)] = B is set to be equivalent to the state that [M.sub.i] is blocked because of [B.sub.i,n]([m.sub.i] = B, [b.sub.i,n] = [C.sub.i,n)]. In this case, [M.sub.d(j,i)] is considered to be nonoperational (under repair) at time t in the decomposed method. Therefore, [M.sub.d(j,i)] can be operational at time t + [Delta]t only if [M.sub.i] becomes operational during time interval [t, t + [Delta]t]. For [M.sub.i] to be operational at time t + [Delta]t, [M.sub.n] must be operational at time t, because [M.sub.n] should finish a unit during time interval It, t + [Delta]t]. Therefore, we have

(29) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The last equality holds because [M.sub.d(j,i)] is operational at time t + [Delta]t given that [M.sub.i] is blocked at time t, [B.sub.i,n] is full at time t, and [M.sub.n] is operational at time t, only if [M.sub.n] finishes a unit during time interval [t, t + [Delta]t].

From (26)-(29) we have

(30) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since prob{[m.sub.i] = 1} = prob{[M.sub.d(j,i)]= 1} from (1), (3), (4), and (5), we have

(31) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But prob{[m.sub.i] = S} and prob{[m.sub.i] = B} can be approximated by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], prob{[m.sub.d(k,i)] = S} and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], prob {[m.sub.u(i,n)] = B}, respectively. Therefore,

(32) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In addition, since prob{[m.sub.k] = 1, [b.sub.k,i] = 0, [m.sub.i] = S} and prob{[m.sub.i] = B, [b.sub.i,n] = [C.sub.i,n], [m.sub.n] = 1} can be replaced with prob{[m.sub.u(k.i)] = 1, [m.sub.d(k,i)] = S} and prob{[m.sub.u(i,n)] = B, [m.sub.d(i,n)] = 1}, respectively, repair rate of [M.sub.d(j,i)] given by (30) can be written as

(33) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Similarly, repair rate of [M.sub.u(i,m)] can be written as

(34) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.5. Boundary conditions

Failure and repair rates of an input machine are equated with those of the corresponding upstream machine, whereas failure and repair rates of an output machine are equated with those of the corresponding downstream machine. That is,

(35) [[Lambda].sub.u(i,m)] = [[Lambda].sub.i] and [[Mu].sub.u(i,m)] = [[Mu].sub,i], for i [element of] I,

(36) [[Lambda].sub.d(j,i)] = [[Lambda].sub.i] and [[Mu].sub.d(j,i)] = [[Mu].sub.i], for i [element of] O,

where I is the set of input machines and O is the set of output machines, i.e., [U.sub.i] = ?? for i [element of] I and [D.sub.i] = ?? for i [element of] O.

3.6. Computational methods

We propose two decomposition methods. One, called IF, is based on interruption of flow and flow rate-idle time relations and the other, called RF, is based on resumption of flow and flow rate-idle time relations. In both methods, processing rates in the decomposed lines are determined by (1). However, IF determines failure and repair rates in the decomposed lines based on interruption of flow and flow rate-idle time relations, respectively, whereas RF determines repair and failure rates in the decomposed lines based on resumption of flow and flow rate-idle time relations, respectively.

Because it is not easy to solve equations required for the rates analytically, the iterative computational algorithm proposed by Mascolo et al. [15] is used in this study. This algorithm uses an evaluation list of N two-machine lines {[L'.sub.1], [L'.sub.2], ... , [L'.sub.N]}, which is prepared in such a way that two-machine lines that contain either an input machine or an output machine appear exactly once, other two-machine lines appear exactly twice, and two consecutive lines, [L'.sub.n] and [L.sub.n+1], have one common machine. (Note that N = 2(K - 1) - |I| - |O|.) The algorithm can be summarized as follows (see [10] for more details).

Algorithms (IF, RF)

Step 1. Let [[Lambda].sub.u(i,m)] [[Lambda].sub.d(j,i)] = [[Lambda].sub.i],[[Mu].sub.u(i,m)] = [[Mu].sub.d(j,i)] = [[Mu].sub.i], and [[Rho].sub.u(i,m)] = [[Rho].sub.d(j,i)] = [[Rho].sub.i] and prepare an evaluation list. Let the iteration count k = 0. Using a two-machine line model (such as those of Gershwin and Berman [12], Hong and Seong [23], and Gershwin [22]), evaluate all of the decomposed two-machine lines and obtain throughput rates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the throughput rate of decomposed line [L.sub.i,j] at the kth iteration.

Step 2. Let k = k+1 and n = 1.

Step 3. Consider the nth two-machine line of the evaluation list, [L'.sub.n]. Assume [L.sub.i, j] is the nth line, i.e., [L'.sub.n] = [L.sub.i,j]. If the common machine of [L'.sub.n], [L'.sub.n-1] ([L'.sub.0] and [L'.sub.N] are identical here) is the downstream machine of [L'.sub.n], i.e., machine j, do:

(IF) Calculate [[Lambda].sub.d(i,j)] and [[Mu].sub.d(i,j)] using (22) and

(13), respectively.

(RF) Calculate [[Mu].sub.d(i,j)] and [[Lambda].sub.d(i,j)] using (33) and

(13), respectively.

If the common machine of [L'.sub.n] and [L'.sub.n-1] is the

upstream machine of [L'.sub.n], i.e. machine i, do:

(IF) Calculate [[Lambda].sub.u(i,j)] and [[Mu].sub.u(i,j)] using (23) and

(14), respectively.

(RF) Calculate [[Mu].sub.(i,j)] and [[Lambda].sub.u(i,j)] using (34) and

(14), respectively.

Obtain throughput rate [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Step 4. If n [is less than] N, let n = n+1 and go to step 3. Otherwise, go to step 5.

Step 5. If difference in throughput rates of two consecutive iterations is less than e, that is, if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [is less than or equal to] [Epsilon], stop. Otherwise, go to step 2.

In the above algorithm, the decomposed two-machine line [L.sub.i,j]. is evaluated using an algorithm for calculating the steady-state probabilities of the continuous-time Markov chain with 4([C.sub.i,j]. + 2) states. The steady-state throughput rate of the AD system can be obtained from the steady-state throughput rate of any decomposed line. Note that the steady-state throughput rate is equal for all decomposed lines when the algorithm converges. The average buffer level of [B.sub.i,j] can also be obtained from the average buffer level of the corresponding decomposed line [L.sub.i,j]. The parameter [Epsilon] used for the stopping criterion in the algorithms was set to be 0.00001 in the computational experiments reported in the next section.

4. Computational experiments

For a comparison of the proposed methods IF and RF, they are applied to a body assembly shop of an automobile manufacturing company. Since this company is constructing a new body assembly shop, it is necessary to evaluate many alternative designs for various scenarios for the shop such as different failure, repair, and processing rates. Simulation may be used to evaluate the alternatives, but computation time required for evaluation of an alternative is not short enough for evaluation of all (or many) alternatives.

Fig. 4 shows the body assembly shop, which is composed of 21 work stations and 20 inter-station buffers. The failure, repair, and processing rates of the work stations and storage capacities of the buffers are shown in Tables 1 and 2. A simulation study on the shop was done to compare throughput rate and average buffer levels from the suggested methods with those from simulation.

[Figure 4 ILLUSTRATION OMITTED]

Table 1. Data for the work stations

Work station     Failure rate    Repair rate    Process&g rate
                 (per minute)    (per minute)    (per minute)

FF                 0.00190         0.05722          1.22449
FW                 0.00123         0.05769          1.22449
FC                 0.00123         0.05630          1.22449
RF                 0.00323         0.05681          1.22449
UC                 0.00611         0.05642          1.17647
SIR                0.00105         0.05159          1.22449
RC                 0.00001         0.05000          1.22449
SCR                0.00347         0.05672          1.17647
SIL                0.00105         0.05159          1.22449
SCL                0.00347         0.05672          1.17647
BF                 0.00290         0.05687          1.15385
BR                 0.00492         0.05644          1.15385
TL                 0.00028         0.06960          1.30435
FDR                0.00025         0.06600          1.30435
RDR                0.00018         0.06781          1.30435
TG                 0.00030         0.07053          1.39535
EH                 0.00022         0.07044          1.39535
FDL                0.00025         0.06600          1.30435
RDL                0.00018         0.06781          1.30435
MI                 0.00122         0.05732          1.11111
BI                 0.00006         0.08404          1.11111

Table 2. Storage capacity of the buffers

Buffer        1    2    3    4    5    6    7    8    9   10
Capacity     10   11   10   11   10   10    3   12   10   12

Buffer       11   12   13   14   15   16   17   18   19   20
Capacity     10   11    8    5    7   14    5    5    7   10

Ten replications of the simulation were made so as to obtain statistically reliable simulation results. In each replication, 31 000 time units were simulated and statistics during [1000, 31 000] were gathered. The computational algorithm and the simulation model were implemented using the C language and run on a personal computer (PC) with a Pentium processor (120 MHz).

Table 3 shows failure and repair rates of machines in the decomposed lines and buffer levels from IF, RF, and simulation. The throughput rates estimated by IF and RF were 0.788 and 0.786, respectively, whereas the average throughput rate obtained from the simulation was 0.746 (standard deviation was 0.008). The methods overestimate the throughput rate by 5.6%, which does not seem to be excessive considering the size of the system (21 stations). It took 1.15 seconds to obtain a solution for each of IF and RF.

Table 3. Results from the decomposition methods and simulation on the body assembly shop

Decomposed line

L (b)         [MATHEMATICAL           [MATHEMATICAL
               EXPRESSION              EXPRESSION
             NOT REPRODUCIBLE        NOT REPRODUCIBLE
                IN ASCII]               IN ASCII]

L(1)             0.00190                 0.05722
                 0.00190                 0.05722
L(2)             0.00123                 0.05769
                 0.00123                 0.05769
L(3)             0.00123                 0.05630
                 0.00123                 0.05630
L(4)             0.00323                 0.05681
                 0.00323                 0.05681
L(5)             0.06339                 0.24851
                 0.06516                 0.25515
L(6)             0.00001                 0.05000
                 0.00001                 0.05000
L(7)             0.00105                 0.05159
                 0.00105                 0.05159
L(8)             0.15026                 0.68685
                 0.15364                 0.69829
L(9)             0.00105                 0.05159
                 0.00105                 0.05159
L(10)            0.01701                 0.18928
                 0.01731                 0.19253
L(11)            0.14522                 0.42174
                 0.15086                 0.43651
L(12)            0.12771                 0.37655
                 0.13133                 0.38050
L(13)            0.00028                 0.06960
                 0.00028                 0.06960
L(14)            0.00025                 0.06600
                 0.00025                 0.06600
L(15)            0.00018                 0.06781
                 0.00018                 0.06781
L(16)            0.00030                 0.07053
                 0.00030                 0.07053
L(17)            0.00022                 0.07044
                 0.00022                 0.07044
L(18)            0.00025                 0.06600
                 0.00025                 0.06600
L(19)            0.00018                 0.06781
                 0.00018                 0.06781
L(20)            0.26271                 0.67121
                 0.26717                 0.67410

Decomposed line

L (b)         [MATHEMATICAL           [MATHEMATICAL
               EXPRESSION              EXPRESSION
             NOT REPRODUCIBLE        NOT REPRODUCIBLE
                IN ASCII]               IN ASCII]

L(1)             0.20973                 0.46327
                 0.20696                 0.45242
L(2)             0.21454                 0.46011
                 0.21284                 0.45179
L(3)             0.21093                 0.45799
                 0.20848                 0.44804
L(4)             0.21097                 0.47690
                 0.20832                 0.46586
L(5)             0.16560                 0.54771
                 0.15352                 0.50115
L(6)             0.22419                 0.49878
                 0.22419                 0.49349
L(7)             0.16997                 0.50798
                 0.16068                 0.47513
L(8)             0.19426                 0.49836
                 0.18688                 0.47476
L(9)             0.24669                 0.53225
                 0.24443                 0.52194
L(10)            0.21517                 0.51352
                 0.21265                 0.50137
L(11)            0.10349                 0.48930
                 0.08491                 0.40381
L(12)            0.18513                 0.85934
                 0.17083                 0.79483
L(13)            0.27048                 0.68524
                 0.27217                 0.68144
L(14)            0.24072                 0.65906
                 0.23835                 0.64464
L(15)            0.26466                 0.67981
                 0.26538                 0.67358
L(16)            0.28177                 0.69163
                 0.28551                 0.69300
L(17)            0.25047                 0.66346
                 0.24978                 0.65372
L(18)            0.24072                 0.65906
                 0.23835                 0.64464
L(19)            0.26466                 0.67981
                 0.26538                 0.67358
L(20)            0.00006                 0.08404
                 0.00006                 0.08404

Decomposed line         Average buffer level

                   Decomposition        Simulation
L (b)              methods(a)
                                    Mean     Std. dev.

L(1)                  8.08          8.26       0.088
                      8.08
L(2)                  9.11          9.34       0.069
                      9.12
L(3)                  8.16          8.32       0.088
                      8.17
L(4)                  8.80          8.88       0.095
                      8.81
L(5)                  5.79          6.17       0.173
                      5.81
L(6)                  8.39          8.55       0.063
                      8.40
L(7)                  2.03          2.09       0.015
                      2.03
L(8)                  7.91          9.66       0.145
                      7.92
L(9)                  8.23          8.32       0.073
                      8.23
L(10)                 9.18          9.27       0.148
                      9.20
L(11)                 4.36          3.91       0.217
                      4.38
L(12)                 5.11          4.15       0.226
                      5.07
L(13)                 6.82          7.05       0.033
                      6.83
L(14)                 3.99          4.13       0.018
                      4.00
L(15)                 5.87          6.07       0.042
                      5.88
L(16)                12.95         13.23       0.047
                     12.96
L(17)                 4.15          4.30       0.028
                      4.16
L(18)                 3.99          4.13       0.015
                      4.00
L(19)                 5.87          6.07       0.039
                      5.88
L(20)                 2.07          1.87.      0.077
                      2.05

(1) Figures in the upper lines of the entries are results from IF and those in the lower lines of the entries are results from RF.

To test the performance of the proposed methods for AD systems of various structures, we additionally performed a series of computational experiments. Four types of the tree structure were tested: one type (structure 1) was composed of three machines and the rest (structures 2-4) were composed of eight machines as shown in Fig. 5. Each structure was tested under various parameter settings, i.e. different levels for repair rates, failure rates, and buffer capacities, each of which is characterized by (r, f, C). That is, the repair rate ([[micro].sub.i]) of each machine is generated from U(0.9r, 1.1r), the uniform distribution with a range 0.9r to 1.1r, and the failure rate ([[Lambda].sub.i]) of each machine is generated from U(0.9rf, 1.1rf), whereas the capacity of each buffer is fixed at C. The processing rate ([[Rho].sub.i]) of each machine is generated from U(0.9, 1.1). We generated 20 problem instances for each of all combinations of three levels for r (0.05, 0.1, 0.5), three levels for f (0.01, 0.05, 0.1), and three levels for C (5, 10, 15). Therefore, a total of 540 problem instances was tested for each type of the tree structures.

[Figure 5 ILLUSTRATION OMITTED]

A simulation study on these problem instances was also done to compare results of the methods with simulation results. Ten replications were made for each problem instance. In each replication, 31 000 time units were simulated, but the initial 1000 time units were not used in the evaluation. To compare throughput rates from the methods with those from the simulation, we use a measure called relative deviation percentage (RDP), which shows the ratio of the difference of the throughput rates from the methods and the simulation to the throughput rate from the simulation. Table 4 shows the average RDP of 20 problem instances for each of the parameter sets and different structures.

Table 4. Average relative deviation percentages of the problem sets

Method   structure    C...                5
                      f\r      0.05      0.1      0.5

IF           1        0.01     1.53     1.73      2.01
                      0.05     1.27     1.39      2.26
                      0.10     1.59     1.78      2.98
             2        0.01     7.22     8.07      9.10
                      0.05     3.20     5.16      9.44
                      0.10     1.35     4.02     10.64
             3        0.01     6.55     7.11      7.96
                      0.05     2.31     4.07      7.82
                      0.10     0.67     1.81      8.77
             4        0.01     6.19     6.90      8.02
                      0.05     1.84     3.94      8.17
                      0.10     0.60     2.90      9.54

RF           1        0.01     1.67     1.85      1.97
                      0.05     1.48     1.57      2.17
                      0.10     1.88     1.96      2.83
             2        0.01     7.56     8.30      8.63
                      0.05     3.68     5.39      8.75
                      0.10     1.80     4.14      9.67
             3        0.01     6.70     7.21      7.78
                      0.05     2.59     4.25      7.61
                      0.10     0.28     2.03      8.47
             4        0.01     6.56     7.16      7.63
                      0.05     2.36     4.21      7.62
                      0.10     0.02     3.13      8.64

Method   structure              10                     15
                      0.05     0.1     0.5    0.05     0.1     0.5

IF           1        0.27    0.28    0.51    0.26    0.07    0.07
                      0.01    0.04    0.85    0.63    0.32    0.35
                      0.60    0.73    1.48    0.27    0.27    1.00
             2        0.62    1.43    2.75    1.09    0.20    0.75
                      3.54    0.72    3.05    5.18    2.30    1.05
                      4.11    1.10    4.00    5.60    2.53    1.90
             3        1.24    1.92    3.01    0.32    0.37    1.14
                      2.51    0.44    3.23    3.32    1.58    1.50
                      4.42    1.87    3.72    4.33    2.05    2.16
             4        0.25    1.25    2.33    1.23    0.18    0.71
                      3.92    1.43    2.71    5.37    2.58    0.94
                      5.12    1.92    3.58    6.12    2.82    1.73

RF           1        0.36    0.34    0.50    0.19    0.03    0.06
                      0.20    0.19    0.79    0.42    0.21    0.32
                      0.93    0.83    1.36    0.54    0.35    0.95
             2        0.79    1.56    2.65    1.02    0.15    0.71
                      3.24    0.54    2.81    4.94    2.21    0.96
                      3.67    1.00    3.62    5.25    2.51    1.74
             3        1.33    1.98    2.95    0.27    0.39    1.11
                      2.18    0.26    3.14    2.92    1.46    1.47
                      3.84    1.48    3.61    3.59    1.76    2.11
             4        0.39    1.36    2.22    1.16    0.13    0.68
                      3.51    1.20    2.49    5.09    2.44    0.86
                      4.45    1.59    3.23    5.52    2.66    1.58

In general, both methods, IF and RF, gave good estimates. Table 5 summarizes the results from the computational experiments. The test results indicate that two methods reveal almost the same performance. The overall average RDPs of IF and RF were 2.81% and 2.72%, respectively. The average CPU times (on the PC with a Pentium processor) for IF were 0.03 and 0.16 seconds for the three-machine structure and the eight-machine structure, respectively, whereas those for RF were 0.04 and 0.18 seconds, respectively. RF was slightly better than IF in terms of accuracy (especially when repair and failure rates are high and buffer capacities are large), whereas IF required slightly shorter computation time than RF (especially when repair rates are low and buffer capacities are small). The accuracy of the estimates from the methods tends to decrease as the buffer capacities decrease and as failure rates increase (the accuracy does not seem to be affected much by repair rates). This may be explained as follows. When the buffer capacities are small and failure rates of the machines are large, the probabilities that a machine is starved because two or more upstream buffers are empty at the same time and that a machine is blocked because two or more downstream buffers are full at the same time become large. Therefore, in such cases, the proposed decomposition methods become less accurate.

Table 5. Summary of computational results

Factor       Level    RDP of       RDP of      Ratio of the
                      IF (%)       RF (%)       computation
                                               times(a) (%)

Structure    1         0.91         0.96           95.08
             2         3.71         3.60           87.61
             3         3.19         3.06           84.97
             4         3.42         3.25           90.87
r            0.05      2.63         2.57           85.44
             0.1       2.15         2.16           85.17
             0.5       3.65         3.44           98.29
f            0.01      2.63         2.65           86.92
             0.05      2.73         2.65           88.89
             0.1       3.06         2.86           93.09
C            5         4.72         4.71           85.88
             10        1.97         1.85           88.42
             15        1.73         1.60           94.60

Average                2.81         2.72           89.63

(a) (Computation time for IF/computation time for RF) x 100

To show the performance of the method on AD systems with a large number of machines, we perform another series of tests by increasing the number of machines from 4 to 30 in problems of the type 4 structure. In these problems, other data were generated with a processing rate of 1, a repair rate of 0.1, a failure rate of 0.005, and a buffer capacity of 10. The results are shown in Fig. 6. The accuracy of the estimates from the methods decreases as the number of machines in the AD system increases. A reason seems to be that when the method is applied to a large system, machines in decomposed lines represent upstreams or downstreams composed of a large number of machines in the original AD system, and the approximation of dynamics in upstreams or downstreams with that of a single machine becomes less accurate in such cases. Although the methods do not give very accurate estimates for large AD systems, they can be used as tools for (approximate) performance evaluation of large AD systems when a rough but quick performance evaluation is needed.

[Figure 6 ILLUSTRATION OMITTED]

5. Conclusion

We proposed an efficient decomposition method to evaluate the performance of tree-structured AD systems with finite buffer capacities where the times to failure, the times to repair, and the processing times are exponentially distributed. The method converts a K-machine tree-structured AD system into a system of K - 1 two-machine lines and then finds the processing rates, failure rates and repair rates of the latter system that make performance of the two systems close to each other. We proposed two methods IF and RF to determine the unknown parameters of decomposed lines. These two methods equate processing rates of decomposed lines to those of corresponding machines in the AD system. IF determines failure and repair rates based on interruption of flow and flow rate-idle time relations, respectively, whereas RF determines repair and failure rates based on resumption of flow and flow rate-idle time relations, respectively.

The results of computational experiments indicate that IF and RF converge well and they show almost the same performance. They gave relatively good estimates for throughput rate and average buffer levels of the AD systems in short times. The methods can be used as a viable tool for performance evaluation of AD systems when designing such systems because many alternative designs can be evaluated with the methods in a reasonable amount of time. For example, the suggested methods can be used when allocating a finite overall storage capacity to each of local buffers and adjusting processing rates, repair rates and/or failure rates of machines by considering trade-offs between throughput rate and investment costs for such adjustments.

Acknowledgements

We thank a referee for valuable comments on the earlier version of this paper that helped us improve the paper significantly. This research was supported by the Korea Science and Engineering Foundation under grant 9611012-095-1.

References

[1] Harrison, J.M. (1973) Assembly-like queues. Journal of Applied Probability, 10(3), 354-367.

[2] Crane, M.A. (1974) Multi-server assembly queues. Journal of Applied Probability, 11(3), 280-283.

[3] Heidelberger, P. and Trivedi, S.K. (1983) Analytic queuing models for programs with internal concurrency. IEEE Transactions on Computers, 32(1), 73-82.

[4] Duda, A. and Czachorski, T. (1987) Performance evaluation of fork and join synchronization primitives. Acta Informatica, 24(5), 525-553.

[5] Baccelli, F., Makowski, A.M. and Shwartz, A. (1989) The fork-join queue and related systems with synchronization constraints: stochastic ordering, approximations and computable bounds. Advances in Applied Probability, 21(3), 629-660.

[6] Baccelli, F., Massey, W.A. and Towsley, D. (1989) Acyclic fork-join queuing networks. Journal of the Association for Computing Machinery, 36(3), 615-642.

[7] Liu, Y.C. and Perros, H.G. (1991) A decomposition procedure for the analysis of a closed fork/join queuing system. IEEE Transactions on Computers, 40(3), 365-370.

[8] Liu, Y.C, and Perros, H.G. (1991) Approximate analysis of a closed fork/join model. European Journal of Operational Research, 53(3), 382-392.

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

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

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

[12] Gershwin, S.B. and Berman, O. (1981) Analysis of transfer lines consisting of two unreliable machines with random processing times and finite storage buffers. AIIE Transactions, 13(1), 2-11.

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

[14] Dallery, Y., David, R. and Xie, X. (1988) An efficient algorithm for analysis of transfer lines with unreliable machines and finite buffers, IIE Transactions, 20(3), 280-283.

[15] Xie, X. (1993) Performance analysis of a transfer line with unreliable machines and finite buffers. IIE Transactions, 25(1), 99108.

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

[17] Glassey, C.R. and Hong, Y. (1993) Analysis of behaviour of unreliable n-stage transfer line with (n - 1) inter-stage storage buffers. International Journal of Production Research, 31(3), 519-530.

[18] Alvarez-Vergas, R., Dallery, Y. and David, R. (1994) A study of the continuous flow-model of production lines with unreliable machines and finite buffers. Journal of Manufacturing Systems, 13(3), 221-234.

[19] Choong, Y.F. and Gershwin, S.B. (1987) A decomposition method for the approximate evaluation of capacited transfer lines with unreliable machines and random processing times. IIE Transactions, 19(2), 150-159.

[20] Hong, Y., Glassey, C.R. and Seong, D. (1992) The analysis of a production line with unreliable machines and random processing times. IIE Transactions, 24(1), 77-83.

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

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

[23] Hong, Y. and Seong, D. (1993) The analysis of an unreliable two-machine production line with random processing times. European Journal of Operational Research, 68(2), 228-235.

Biographies

Keun-Chae Jeong is a Ph.D. student at the Department of Industrial Engineering, Korea Advanced Institute of Science and Technology (KAIST). He received a B.S. from Korea University and an M.S. from KAIST both in Industrial Engineering. His research areas include analysis and design of manufacturing systems, real-time scheduling, knowledge-based decision support systems.

Yeong-Dae Kim is an Associate Professor at the Department of Industrial Engineering, KAIST. He received a B.S. from Seoul National University, an M.S. from KAIST both in Industrial Engineering, and a Ph.D. from the University of Michigan in Industrial and Operations Engineering. His research areas include design and operation of manufacturing systems, operations scheduling and production and inventory management. He is a senior member of IIE, a member of INFORMS and the Operational Research Society.

KEUN-CHAE JEONG and YEONG-DAE KIM Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, Yusong-gu, Daejon 305-701, Korea

Received July 1995 and accepted January 1997