# A Recursive Optimization Approach for Buffer Allocation in Large Production Lines
## 5 Solution Approach
### Recursive Binary Decomposition Algorithm  
On way to improve the efficiency of the gradient search algorithm is to start with a good initial solution. For this purpose, we propose a recursive binary decomposition (RBD) algorithm. Consider the production line \(L\) in Figure 3, which consists of machines \(M_{1},...,M_{K}\) and buffers \(B_{1},...,B_{K-1}\). The middle machine of \(L\) is \(M_{m}\), where \(m=\lceil(K+1)/2\rceil\), i.e., \(m\) is the smallest integer greater than or equal to \((K+1)/2\). The line \(L\) is decomposed into a left sub-line \(L_{1}\), which consists of machines \(M_{1},...,M_{m}\) and buffers \(B_{1},...,B_{m-1}\), and a right sub-line \(L_{2}\), which consists of machines \(M_{m},...,M_{K}\) and buffers \(B_{m},...,B_{K-1}\). The two sub-lines operate independently. Moreover, each sub-line is recursively decomposed until the decomposed sub-lines have only two machines. Consider the BAP in \(L\) with a desired production rate \(P^{*}\), represented by BAP\((M_{1},B_{1},...,M_{K},P^{*})\). Let \(b=(b_{1}^{*},...,b_{K-1}^{*})\) be the optimal solution to this problem. Then, \((b_{1}^{*},...,b_{m-1}^{*})\) can guarantee the sub-line \(L_{1}\) achieves the desired production rate \(P^{*}\), because the last  
Figure 3: Recursive binary decomposition of a production line. machine \(M_{m}\) in \(L_{1}\) is never blocked, meaning that \(P_{L_{1}}(b_{1}^{*},...,b_{m-1}^{*})>P_{L}(b_{1}^{*},...,b_{K-1}^{*})\geq P^{*}\) (see [52] for a strict proof). Let \(x=(x_{1},...,x_{m-1})\) be the optimal solution to the sub-problem BAP\((M_{1},B_{1},...,M_{m},P^{*})\) in \(L_{1}\). It follows that \(\sum_{i=1}^{m-1}x_{i}\leq\sum_{i=1}^{m-1}b_{i}^{*}\), i.e., the sum of the buffer capacities \(x_{i}\) in \(L_{1}\) provides a lower bound for the sum of the respective buffer capacities \(b_{i}^{*}\) in the original line \(L\). In the RBD algorithm, we use \(x_{i}\) as a lower bound of \(b_{i}^{*}\), \(i=1,...,m-1\) to speed up the search process. Similarly, let \(y=(y_{m},...,y_{K-1})\) be the optimal solution to the sub-problem BAP\((M_{m},B_{m},...,M_{K},P^{*})\) in \(L_{2}\),and \(y_{i}\) is used as a lower bound of the respective buffer capacity \(b_{i}^{*}\) in the original line \(L\), \(i=m,...K-1\). The main steps of the RBD algorithm are exhibited as a flowchart in Figure 4 and the pseudocode is given in Algorithm 2. Note that the sub-lines \(L_{1}\) and \(L_{2}\) may have multiple optimal solutions. For example, consider a five-machine, four-buffer line with identical machines. The left sub-line \(L_{1}=(M_{1},B_{1},M_{2},B_{2},M_{3})\) may have two optimal solutions \((a,a+1)\) and \((a+1,a)\), because when the current solution of the gradient algorithm is \((a,a)\), the components \(g_{1}\) and \(g_{2}\) are the same due to symmetry. The right sub-line \(L_{2}\) may also have the ambiguity problem. In our implementation, the following rule is used: if \(L_{1}\) has more than one maximum gradient component, the buffer on the right is prioritized higher; if \(L_{2}\) has more than one maximum gradient component, the buffer on the left is prioritized higher. According to  
Figure 4: Flowchart for the RBD algorithm. this rule, the initial solution to the original BAP is \((a,a+1,a+1,a)\), which is consistent with the inverted bowl phenomenon [53]. ```
Step 1: Solve the base case  If \(K=2\)  call the gradient search algorithm to solve BAP\((M_{1},B_{1},M_{2},P^{*})\). return the obtained solution \(b^{*}\). Step 2: Decompose the line \(L\) into a left sub-line \(L_{1}\) and a right sub-line \(L_{2}\) \(m:=\lceil(K+1)/2\rceil\) \(L_{1}:=(M_{1},B_{1},...,M_{m})\) \(L_{2}:=(M_{m},B_{m},...,M_{K})\) Step 3: Solve the BAP in the left sub-line \(L_{1}\)  call the RBD algorithm to recursively solve BAP\((M_{1},B_{1},...,M_{m},P^{*})\). let \(x=(x_{1},...,x_{m-1})\) be the obtained solution. Step 4: Solve the BAP in the right sub-line \(L_{2}\)  call the RBD algorithm to recursively solve BAP\((M_{m},B_{m},...,M_{K},P^{*})\). let \(y=(y_{m},...,y_{K-1})\) be the obtained solution.