当前位置:首页 >> >> 1 AN HYPER-EXPONENTIAL DECOMPOSITION METHOD FOR THE ANALYSIS OF PRODUCTION LINES WITH UNREL

1 AN HYPER-EXPONENTIAL DECOMPOSITION METHOD FOR THE ANALYSIS OF PRODUCTION LINES WITH UNREL

AN HYPER-EXPONENTIAL DECOMPOSITION METHOD FOR THE ANALYSIS OF PRODUCTION LINES WITH UNRELIABLE MACHINES AND FINITE BUFFERS
Hervé LE BIHAN and Yves DALLERY LIP6 (Laboratoire d’Informatique de Paris 6) Université Pierre et Marie Curie 4 Place Jussieu, 75252 Paris Cedex 05 FRANCE Herve.Lebihan@lip6.fr Yves.Dallery@lip6.fr

Abstract We consider production lines consisting of a series of machines separated by finite buffers. The processing time of each machine is deterministic and all the machines have the same processing time. All machines are subject to failures. As usually the case for production systems we assume that the failures are operation dependent [3,7]. Moreover, we assume that the times to failure and the times to repair are exponentially distributed. To analyze such systems, a decomposition method was proposed by Gershwin [11]. The computational efficiency of this method was later significantly improved by the introduction of the so-called DDX algorithm [5,6]. In general, this method provides fairly accurate results. There are however cases for which the accuracy of this decomposition method may not be so good. This is the case when the reliability parameters (average failure time and average repair time) of the different machines have different orders of magnitude. Such a situation may be encountered in real production lines. In [8] an improvement of Gershwin's original decomposition method has been proposed that in general provides more accurate results in the above mentioned situation. This other method is referred to as the GE-method. The basic difference between the GE-method with that of Gershwin is that it uses a two-moment approximation instead of a one-moment approximation of the repair time distributions of the equivalent machines. There are however still cases for which the accuracy of the GE-method is not as good as expected. This is the case for example when the buffer sizes are too small in comparison with the average repair time. We present in this paper a new decomposition method that is based on a better approximation of the repair time distributions. This method uses a three-moment approximation of the repair time distributions of the equivalent machines. Numerical results show that the new method is very robust in the sense that it seems to provide accurate results in all situations. Keywords: production lines, unreliable machines, finite buffers, decomposition method, hyper-exponential distributions

1

1. Introduction In this paper, we consider production lines consisting of a series of machines separated by finite buffers. The processing time of each machine is deterministic, i.e., a fixed amount of time is required to perform the operation. Moreover, we assume that all the machines have the same processing time, that is we restrict our attention to so-called homogeneous lines [6]. All machines are subject to failures. As is usually the case for production systems we assume that the failures are operation dependent [3,7]. This means that a machine can fail only while it is working. Moreover, we assume that the times to failure and the times to repair are exponentially distributed. Finally, we assume that there are always raw parts available at the input and that there is always room to accommodate the finished parts at the output. Models of production lines with deterministic processing times and exponentially distributed times to failure and times to repair are referred to as asynchronous models [7]. A number of methods have been developed for analyzing production lines with unreliable machines and finite buffers (also called transfer lines). See [7] for a survey and a list of references. Obtaining exact analytical solutions of asynchronous models of production lines is in general not feasible. As a result, different models have been used to approximate the behavior of asynchronous models [7]: the synchronous model [2] and the continuous flow model [17]. These models provide a good approximation of the original asynchronous model as long as the average times to failures are significantly larger than the processing times, which is usually the case in production systems [1]. For both models, exact solutions of a line consisting of two machines separated by a finite buffer can be obtained; see e.g. [3,13] in the case of the synchronous model and [9,11] in the case of the continuous flow model. The analysis of longer lines is based on approximation methods [7]. Among these methods, the decomposition method proposed by Gershwin [11] in the context of the synchronous model appears to be quite accurate. Moreover, using the iterative algorithm proposed in [5], this method can be made very efficient and reliable. A similar decomposition method was proposed in the case of the continuous flow model [6]. However, there are situations for which the accuracy of this decomposition method may not be so good. This is the case when the reliability parameters (average failure time and average repair time) of the different machines have different order of magnitudes. Such a situation may be encountered in real production lines. In [8] an improvement of Gershwin's original decomposition method was proposed that in general provides accurate results even in the above mentioned situation. This other method is referred to as the GE-method. The basic difference between the GE-method with that of Gershwin is that it uses a two-moment approximation instead of a one-moment approximation of the repair time distributions of the equivalent machines. The repair time distributions of the equivalent machines are approximated by generalized exponential (GE) distributions, which can easily be handled in the decomposition method without involving any additional complexity with respect to the exponential approximation used by Gershwin.[4,8]. Even though the GE-method is fairly robust, there are still situations for which the accuracy is not satisfactory. This is the case for example when the buffer sizes are too small in comparison with the average repair time. We present in this paper a new decomposition method that is based on a better approximation of the repair time distribution. This method is again an extension of Gershwin’s decomposition method. The main feature of the new method is that the repair time distributions of the equivalent machines are approximated by two-stage

2

Hyper-Exponential (HE) distributions. The HE-method uses a three-moment approximation of the repair time distributions. In this paper, we compare the performance results obtained by using the HE-method with those obtained by using a simulation. We also compare the accuracy of the new method with that of Gershwin's original method, referred to as the exponential method (E-method), as well as that of the GE-method proposed in [8]. It appears that the HE-method is very robust in terms of accuracy. The paper is organized as follows. The continuous flow model is presented in Section 2. The HE decomposition method is described in Section 3. The HE-DDX computational algorithm is given in Section 4. Finally, numerical examples are reported in Section 5. 2. The Continuous Flow Model We consider the continuous flow model of a production line consisting of a series of K machines (M1, M2, ..., MK) separated by K-1 intermediate buffers (B1, B2, ..., BK-1). Parts flow from outside the system to machine M1, then to buffer B1, then to machine M2, and so forth until they reach machine MK, after which they leave the system. We assume that there are always parts available at the input of the system and space available at the output of the system. The intermediate buffers are each of finite capacity (C1, C2, ..., CK-1). A four machine production line is shown in Figure 1. The quantity of material in each buffer Bi at any time is a real number hi(t), where 0 ≤ hi(t) ≤ Ci. Each machine can be in two states: operational (not in a failure condition) or down (under repair). When operational, it can be either working or idle. A machine is idle if it is starved or blocked. Machine Mi is starved at time t if one of the upstream machines is down and all buffers between this machine and machine Mi are empty. Machine Mi is blocked if one of the downstream machines is down and all the buffers in between this machine and machine Mi are full. A machine that is operational and neither starved nor blocked is working. When machine Mi is working, it transfers material from its upstream buffer, Bi-1, to its downstream buffer, Bi, at a constant rate U. That is a quantity of material Udt is transferred in time dt. Note that U=1/T, where T is the processing time of all the machines in the original asynchronous model. A machine may fail only while it is working. The time to failure and the time to repair of machine Mi are exponentially distributed with rates λi and ?i, respectively. Throughout the rest of the paper we assume that T = 1 and that, as a result U = 1. This is without loss of generality since the time unit can always be chosen so that this condition is satisfied. Let L denote the continuous flow model of the production line. Let us define the following performance parameters of the continuous model: ei: Isolated efficiency of machine Mi. ei = ?i = λi + ?i 1 λ 1+ i ?i

Ei: psi: pbi:

Efficiency of machine Mi; proportion of time machine Mi is working in line L. Probability of machine Mi being starved in line L. Probability of machine Mi being blocked in line L.

3

Since U = 1, Ei can equivalently be interpreted as the production rate of machine Mi in line L. The following relationships have been established in [6] for the continuous flow model of tandem production lines. E1 = E2 = ... = EK Ei = ei (1 - psi - pbi ) i = 1, ..., K (1) (2)

The first relation is related to conservation of flow. The second equation relates the efficiency of machine Mi in line L, Ei, to its efficiency when considered in isolation ei. It is an exact relationship in the case of the continuous flow model because a machine cannot be simultaneously starved and blocked [6]. M1 B1 M2 B2 M3 B3 M4

L
λ1 ?1 Mu(1) C1 B(1) λ2 ?2 Md(1) C2 λ3 ?3 C3 λ4 ?4

L(1)
λu(1) C1 ?u1(1), pu1(1) ?u2(1), pu2(1) λd(1) ?d1(1), pd1(1) ?d2(1), pd2(1) Mu(2) B(2) Md(2)

L(2)
λu(2) C2 ?u1(2), pu1(2) ?u2(2), pu2(2) λd(2) ?d1(2), pd1(2) ?d2(2), pd2(2) Mu(3) B(3) Md(3)

L(3)
λu(3) ?u1(3), pu1(3) ?u2(3), pu2(3) C3 λd(3) ?d1(3), pd1(3) ?d2(3), pd2(3)

Figure 1: A four-machine production line and its decomposition into three two-machine production lines.

4

3. Decomposition Method In this section we present the two-stage hyper-exponential decomposition method for the analysis of the continuous flow model. The principle of this method is to decompose the K-machine line into a set of K-1 two-machine lines L(i), for i = 1, ..., K1 (see Figure 1). Each line L(i) is a continuous flow model consisting of an upstream machine Mu(i), a downstream machine, Md(i), and an intermediate buffer, B(i). There is an infinite supply of material in front of machine Mu(i), i.e, Mu(i) is never starved, while there is an infinite amount of storage available at the output of machine Md(i), i.e, Md(i) is never blocked. Each system L(i) must be defined in such a way that the behavior of the material flow in buffer B(i) closely matches that of the material flow in buffer Bi of line L. Machine Mu(i) represents (in an aggregate way) the part of the line upstream of buffer Bi, while machine Md(i) represents (in an aggregate way) the part of the line downstream of buffer Bi (upstream and downstream refer to the direction of the flow of material). In other words, machine Mu(i) models how material is transferred into buffer Bi, while machine Md(i) models how material is transferred out of buffer Bi. To achieve the above goal, the equivalent machines Mu(i) and Md(i) of each line L(i) are characterized as follows. Both machines have the same processing rate as the machines of line L, that is U = 1. The capacity of buffer B(i) is the same as that of buffer Bi, that is Ci. The failure times of machine Mu(i) and Md(i) have exponential distributions with parameters λu(i) and λd(i), respectively. So far, this is totally similar to Gershwin’s approach. As stated in the introduction, the difference between the method proposed in this paper and that of Gershwin lies in the characterization of the repair time distributions. Let us recall that in Gershwin’s method, the repair time distributions of the equivalent machines are assumed to be exponential. In order to define the characterization of the repair time distributions, consider for instance the failure/repair mechanism of machine Mu(i). A failure of machine Mu(i) represents either a failure or a starvation of machine Mi. A starvation of machine Mi is a consequence of either a failure or a starvation of machine Mi-1. A starvation of machine Mi-1 is in turn a consequence of either a failure or a starvation of machine Mi-2, and so forth. Thus, a failure of Machine Mu(i) is caused either by a failure of machine Mi or by a failure of one of the upstream machines (Mi-1, ..., M1). As a result, the repair of Machine Mu(i) will be the consequence of a repair of machine Mi, in case machine Mi is down, or of a residual repair time of one of the upstream machines (Mi-1, ..., M1) at the instant of starvation, in case machine Mi is starved. Now, since the repair time of every machine j, j = i-1,..., 1, is exponentially distributed, its residual repair time is also exponentially distributed with the same rate ?j. Thus, we conclude that the repair time of machine Mu(i) should be characterized by an so-called hyper-exponential distribution (i.e., a probabilistic mixture of exponential distributions) consisting of i stages, with rates ?i, ?i-1,..., ?1, as shown in figure 2. Similarly, the repair time of machine Md(i) should be characterized by an hyper-exponential distribution consisting of K-i stages, with rates ?i+1, ?i+2,..., ?K.

5

?i

?i-1

?1 Figure 2: Illustration of the repair time distribution of Machine Mu(i). Before going any further, one important question arises pertaining to the analysis of each subsystem L(i). Indeed, in any decomposition method, the overall method relies on the analysis of each subsystem L(i). If this analysis is too complex, then the decomposition method may become too cumbersome and not suitable for solving large production lines. It turns out that this may be the case if we are directly using the above characterization. Indeed, the analysis of line L(i) would imply solving the continuous flow model of a two-machine subsystem with exponential failure time distributions and hyper-exponential repair time distributions with i and K-i stages for the upstream and downstream machines, respectively. This would involve solving a set of K-1 differential equations, which is very tedious, if not impossible [15]. To reduce the complexity, while retaining the idea of this new characterization, we propose to replace the characterization of the repair time distributions using hyperexponential distributions with arbitrary number of stages by a characterization using hyper-exponential distributions consisting of only two stages. The idea behind this simplification, is that an arbitrary hyper-exponential distribution can always be approximated by a two-stage hyper-exponential distribution having the same first three moments (see Appendix B). Now, it turns out with this characterization, the analysis of line L(i) implies solving the continuous flow model of a two-machine subsystem with exponential failure time distributions and two-stage hyper-exponential repair time distributions. This reduces to solving a set of 3 differential equations, which can easily be done (a brief discussion of the solution is given in Appendix A and details can be found in [16]). Thus, we assume that repair time distribution of machine Mu(i) is characterized by a two-stage hyper-exponential distribution with parameters (?u1(i), ?u2(i), pu1(i), pu2(i)) (see Figure 3). This means that, with a probability pu1(i) the repair time is exponentially distributed with rate ?u1(i), while with a probability pu2(i), it is exponentially distributed with rate ?u2(i), where pu1(i) and pu2(i) verify the following relationships: p u1 (i ) + p u 2 (i) = 1 (3)

6

Similarly, we assume that the repair time distribution of machine Md(i) is characterized by a two-stage hyper-exponential distribution with parameters (?d1(i), ?d2(i), pd1(i), pd2(i)). This means that, with a probability pd1(i) the repair time is exponentially distributed with rate ?d1(i), while with a probability pd2(i), it is exponentially distributed with rate ?d2(i), where pd1(i) and pd2(i) verify the following relationships: p d1 (i ) + p d 2 (i) = 1 ?u1(i) (4)

pu1(i)

pu2(i) ?u2(i) Figure 3: Illustration of the two-stage hyper-exponential approximation of the repair time distribution of machine Mu(i). It is then expected that using a three moment approximation of the repair time distributions of the equivalent machines will lead to a better accuracy of the decomposition method compared to previous methods: Gershwin’s method [6,11] that uses a first moment approximation of the repair time distributions and the GE-method [8] that uses a two moment approximation. In order to determine the unknown parameters λu(i), ?u1(i), ?u2(i), pu1(i), pu2(i), λd(i), ?d1(i), ?d2(i), pd1(i) and pd2(i), for each two-machine line L(i), i=1, ..., K-1, we need a set of 10(K-1) independent equations. Since pu1(i) and pu2(i) (respectively pd1(i) and pd2(i)) are related through equation (3) (respectively (4)), we actually only need an additional set of 8(K-1) independent equations. In the sequel of this section we derive these equations. Let us define the following quantities: e u (i) = 1 ? p (i) p (i) ? 1 + λ u (i )? u1 + u 2 ? ? ? u1 (i ) ? u 2 (i ) ? 1 ? p (i) p (i) ? 1 + λ d (i )? d1 + d 2 ? ? ? d1 (i ) ? d 2 (i ) ? i = 1, ..., K-1 (5)

e d (i) =

i = 1, ..., K-1

(6)

eu(i) and ed(i) represent the efficiencies of machines Mu(i) and Md(i) in isolation. For each line L(i), we define the following performance parameters:

7

E(i): Efficiency of line L(i). This is the proportion of time machine Md(i) is working. ps(i): Probability of machine Md(i) being starved in line L(i). pb(i): Probability of machine Mu(i) being blocked in line L(i). Again since U = 1, E(i) can equivalently be interpreted as the production rate of line L(i). These performance parameters are functions of the parameters of the upstream and downstream machines of L(i). We have the following relationships [7]: E(i ) = e u (i)(1 - p b (i )) E(i ) = e d (i )(1 - p s (i)) i = 1, ..., K-1 i = 1, ..., K-1 (7) (8)

From equation (1) and (2) and the above conditions the following set of equations can be derived (see [6,7] for details): E(1) = E(2) = = E(K - 1) E(i - 1) = e i (1 - p s (i - 1) - p b (i))

K

i = 2, ..., K-1

(9) (10)

Now using (7), (8) and (9), after some manipulation, (10) can be written as: 1 1 1 1 + = + e d (i ? 1) e u (i ) E(i ? 1) e i i = 2, ..., K-1 (11)

r r αu(i) p u 1 ( i ? 1) and αu(i) p u 2 ( i ? 1) corresponding respectively to the rates ?i, ?u1(i-1), and ?u2(i-1) respectively (see figure 4).

r r ?u2(i-1). Let p u 1 ( i ? 1) (respectively p u 2 ( i ? 1) ) be the probability that the repair time of Machine Mu(i-1) at the time of starvation of Machine Mi is exponentially distributed with rate ?u1(i-1) (respectively ?u2(i-1)). As a result, the repair time distribution of machine Mu(i) is a three-stage hyper-exponential distribution with probabilities 1-αu(i),

Consider again the failure/repair mechanism of machine Mu(i). As discussed above, a failure of machine Mu(i) represents either a failure or a starvation of machine Mi. A starvation of machine Mi is a consequence of either a failure or a starvation of machine Mi-1. In the decomposition, a failure or a starvation of machine Mi-1 is represented by a failure of machine Mu(i-1). Therefore, a failure of machine Mu(i) results from either a failure of machine Mi or a failure of machine Mu(i-1). Let αu(i) be the proportion of time the cause of the failure of machine Mu(i) is a failure of machine Mu(i-1). As a result, the repair time of machine Mu(i) is either the repair time of machine Mi, or the residual repair time of machine Mu(i-1) at the instant of starvation of machine Mi. Thus, the repair time distribution of machine Mu(i) is a probabilistic mixture of the residual repair time distribution of machine Mu(i-1) (with probability αu(i)) and of the repair time distribution of machine Mi (with probability 1-αu(i)). Since we assume that the repair time of Machine Mu(i-1) has a two-stage hyper-exponential distribution and because of using the memoryless property of exponential distributions, it follows that the repair time distribution of machine Mu(i-1) at the instant of starvation of Machine Mi is also a two-stage hyper-exponential distribution with rates ?u1(i-1) and

8

r αu(i) p u1 (i ? 1) ?u1(i-1)

pr u1 ( i ? 1) αu(i)

?u1(i-1) αu(i) p r u2 ( i ? 1) ?u2(i-1)

pr u2 ( i ? 1) ?u2(i-1)

1?αu(i)

?i

1?αu(i)

?i

Figure 4: Illustration of the construction of the repair time distribution of machine Mu(i). Let us now calculate the quantity αu(i). αu(i) is the ratio of the average number of failures (per unit of time) of machine Mu(i) which result from a failure of machine Mu(i-1) to the average number of failures (per unit of time) of machine Mu(i). Let 1) m( u ( i ) be the average repair time of machine Mu(i). Let Du(i) be the probability of machine Mu(i) being in a failure condition. Then, the average number of failures (per unit of time) occurring on machine Mu(i), which is equal to that of repairs, is equal to 1) D u (i) / m ( u ( i ) . On the other hand, the probability of machine Mu(i) being in a failure condition which is a consequence of a failure of machine Mu(i-1), is equal to ps(i-1). Let mr u ( i ? 1) be the average residual repair time of machine Mu(i-1) at the instant of starvation of machine Mu(i). Then, the average number of failures (per unit of time) of Mu(i) that result from a failure of machine Mu(i-1), which is equal to that of repairs, is equal to ps(i-1)/ m r u ( i ? 1) . As a result the quantity αu(i) is given by: α u (i) =
1) p s (i ? 1)m ( u (i) r D u ( i )m u (i ? 1)

i = 2, ..., K-1

(12)

The probability of machine Mu(i) being in failure condition, Du(i), can be expressed as (see Property 1 in the Appendix of [7]): ? 1 ? ? 1? E(i) D u (i) = ? ? e u (i) ?
1) By definition, the quantity m ( u ( i ) is given by: (1) 1) r m( u ( i) = α u (i )m u ( i ? 1) + (1 ? α u ( i ))m i

i = 1, ..., K-1

(13)

i = 2, ..., K-1

(14)

9

1 1) 1) where m ( the average repair time of machine Mi is given by m ( and i i = ? i mr u ( i ? 1) , the average residual repair time of machine Mu(i-1) at the instant of starvation is given by: mr u ( i ? 1) =
r pr u1 ( i ? 1) + p u 2 ( i ? 1) ? u1 (i ? 1) ? u 2 (i ? 1)

i = 2, ..., K-1

(15)

As a result, using (15), (14) can be written as:
r ? pr ? 1) u1 ( i ? 1) + p u 2 ( i ? 1) + 1 - α u ( i ) ( ) = ( ) m( i α i ? ? u u ? ( i ? 1 ) ? ( i ? 1 ) ?i ? ? u 1 u 2 ? ?

i = 1, ..., K-1 (16)

Using (13), (15), and (16), αu(i) can finally be expressed as: α u (i) = 1 ? ?? 1 ? ?? ? 1? E(i ? 1) ? r r ? ? e u (i) ? ? ? p u1 (i ? 1) p u 2 (i ? 1) ? ?i ? ? 1? ? + ? ? (i ? 1) ? (i ? 1) ? ? +1 p s (i ? 1) ? ? 1 2 u u ? ? ? ? ? ?

We have thus obtained a first representation of the repair time distribution of Mu(i) as a three-stage hyper-exponential distribution. However we have assumed a twostage hyper-exponential distribution as the characterization of this repair time distribution of machine Mu(i). In order to obtain this distribution, we approximate the three-stage HE distribution by a two-stage HE distribution, using a three moment approximation, as illustrated in Figure 5. As shown in Appendix B, for any three-stage HE distribution, there exists a two-stage HE distribution having the same first three moments.

10

αu(i) p r u1 ( i ? 1)

?u1(i-1) pu1(i) ?u1(i)

αu(i) p r u2 ( i ? 1)

?u2(i-1) pu2(i) ?i ?u2(i)

1?αu(i)

Figure 5: Illustration of the three moment approximation of the three-stage hyperexponential repair time distribution of machine Mu(i) by a two-stage HE-distribution.

1) (2) (3) Let m ( u ( i ) , m u ( i ) and m u ( i ) be the first, second and third moments of the original three-stage hyper-exponential distribution. They can be calculated using the following expressions: 1) m( u (i) = 2) m( u (i) = 3) m( u (i) = r r α u (i)p u 1 (i ? 1) + α u ( i ) p u 2 ( i ? 1) + 1 ? α u ( i ) ? u1 (i ? 1) ? u 2 (i ? 1) ?i r 2α u ( i ) p u 1 (i ? 1)

? u1 (i ? 1) 2

+ +

r 2α u ( i ) p u 2 ( i ? 1)

? u 2 (i ? 1) 2

+ +

2(1 ? α u (i )) ?i2 6(1 ? α u (i)) ?i3

r 6α u ( i ) p u 1 ( i ? 1)

? u1 (i ? 1) 3

r 6α u (i)p u 2 ( i ? 1)

? u 2 (i ? 1) 3

From the three first moments of the three-stage hyper-exponential distribution we can derive the parameters, p u1 (i ) , p u2 (i ) , ? u1 (i) and ? u2 (i ) of the two-stage hyper-exponential distribution by means of the equations given in Appendix B. A totally similar analysis of the failure-repair mechanism of Machine Md(i) can be developed. First the repair time distribution of machine Md(i) can be represented as a three-stage hyper-exponential distribution (see figure 5). The quantity α d (i) denotes the proportion of time a failure of machine Md(i) is caused by a failure of machine Md(i+1). It can be expressed as: α d (i ) =
1) p b (i + 1)m ( d (i) r D d ( i )m d (i + 1)

11

Following derivations similar to those used for α u (i) , α d (i) can finally be expressed as: 1 α d (i) = ?? 1 ? ? ?? ? 1? E(i + 1) ? r r ? ? e d (i) ? ? ? p d1 (i + 1) p d 2 (i + 1) ? ? ? ? i +1 ? ? 1? ? + ? +1 p b (i + 1) ? ( i + ) ? ( i + ) 1 1 ? ? d d 1 2 ? ? ? ? ? ? Finally, there are boundary conditions: λu(1) = λ1; ?u1(1) = ?1; ?u2(1) = ?1; pu1(1) = 1; pu2(1) = 0; (17) λd(K-1) = λK; ?d1(K-1) = ?K; ?d2(K-1) = ?K; pd1(K-1)= 1; pd2(K-1)= 0; (18) These boundary conditions simply express the fact that machine Mu(i) should be exactly identical to machine M1, while machine Md(K-1) should be exactly identical to machine M K.

4. Computational Algorithm In this section, we propose a general algorithm to determine the unknown parameters of the decomposition method, which is the generalization of the DDX algorithm [5,6]. First of all, it is important to recognize that it is possible to obtain the exact analysis of a two-machine production line model with failure and repair time distributions characterized by exponential and two-stage HE distributions, respectively (a brief discussion of the solution is given in Appendix A and details can be found in [16]). This implies that for given values of the parameters λu(i), ?u1(i), ?u2(i), pu1(i), pu2(i), λd(i), ?d1(i), pd1(i) and pd2(i) of line L(i), the parameters of interest, E(i), ps(i),

r r r pb(i), p r u1 (i ) , p u 2 ( i ) , p d1 ( i ) and p d 2 ( i) can easily be derived. With equations derived in section 3, the parameters of the upstream machine Mu(i) of line L(i) can be obtained from the performance parameters of line L(i-1). Similarly, the parameters of the downstream machine of line L(i) can be obtained from the performance parameters of line L(i+1).

In order to obtain the final computational algorithm, let us transform the original set of equations. After some manipulation, the 2(K-2) equations given by (9) and (11) can be equivalently transformed into the following equations (see [8]): 1 1 1 1 = + ? e u (i ) E(i ? 1) e i e d (i ? 1) 1 1 1 1 = + ? e d (i) E(i + 1) e i +1 e u (i + 1) i = 2, ..., K-1 (19)

i = 1, ..., K-2

(20)

12

The following iterative algorithm can be used to determine the unknown parameters of the upstream and downstream machines of all the lines L(i), i=1, ..., K-1. As all DDX-type algorithms, it consists of a forward path (step 2) that calculate updated estimates of the parameters of the upstream machines, and a backward path (step 3) that calculate updated estimates of the parameters of the downstream machines. Algorithm Step 1. Set: λu(1) = λ1; ?u1(1) = ?1; ?u2(1) = ?1; pu1(1) = 1; pu2(1) = 0; λd(K-1) = λK; ?d1(K-1) = ?K; ?d2(K-1) = ?K; pd1(K-1) = 1; pd2(K-1) = 0; Initialize i = 1, ..., K-2 λd(i) = λi+1; ?d1(i) = ?i+1; ?d2(i) = ?i+1; pd1(i) = 1; pd2(i) = 0; Step 2. For i=2, 3,..., K-1:
r r Analyse line L(i-1) and calculate E(i-1), p s (i ? 1) , p u 1 ( i ? 1) , and p u 2 ( i ? 1)

1 1 1 1 = + ? e u (i ) E(i ? 1) e i e d (i ? 1) α u (i) = 1 ? ?? 1 ? ?? ? 1? E(i ? 1) ? r r ? ? e u (i) ? ? ? p u1 (i ? 1) p u 2 (i ? 1) ? ?i ? ? 1? ? + ? ? (i ? 1) ? (i ? 1) ? ? +1 p s (i ? 1) ? ? 1 2 u u ? ? ? ? ? ?
r r α u (i)p u 1 (i ? 1) + α u ( i ) p u 2 ( i ? 1) + 1 ? α u ( i ) ? u1 (i ? 1) ? u 2 (i ? 1) ?i r 2α u ( i ) p u 1 (i ? 1)

1) m( u (i) = 2) m( u (i) = 3) m( u (i) =

? u1 (i ? 1) 2

+ +

r 2α u ( i ) p u 2 ( i ? 1)

? u 2 (i ? 1) 2

+ +

2(1 ? α u (i )) ?i2 6(1 ? α u (i)) ?i3

r 6α u ( i ) p u 1 ( i ? 1)

? u1 (i ? 1) 3

r 6α u (i)p u 2 ( i ? 1)

? u 2 (i ? 1) 3

Calculate the HE parameters (?u1(i), ?u2(i), pu1(i), pu2(i)) of the repair time distribution of Mu(i) (using the formulas in given Appendix B) ? 1 ? ? 1? ? ? e u (i) ? λ u (i) = p u1 (i ) p u 2 (i ) + ? u1 (i) ? u 2 (i )

13

Step 3. For i = K-2, K-3,..., 1:
r r Analyse line L(i+1) and calculate E(i+1), p b (i + 1) , p d1 (i + 1) , and p d 2 ( i + 1)

1 1 1 1 = + ? e d (i) E(i + 1) e i +1 e u (i + 1) α d (i) = 1 ?? 1 ? ? ?? ? 1? E(i + 1) ? r r ? ? e d (i) ? ? ? p d1 (i + 1) p d 2 (i + 1) ? ? i +1 ? ? 1? ? + ? ? (i + 1) ? (i + 1) ? ? +1 p b (i + 1) ? ? d d 1 2 ? ? ? ? ? ?
r r (i + 1) α d (i )p d α d (i)p d 1 2 ( i + 1) + 1 ? α d ( i) = + ? d1 (i + 1) ? d 2 (i + 1) ? i +1 r 2α d ( i ) p d 1 ( i + 1)

1) m( d (i)

2) m( d (i) = 3) m( d (i) =

? d1 (i + 1) 2

+ +

r 2α d ( i ) p d 2 ( i + 1)

? d 2 (i + 1) 2

+ +

2(1 ? α d (i)) ? i + 12 6(1 ? α d (i )) ? i + 13

r 6α d ( i ) p d 1 ( i + 1)

? d1 (i + 1) 3

r 6α d ( i ) p d 2 ( i + 1)

? d 2 (i + 1) 3

Calculate the HE parameters (?d1(i), ?d2(i), pd1(i), pd2(i)) of the repair time distribution of Md(i) (using the formulas in given Appendix B) ? 1 ? ? 1? ? ? e d (i) ? λ d (i) = p d1 (i ) p d 2 (i ) + ? d1 (i) ? d 2 (i ) Step 4. Go to Step 2 until convergence of the unknown parameters (λu(i), ?u1(i), ?u2(i), pu1(i), pu2(i), λd(i), ?d1(i), ?d2(i), pd1(i) and pd2(i)), i=1, ..., K-1

14

5. Numerical Experiments In this section, we present two examples that illustrate the behavior of the new decomposition method. For each example, we provide the results obtained using the original decomposition method with exponential approximations of the repair time distributions as described in [6], referred to as the E-method, the method presented in [8] with general exponential approximations of the repair time distributions, referred to as the GE-method, and the new method presented in this paper, referred to as the HEmethod. For each example the convergence parameter is set to 1.10-7. This means that we stop the algorithm if the relative difference of each parameter (λu(i), ?u1(i), ?u2(i), pu1(i), pu2(i), λd(i), ?d1(i), pd1(i) and pd2(i), i = 1, ..., K-1) between two iterations of the algorithm is less than 1.10-7. The three different algorithms are computationally very efficient and give the results almost instantaneously on a Pentium100 machine (see table 5 for a comparison of the time required to achieve convergence for each algorithm). We compare these results with simulation results of the continuous flow model of the original production lines. We ran long enough simulations so that the outcome of these simulations can be used as a reference to compare the three decomposition methods as can be seen from the corresponding confidence intervals. For each example, we provide the production rate of the line as well as the average buffer levels. We also provide the relative error of each decomposition method with respect to the simulation results. In all examples, the common speed of the machines is U=1. The first example (Example 1) pertains to a line consisting of 10 machines. The parameters are given in table 1. This example, although not coming directly from an industrial case, is however representative of production lines that are encountered in industry. The isolated efficiencies of the machines range from 0.870 to 0.952. The average times to repair are fairly different from one machine to the other (ratio of 1 to 10). We consider three different sets of buffer capacities, referred to as A, B, and C. The buffer capacities of example 1-B are twice those of example 1-A, and the buffer capacities of example 1-C are twice those of example 1-B. The results obtained using the E-method, the GE-method and the HE-method are given in table 2. The main performance parameter of interest is the production rate of the line, which can be interpreted as the production capacity of the system. For the three configurations, it appears that the production rates obtained using the GE-method or the HE-method are significantly more accurate than those obtained using the E-method. Indeed, the errors of the GE-method ant the HE-method are of the order of 1%, whereas the error of the Emethod can be close to 10% (see example 1-A). The significant errors encountered with the E-method is due to the fact that the exponential approximation of the repair time is a poor approximation of the actual repair time distributions in situations where the average repair time of the machines are very different, which is the case in example 1. For the three configurations, the average error of the GE-method is 0.73%, and the average error of the HE-method is 0.67%, whereas the average error of the E-method is 5.14%. On the other hand, the results pertaining to the buffer levels are not as significantly different. Nevertheless, it appears that the HE-method does slightly better than the GE-method, which in turns does slightly better than the E-method. Indeed, the average error of the HE-method is 5.9%, whereas that of the GE-method is 7.8% and that of the E-method is 12.4%. The second example (Example 2) is derived from example 1 as follows. The average time to failure (respectively time to repair) of machines 2, 4, 6, 8 and 10 are

15

mutliplied by 2 (respectively 4) with respect to the parameters of the first example. The other machines are unchanged. The isolated efficiencies of the machines now range from 0.769 to 0.952. The average times to repair are now significantly different from one machine to the other (ratio of 1 to 40). We consider the same three different sets of buffer capacities, referred to as A, B, and C. . The parameters are given in table 3. The results obtained using the E-method, the GE-method and the HE-method are given in table 4. Let us first discuss the results pertaining to the production rate. As expected, the results obtained using the E-method are fairly poor. Indeed, the error is larger than 10% for the three configurations. Now, it appears that for this example, the GE-method also leads to some significant errors, in particular when the buffer sizes are small (the error is close to 5% for configuration 2-A). On the other hand, the HE-method is still fairly robust since the largest error is less than 2%. For the three configurations, the average error of the GE-method is 2.8%, whereas the average error of the HE-method is 1.30% and the average error of the E-method is 13.43%. For the average buffer levels, the superiority of the HE-method over the other two methods becomes clearer. Indeed, the average (respectively maximum) error of the HE-method is 5.9%, (respectively 17.84%) whereas that of the GE-method is 9.9% (respectively 28.43) and that of the E-method is 18.1% (respectively 39.93). The conclusions drawn by means of these two examples were actually confirmed by the results obtained with many other examples we tested.(see [15] for other examples) These conclusions can be summarized as follows. The E-method can lead to large errors in the estimation of the production rate in situations where the average repair times of the different machines have different orders of magnitudes. In such cases, the GE-method does provide good results, expect when the buffer sizes are too small, in which case it can also lead to significant errors. On the other hand the HEmethod appears to be very robust in the sense that regarles of the parameters of the production line (reliability parameters of the machines and sizes of the buffers), it always provide reasonnably accurate results. Let us briefly discuss the convergence and computational complexity of the new algorithm, referred to as the HE-DDX algorithm, and compare them with those of GEDDX algorithm, derived for the GE-method, and the E-DDX algorithm derived for the E-method. We tested many examples with quite different parameters and on all these examples, the GE-DDX and HE-DDX algorithms always converged. The time to achieve convergence of the GE-DDX algorithm is very similar to the convergence time of the original E-DDX algorithm, whereas the convergence time of the HE-DDX algorithm can be ten times larger (see table 5). This is due to the fact that the analysis of each two-machine production line requires significantly more time in case the repair time distribution of the equivalent machines is characterized by HE-distributions. However, it should be noticed that even the HE-DDX algorithm is very fast (convergence is always reached in less than one second for production lines with a number of machines of the order of 10).

16

6. Conclusion
In this paper, we proposed an improvement of Gershwin's original decomposition method that provides accurate results in situations where the GE-method and the original E-method can lead to significant errors. This is the case when the reliability parameters (average failure time and average repair time) of the different machines have different orders of magnitude and the buffer capacities are small. Such a situation may be encountered in real production lines. The basic difference between the decomposition method presented in this paper with that of Gershwin and that presented in [8] is that the times to repair of the equivalent machines are modeled as two-stage hyper-exponential distribution instead of generalized exponential or exponential distributions. This allows us to use a three-moment approximation instead of a twomoment approximation or a one-moment approximation of the repair time distributions of these equivalent machines. Our results show that the HE-method is very robust in terms of accuracy, while still being fast enough to be used in an interactive way.

References [1] R. Alvarez, Y. Dallery and R. David, "A study of the continuous flow model of production lines with unreliable machines and finite buffers", Journal of Manufacturing Systems, Volume 13/No. 3, pp. 221-234. J. A. Buzacott, "Automatic transfer lines with buffer stocks", Int. J. Prod. Res., Vol. 5, N°3, pp. 182-200, 1967. J.A. Buzacott and L.E. Hanifin, "Models of automatic transfer lines with inventory banks: a review and comparison", AIIE Transactions, Vol. 10, N°2, pp. 197-207, 1978. Y. Dallery, "On modeling failure and repair times in stochastic models of manufacturing systems using generalized exponential distributions", Queuing Systems (Theory and Application) Vol. 15, pp. 199-209, 1994. Y. Dallery, R. David and X.L. Xie, "An efficient algorithm for analysis of transfer lines with unreliable machines and finite buffers", IIE Transactions, Vol. 20, pp. 280-283, 1988. Y. Dallery, R. David and X.-L. Xie, "Approximate analysis of transfer lines with unreliable machines and finite buffers", IEEE Transactions on Automatic Control, Vol. 34, N°9, pp. 943-953, September 1989. Y. Dallery and S.B. Gershwin, "Manufacturing flow line systems: a review of models and analytical results", Queuing Systems Theory and Applications, Vol. 12, pp. 3-94, 1992.

[2] [3]

[4]

[5]

[6]

[7]

17

[8]

Y. Dallery and H. Le Bihan, "An improved decomposition method for the analysis of production lines with unreliable machines and finite buffers", INRIA/IEEE, (ETFA'95), Paris, France, October 1995. D. Dubois and J.-P. Forestier, "Productivité et en-cours moyens d'un ensemble de deux machines séparées par une z?ne de stockage", RAIRO Automatique, Vol. 16, N°2, pp. 105-132, 1982. Y. Frein, C. Commault and Y. Dallery, "Modeling and analysis of closed-loop production lines with unreliable machines and finite buffers, IIE Transactions 28, 545-554, 1996 S.B. Gershwin, "An efficient decomposition method for the approximate evaluation of tandem queues with finite storage space and blocking", Operations Research, Vol. 35, N°2, pp. 291-305, March-April 1987. S.B. Gershwin and I.C. Schick, "Continuous model of an unreliable two-stage material flow system with a finite interstage buffer", Tech. Rep. LIDS-R-1039, Massachusetts Institute of Technology, 1980. S.B. Gershwin and I.C. Schick, "Modelling and analysis of three-stage transfer lines with unreliable machines and finite buffers", Operations Research, Vol. 31, n°2, pp. 354-380, 1983. D.D Kouvatsos, Maximum entropy and the G/G/1/N queue, Acta Informatica 23, pp. 545-565, 1986. H. Le Bihan, De nouvelles méthodes analytique pour l'évaluation de performances de lignes de production, PhD Thesis, Université Pierre et Marie Curie, in preparation. H. Le Bihan and Y. Dallery, Analysis of the continuous flow model of a twomachine production line with exponential failure time and hyper-exponential repair time distribution, Technical report LIP6, in preparation. B. Zimmern, "Etude de la propagation des arrêts aléatoires dans les cha?nes de production", Revue de Statistique Appliquées, Vol. 4, pp. 85-104, 1956.

[9]

[10]

[11]

[12]

[13]

[14] [15]

[16]

[17]

18

Appendix A : Analysis of the continuous flow model of a two-machine production line with exponential failure time and two-stage hyper-exponential repair time distributions In this appendix, we briefly show the analysis of the continuous flow model of a twomachine production line with exponential failure time and two-stage hyper-exponential repair time distributions. Details pertaining to the analysis and the formulas for the performance parameters can be found in [16]. Consider the continuous flow model of a two-machine production line with a finite storage buffer. Each machine can fail. Let i = 1,2 denote the number of the machine in the production line (i=1 for the upstream machine and i=2 for the downstream machine). The time to failure of machine i is exponentially distributed with rate λi (i = 1,2). The distribution of the repair time of machine i is a two-stage hyper-exponential distribution with parameters ?i1, ?i2, pi1 and pi2. Let C be the finite capacity of the buffer. Let U be the constant transfer rate of all the machines of the line. Let x be the quantity of material in the buffer and αi (i=0, 1, 2) be a variable indicating whether machine i is operational (αi=0), under repair by the stage 1 (αi=1) of the hyper-exponential distribution of the repair times, or under repair by the stage 2 (αi=2). Let f α 1 , α 2 ( x) be the steady-state probability density of the internal states (α1, α2, x) where 0 < x < C. Let Pα 1 , α 2 (0) be the steady-state probabilities of the boundary states where x = 0. Let Pα 1 , α 2 (C) be the steady-state probabilities of the boundary states where x = C. Internal equations of the steady-state probability density We define internal states as states (α1, α2, x) where 0 < x < C. All other states are boundary states. Internal equations are the balance equations that do not include any boundary states. The rest are called boundary equations. p11λ 1f 01 (x) + p 21λ 2 f10 (x) ? (?11 + ? 21 )f11 (x) = 0 p12 λ 1f01 (x ) + p 21λ 2 f20 (x ) ? (?12 + ? 21 )f21 ( x) = 0 p11λ 1f 02 (x ) + p 22 λ 2 f10 (x ) ? (?11 + ? 22 )f12 ( x) = 0 p12 λ 1f02 ( x) + p 22 λ 2 f20 ( x) ? (?12 + ? 22 )f22 ( x) = 0 ?U ?U ? f10 ( x) = p11λ 1f 00 ( x ) + ? 22 f12 ( x) + ? 21f11 (x ) - (?11 + λ 2 )f10 ( x) ? x ? f20 (x ) = p12 λ 1f00 ( x) + ? 22 f22 (x ) + ? 21f21 (x ) - (?12 + λ 2 )f20 ( x) ? x (A1) (A2) (A3) (A4) (A5)

(A6)

19

U

? f01 ( x ) = ?12 f21 (x ) + ?11f11 ( x) + p 21λ 2 f 00 (x ) - (? 21 + λ 1 )f20 ( x) ? x ? f02 ( x) = ?12 f22 (x ) + ?11f12 ( x) + p 22 λ 2 f00 ( x) - (? 22 + λ 1 )f 02 ( x) ? x

(A7)

U

(A8) (A9)

?11 f10 ( x) + ?12 f20 ( x) + ? 21 f01 (x ) + ? 22 f 02 (x ) - (λ 2 + λ 1 )f00 (x ) = 0 Boundary equations of the steady-state probability ? 21P01 (C) = p 21λ 2 P00 (C) + f 01 (C) ? 22 P02 (C) = p 22 λ 2 P00 (C) + f 02 (C) (λ 1 + λ 2 )P00 (C) = ? 21P01 (C) + ? 22 P02 (C) ?11P10 (0) = p11λ 1P00 (0) + f10 (0 ) ?12 P20 (0) = p12 λ 1P00 (0 ) + f20 (0) (λ 1 + λ 2 )P00 (0 ) = ?11P10 (0) + ?12 P20 (0) P01 (0) = P02 (0 ) = P10 (C) = P20 (C) = 0 P11 (0) = P12 (0) = P21 (0) = P22 (0) = 0 P11 (C) = P12 (C) = P21 (C) = P22 (C) = 0 f10 (C) = p11λ 1P00 (C) f20 (C) = p12 λ 1P00 (C) f01 (0 ) = p 21λ 2 P00 (0) f02 (0) = p 22 λ 2 P00 (0) Analysis of internal equations By summing all the internal equations, we obtain the following relationship: ? f 01 (x ) ? f02 ( x) ? f10 (x ) ? f20 ( x ) + = + ?x ?x ?x ?x which implies that:

(A10) (A11) (A12) (A13) (A14) (A15) (A16) (A17) (A18) (A19) (A20) (A21) (A22)

20

f01 ( x) + f02 ( x) = f10 (x) + f20 (x) + K By using the boundary equations, we can find that K is equal to zero. As a result, the previous equation can be written as: f01 ( x) + f02 ( x) = f10 ( x) + f20 (x) (A23)

By using equations (A1), (A2), (A3), (A4), (A9) and (A23), equations (A5), (A7), and (A8) can be written as: U ?f10 (x) ? p λ p λ ? p λ ? ? = ? λ 2 + ?11 + 11 1 (?12 ? ?11 ) ? 22 2 22 ? 21 2 21 ? f10 (x) ?x λ1 + λ 2 ?11 + ? 22 ?11 + ? 21 ? ? ? ? + ? 21 ? 21 ? - p11λ 1 ? 12 + ? f 01 (x) ?11 + ? 21 ? ? λ1 + λ 2 ? ? + ? 22 ? 22 ? - p11λ 1 ? 12 + ? f02 ( x) ?11 + ? 22 ? ? λ1 + λ 2 U ? ? + ?12 ?f01 ( x) ?11 ?12 ? = p 21λ 2 ? 11 + ? ? f10 (x) ?x ?11 + ? 21 ?12 + ? 21 ? ? λ1 + λ 2 ? p λ ? p λ ? p λ (? + ? 21 ) p 21λ 2 ?12 ? + ? ? λ 1 ? ? 21 + 12 1 12 + 11 1 11 + 21 2 12 + ? f 01 (x) ?12 + ? 21 ?11 + ? 21 λ1 + λ 2 ?12 + ? 21 ? ? ? ? + ? 22 ?12 ? + p 21λ 2 ? 12 + ? f 02 ( x) ?12 + ? 21 ? ? λ1 + λ 2 U ? ? + ?12 ? ?f02 (x) ?11 ?12 = p 22 λ 2 ? 11 + ? ? f10 ( x) ?x ?11 + ? 22 ?12 + ? 22 ? ? λ1 + λ 2 ? ? + ? 21 ? ?12 + + p 22 λ 2 ? 12 ? f01 ( x) ?12 + ? 22 ? ? λ1 + λ 2 ? p λ ? p λ ? p λ (? + ? 22 ) + ? ? λ 1 ? ? 22 + 12 1 12 + 11 1 11 + 22 2 12 + ?12 + ? 22 ?11 + ? 22 λ1 + λ 2 ? p 22 λ 2 ?12 ? ? f 02 (x) ?12 + ? 22 ?

The solutions of the previous system is given by the following equations: f10 (x ) = C1x1e R 1 x + C 2 x 2 e R 2 x + C 3 x 3 e R 3 x f01 ( x) = C1y1e R 1 x + C 2 y 2 e R 2 x + C 3 y 3 e R 3 x f02 ( x) = C1z1e R 1 x + C 2 z 2 e R 2 x + C 3 z 3 e R 3 x

21

By using the boundary and internal equations and the following normalization equation,
α1 = 0 α 2 = 0

? ∫ fα α ∑ ∑ ? ? 0
C
1

2

2

2

? =1, we can derive the values of the ( x)dx + Pα 1α 2 ( C) + Pα 1α 2 ( 0)? ?

following parameters: xi, yi, zi, Ri, Ci (i=1,2,3). From these parameters we can derive the steady-state probability densities of the internal states as well as the steady-state probabilities of the boundary states. Let E be the efficiency of the original line. E is given by the following relationship: E= ? ∫ fα ∑ ? ? 0
C 2

α1 = 0

10

? ( x)dx + Pα 1 0 ( C) + Pα 1 0 ( 0)? ?

The average buffer level Q is given by: Q= ? ∫ xfα α ∑ ∑ ? ? 0
C
1

2

2

α1 = 0 α 2 = 0

2

? ( x)dx + CPα 1α 2 ( C)? ?

The probability of blocking and starvation can easily be obtained using : ps = 1 ? E E and p b = 1 ? e2 e1

r Let p11 be the probability that the residual repair times of the first machine are r exponentially distributed with rate ?11 and p12 be the probability that the residual repair times of the first machine are exponentially distributed with rate ?12. These two probabilities are given by :

p10 (0)?11 p10 (0 )?11 + p 20 (0)?12 p 20 (0 )?12 r = p12 p10 (0)?11 + p 20 (0)?12
r = p11

r Similarly p 21 , the probability that the residual repair times of the second machine are r exponentially distributed with rate ?21 and p 22 , the probability that the residual repair times of the second machine are exponentially distributed with rate ?22 are given by the two following relationships:

p 01 (0)? 21 p 01 (0 )? 21 + p 02 (0 )? 22 p 02 (0)? 22 r = p 22 p 01 (0)? 21 + p 02 (0)? 22
r = p 21

22

Appendix B: Three-moment approximation of an arbitrary hyper-exponential distribution by a two-stage hyper-exponential distribution. We search the parameters of a two-stage hyper-exponential distribution such that the three first moments of this distribution are equal to those of a given hyperexponential distribution with an arbitrary number of stages. Let m (1) , m ( 2) and m ( 3) be the first, the second and the third first moment respectively of this distribution. Let p1, p2, ?1 and ?2 be the four parameters of the twostage hyper-exponential distribution where p1 (respectively p2) is the probability that the distribution of the repair times is exponential with rate ?1 (respectively ?2). The relationships between the four parameters of the two-stage hyper-exponential distribution and the three first moments of the arbitrary hyper-exponential distribution are given by the following equations: p1 p 2 + = m (1) ?1 ? 2 2 p1 2 p 2 + 2 = m (2) 2 ?1 ?2 6p 1 ? 13 + 6p 2 ?2
3

= m ( 3)

where p1 + p 2 = 1 Let D and ? D be defined as following:
3 m ( 3) ? m (1) 6 ?3 D= ? m( 2) ? 3 m (1) ? ? 1? ? ? 2 ( 1 ) ? 2m ?

?D = 1?

1 D2 ? m ( 2) ? 4? ? 1? ? ? 2 ? 2 m (1) ? +1

Considerable manipulation is required to show that the parameters p1, p2, ?1 and ?2 are given by the following relationships (details can be found in [13]):

23

p1 = p2 =

1+ ?D 2 1? ?D 2

if D ≥ 0 ? 1 = m (1) ? ?1 ? ?1 ? p2 p1 ? m(2) ?? ? ? 1? ? ? ?? 2 ? 2 m (1) ??

? ?? p1 ? m(2) 1 ? (1) ? ? = m ?1 + ? 1? ? ? 2 ?2 p2 ? ? 2 m (1) ?? ? if D < 0 ? 1 (1) ? = m ?1 + ?1 ? p2 p1 ? m ( 2) ?? ? ? 1? ? ? ?? 2 ? 2 m (1) ??

? ?? p1 ? 1 m ( 2) (1) ? ? = m ?1 ? ? 1? ? ?? 2 ?2 p2 ? ? 2 m (1) ?? ? It can be shown that there always exists a two-stage hyper-exponential distribution such that its first three moments match those of a given arbitrary hyperexponential distribution. Indeed, the parameters of the two-stage hyper-exponential distribution must satisfy the two following relationships : ? m (2) ? ? p1 ∈[0,1] and p 2 ∈[0,1] ? ? ? 2 > 0 ? Cv 2 > 1 ? ? 2 ? 2 m (1) ? m (2) m (3) 1 1 ≥ 0 and ≥0? ≤ ?1 ?2 6 4 m (1) The first relationship is always true in the case of hyper-exponential distributions. To verify the second relationship we define the third first moment of a n-stage hyperexponential distribution as:
n p m (1) = ∑ i ? 1 i 2

(B1)

24

n p m (2) = ∑ i2 2 1 ?i n p m ( 3) = ∑ i3 6 1 ?i

(B2)

(B3)

Using (B1) and (B3) we can written:
n n n 2 ? 1 1 ? m (1) m (3) ? + ∑ pi = ∑ ∑ pi p j ? + 3? 4 ? ? 3? 6 ? i j ? i ? j ? i =1 ? i i =1 j > i

(B4)

Similarly using (B2) we can written:
2 n n ? 2 ? n p2 m (2) ?+∑ i = ∑ ∑ pip j ? 2 2 4 ? ? 4 ? ? i ? j ? i =1 ? i i =1 j > i

(B5)

By using equations (B4) and (B5), (B6) is given by:
2 n n n n ? 1 ? 2 ? m (1) m (3) m ( 2 ) 1 ? ? ? ? ? ? = ∑ ∑ pi p j ? 3 + ? p p ∑ ∑ i j ? 2 2 ? (B6) 3? 6 4 ? ? ? ? ? ? ? i j ? i j ? i j ? i =1 j > i i =1 j > i

Equation given by (B6) can be equivalently transformed into the following relationship:
2 n n p p ? ? m (1) m (3) m ( 2 ) i j ? 1 ? 1 ? ≥0 ? = ∑∑ 6 4 ? ? ? 2 ? j2 ? ? i =1 j > i i j ? ? i 2

which implies:

m (2)

2

< 4 m (1)

m (3) 6

25

1 1/λi 1/?i ei 1-A 1-B 1-C Ci Ci Ci 50 5 0.909 25 50 100

2 400 60 0.870 30 60 120

3 150 10 0.938 10 20 40

4 200 15 0.930 15 30 30

5 400 40 0.909 15 30 60

6 100 5 0.95 25 50 100

7 500 40 0.926 35 70 140

8 600 60 0.909 25 50 100

9 100 5 0.952 30 60 120

10 800 60 0.930

Table 1: Data for Example 1
X 1-A simulation +/E-method error(%) GE-method error(%) HE-method error(%) 1-B simulation +/E-method error(%) GE-method error(%) HE-method error(%) 1-C simulation +/E-method error(%) GE-method error(%) HE-method error(%) Q1 Q2 Q3 5.6098 0.0124 5.2796 -5.89 6.1467 +9.57 5,5658 -0,78 Q4 6.6129 0.0209 6.5738 -0.59 6.9562 +5.19 6,4954 -1,78 Q5 6.2670 0.0217 6.5539 +4.58 5.4191 -13.53 6,1183 -2,37 Q6 Q7 Q8 6.6884 0.027 7.2413 +8.27 5.6560 -15.44 6,4318 -3,84 Q9 4.6173 0.0294 3.8152 -17.37 4.0028 -13.31 4,0185 -12,97

0.7257 17.2846 20.4284 0.0008 0.027 0.0381

8.2159 10.3845 0.0494 8.0139 -2.46 7.6964 -6.32 7,4102 -9,81 0.0629 9.3169 -10.28 9.4754 -8.75 9,0655 -12,70

0.7880 16.5771 18.3125 +8.58 -4.09 -10.36

0.7230 17.0377 21.1790 -0.37 -1.43 +3.67

0,7308 17,0754 20,7937 +0,70 -1,21 +1,79

0.7919 34.2268 36.9555 10.9399 13.0374 11.2069 17.5750 22.3478 12.5643 11.6938 0.0001 0.0077 0.0013 0.0034 0.0061 0.0060 0.0113 0.0171 0.0093 0.0109 9.8993 -15.35

0.8227 31.2972 31.2859 +3.89 -8.56 -15.34

9.6343 11.8810 11.2543 13.8858 18.8962 12.7172 -11.93 -8.87 +0.42 -20.99 -15.44 +1.22

0.7854 33.1647 38.3790 11.5549 12.7199 10.0923 15.2029 19.7857 12.3587 10.4235 -0.82 -3.10 +3.85 +5.62 -2.44 -9.95 -13.50 -11.46 -1.64 -10.86

0,792 33,2458 37,6359 +0,01 -2,87 +1,84

10,605 12,0645 10,9034 15,8459 -3,06 -7,46 -2,71 -9,84

20,259 12,3961 10,6108 -9,35 -1,34 -9,26

0.8268 66.8602 60.8391 21.1887 26.2214 18.4280 36.2305 47.4257 21.6445 28.0408 0.0001 0.0421 0.0948 0.0212 0.0435 0.0427 0.0842 0.1383 0.0546 0.0854

0.8512 58.2908 43.1900 17.1383 20.9367 15.5488 28.2921 39.9943 17.3256 22.8954 +2.95 -12.82 -29.01 -19.12 -20.15 -15.62 -21.91 -15.67 -19.95 -18.35

0.8350 62.9057 61.0857 20.7649 22.8121 17.1868 30.1355 41.6920 22.7045 25.4899 +0.99 -5.91 +0.41 -2.00 -13.00 -6.74 -16.82 -12.09 +4.90 -9.10

0,8374 62,5861 59,1195 19,8889 23,0857 17,1141 31,9574 43,9566 21,1452 25,7703 +1,28 -6,39 -2,83 -6,13 -11,96 -7,13 -11,79 -7,31 -2,31 -8,10

Table 2: Comparison of the results obtained using the three decomposition methods (example 1)

26

1 1/λi 1/?i ei 2-A 2-B 2-C Ci Ci Ci 50 5 0.909 25 50 100

2 800 240 0.769 30 60 120

3 150 10 0.938 10 20 40

4 400 60 0.87 15 30 30

5 400 40 0.909 15 30 60

6 200 20 0.909 25 50 100

7 500 40 0.926 35 70 140

8 1200 240 0.833 25 50 100

9 100 5 0.952 30 60 120

10 1600 240 0.87

Table 3: Data for Example 2
X 2-A simulation +/E-method error(%) GE-method error(%) HE-method error(%) 2-B simulation +/E-method error(%) GE-method error(%) HE-method error(%) 2-C simulation +/E-method error(%) GE-method error(%) HE-method error(%) Q1 Q2 Q3 5.9581 0.0114 5.1377 -13.77 6.9203 +16.15 6.0175 +1.00 Q4 7.7096 0.0180 6.3805 -17.24 7.8791 +2.20 7.5509 -2.06 Q5 6.9254 0.0207 5.8770 -15.14 6.3234 -8.69 6.6764 -3.60 Q6 8.1589 0.0370 Q7 9.8485 0.0549 Q8 5.7446 0.0257 8.0386 +39.93 4.1113 -28.43 5.2903 -7.91 Q9 4.0244 0.0307 3.6234 -9.96 3.6774 -8.62 3.3242 -17.40

0.5476 19.7957 21.9794 0.0007 0.0122 0.0375

0.6285 19.4582 19.4528 +14.77 -1.70 -11.50

7.4793 11.7612 -8.33 8.1173 -0.51 7.7633 -4.85 +19.42 9.8347 -0.14 8.8142 -10.50

0.5224 18.4646 22.1775 -4.60 -6.72 +0.90

0.5539 20.0935 22.6185 +1.15 +1.50 +2.91

0.5970 40.3525 41.3476 11.5761 14.6174 13.3527 16.8955 22.6336 11.7380 10.3920 0.0002 0.0103 0.0228 0.0083 0.0148 0.0143 0.0229 0.0385 0.0223 0.0287 8.8076 -15.25 8.8126 -15.20 8.5385 -17.84

0.6827 39.5146 36.4460 +14.36 -2.08 -11.85

8.8814 10.7031 10.5062 13.4509 22.9703 16.0016 -23.28 -26.78 -21.32 -20.39 +1.49 +36.32 9.1171 -22.33

0.5779 38.4531 43.0505 13.7808 15.2080 12.1912 15.7651 20.6955 -3.20 -4.71 +4.12 +19.05 +4.04 -8.70 -6.69 -8.56

0.6077 40.8673 42.9696 11.5858 14.3059 13.0935 16.0473 19.8744 10.5427 +1.79 +1.28 +3.92 +0.08 -2.13 -1.94 -5.02 -12.19 -10.18

0.6563 80.3691 72.4321 22.5689 26.3027 24.6641 34.6635 53.6346 24.6085 27.5443 0.0008 0.0935 0.2440 0.0670 0.1123 0.1274 0.2439 0.3590 0.1368 0.1740

0.7296 78.5173 60.2291 14.8528 16.3419 17.6390 25.3253 45.1407 26.9122 22.0427 +11.17 -2.30 -16.85 -34.19 -37.87 -28.48 -26.94 -15.84 +9.36 -19.97

0.6523 77.3405 78.4056 26.6536 27.9996 22.9221 30.2500 45.1272 21.1203 23.0181 -0.61 -3.77 +8.25 +18.10 +6.45 -7.06 -12.73 -15.86 -14.17 -16.43

0.6700 80.3439 74.8058 22.0147 25.3538 24.1737 32.3210 47.0364 22.2008 23.8824 +0.98 -0.03 +3.28 -2.46 -3.61 -1.99 -6.76 -12.30 -9.78 -13.29

Table 4: Comparison of the results obtained using the three decomposition methods (example 2)

27

E-DDX Algorithm GE-DDX Algorithm HE-DDX Algorithm (1.10-4 second) 1-A 1-B 1-C 2-A 2-B 2-C 28.02 31.87 31.87 30.05 32.85 33.01 (1.10-4 second) 23.08 30.77 35.16 27.02 31.05 36.28 (1.10-4 second) 145.60 166.48 188.46 151.78 171.40 191.50

Table 5: Time required to achieve convergence of each algorithm with the convergence parameter equal to 1.10-7

28


更多相关文档:

Improvement of the signal to noise ratio of Lidar echo signal....pdf

ltering the signals of an exponential attenuation....method to remove noise and subtract the part DC...l l Using the 5 levels decomposition of the ...

A fast and adaptive method for image contrast enhancement_....pdf

decomposition and reconstruction and has been used ...According to [10, 11], the exponential and ...method (anisotropic propagation with R = 0.1) ...

A convenient computational form for the Adomian pol....pdf

decomposition method for nonlinear stochastic operator...[2,31 to now include exponential or trigonometric...“=l (1) as (2) C(v, n) H,(q,) ...

南非教授 Optical quasi-solitons by Lie summetry analysis.pdf

Lie summetry analysis_哲学/历史_人文社科_专业资料...decomposition method, He’s variational iteration ...ned as the exponential integral for n = 1 or ...

Thermal kinetic studies on the decompositions of cefuroxime_....pdf

thermogravimetry (DTG) and differential scanning calorimetry (DSC) methods [1... E and the pre-exponential factor, A of the exothermic decomposition of ...

A comparative analysis between temperature and pressure ....pdf

exponential dependence of the vapour pressure on ...decomposition (gassy system) Shellsol T and the ...A Comparative Analysis... 3页 1下载券 ...

土壤有机质.pdf

decomposition rate [39], it is necessary to ... Gaussian lineshape, 1.16-G linewidth and hyper...From the exponential equation, the pseudo-?rst...

1-s2.0-S0140670199983844-main.pdf

what is behind the industry’ s exponential ... the decomposition of iron disulfide was ...analysis method for detecting vegetable oils was ...

slides12_图文.pdf

densities are not simple (Gaussian, exponential, ...5D If we can find this hyper-plane we can: ...?0 ? 17 Symmetric Matrix Eigendecomposition Th n...

...approximate formula for non-isothermal kinetic analysis_....pdf

analysis of non-isothermal solid decomposition is ...For its many inherent advantages, integral method ...(1) where A is the pre-exponential factor of ...

Comparison of the Adomian decomposition method with.pdf

2. Analysis of the Adomian decomposition method ...to u?r?. This is called a deformation and L...1 AN HYPER-EXPONENTIAL... 28页 免费 THE ...

Thermogravimetric analysis of the decomposition of poly(1,4-....pdf

analysis of the decomposition of poly(1,4dioxan-...2? where A, the pre-exponential factor, is ...method for the estimation of reaction mechanisms ...

...method with Benders decomposition for solving tw....pdf

1 AN HYPER-EXPONENTIAL D... 28页 免费 Decomposition Method for... 暂无...All these wait-and-see measures usually cost more than regular production. ...

INVERSE CHARACTERIZATION OF HYPEREXPONENTIAL MAP(2)S.pdf

c-based decomposition of queueing networks, where the network is analyzed ... 21 1 12 (7) 22 2 (8) Figure 2: CTMC of the hyperexponential MAP...

The Sinc-Galerkin Schwarz alternating method for Poisson 's ....pdf

singularities, while maintaining their characteristic exponential convergence rate....A thorough convergence analysis for sinc domain decomposition methods for ...

1 Dynamic Analysis of Constraint-Variable Dependencies to ....pdf

[13] employs hypergraph partitioning methods to derive a tree decomposition....algorithms[7] [9] are known to be time exponential in the tree width. ...

Zeros of z-transform (ZZT) decomposition of speech for source....pdf

spectral decomposition method for source-tract ...Although LP analysis is a widely used technique,...For an increasing exponential, a>1, the zeros ...

Statistical Analysis of SVD-Based Prony Techniques.pdf

Prony method applied to damped exponential signals..... . m?1 ( ) N yL (N ) L+1 (N ) ...decomposition of the matrix y Y and truncating ...

Numerical,Methods,计算方法 Lecture5_IterativeMethods_Handout(....pdf

Numerical,Methods,计算方法 Lecture5_IterativeMethods...The convergence is exponential with a slope ? 1...decomposition we have n det(A) = det(L) × ...

Selberg Integrals.pdf

one gets the exponential Selberg integral [M]: ...ection hyperplanes of a Coxeter group G. Let ...Kato, Gauss decomposition of connection matrices ...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com