# A Recursive Optimization Approach for Buffer Allocation in Large Production Lines
## 4 Performance Evaluation Method  
[PERSON] [16] proposed a well-known decomposition method for approximate performance evaluation of homogeneous production lines. This method was widely used in the study of BAPs [8; 32; 48]. As illustrated in Figure 2, the idea of decomposition is to decompose a \(K\)-machine production line \(L\) into a set of two-machine, one-buffer subsystems \(L(i)\), \(i=1,...,K-1\). The virtual machine \(M_{u}(i)\) of \(L(i)\) represents the portion of line \(L\) upstream of buffer \(B_{i}\), i.e., machine \(M_{1}\) to machine \(M_{i}\). Similarly, the virtual machine \(M_{d}(i)\) represents the portion of line \(L\) downstream of buffer \(B_{i}\), i.e., machine \(M_{i+1}\) to machine \(M_{K}\). Moreover, the buffer \(B(i)\) of \(L(i)\) has the same capacity, \(N_{i}\), as the original buffer \(B_{i}\). The decomposition principle is to determine the parameters of virtual machines such that the behavior of material flow through buffer \(B(i)\) is as close to that of the flow through buffer \(B_{i}\) as possible. [PERSON], [PERSON], and [PERSON] [17] established the decomposition equations of virtual machine parameters for the continuous flow production line model described in the previous section. They also proposed an efficient algorithm, called the DDX algorithm, to solve the equations. We do not use [PERSON]'s decomposition method to evaluate the production rate of homogeneous lines. The reason is that the accuracy of [PERSON]'s decomposition method may be unacceptable when the reliability parameters of different machines have different orders of magnitude [21]. This may lead to incorrect results when comparing the performance of different buffer configurations. For example, consider the six-machine line described in Table 1. The production rate of the line under several different buffer configurations was evaluated by the DDX algorithm and the results are presented in Table 2. Note that the buffer configurations C1-C5 are obtained from C0 by increasing the buffer capacity \(b_{i}\) by 1, \(i=1,...,5\), respectively. It can be observed that for each buffer \(B_{i}\), while its capacity increases, the production rate obtained by the DDX algorithm decreases. This phenomenon is very strange and should not occur, since the production rate is a monotonic function with respect to buffer capacities [50]. Table 2 also presents the production rate obtained by simulation. To avoid incorrect comparisons due to simulation errors, the random variable sequences in the simulations of different buffer configurations were set to be the same, i.e., the sequences of times to failure and the sequences of times to repair of each machine were the same for all the simulations. These simulations were terminated when each machine had encountered at least 10,000 repair events. As can be seen, the simulated production rates satisfy monotonicity. To avoid the above problem, we use the robust decomposition method [21] to evaluate homogeneous production lines. Unlike the decomposition method in [17], which models  
Figure 2: Decomposition method for approximate performance evaluation. the repair times of virtual machines by exponential distributions, the robust decomposition method uses two-stage hyper-exponential distributions to model the repair times. The hyper-exponential distributions allow the use of a three-moment approximation instead of a single-moment approximation of the repair times. In this way, the accuracy is greatly improved. As can be seen from Table 2, the production rates evaluated by the robust decomposition method are much closer to the simulated production rates than the DDX algorithm. More importantly, the robust decomposition method leads to the same results as the simulation method when comparing the performance of different buffer configurations. For example, both methods show that buffer configuration C5 is the best one among C0-C5, whereas the DDX method shows that C0 is. The robust decomposition method is only applicable to homogeneous production lines.