# A Recursive Optimization Approach for Buffer Allocation in Large Production Lines
## 5 Solution Approach
### Recursive Overlapping Decomposition Algorithm  
In the previous algorithm, a production line is divided into two sub-lines without overlapping buffers, i.e., each buffer of the sub-lines corresponds to a different buffer in the original line. In this subsection, we propose a recursive overlapping decomposition (ROD) algorithm, which allows the sub-lines have overlapping buffers, i.e., the buffers of the sub-lines may correspond to the same buffer in the original line. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Label** & \begin{tabular}{c} **Line/** \\ **Sub-Lines** \\ \end{tabular}  & \begin{tabular}{c} **Left** \\ **Sub-Line** \\ \end{tabular}  & \begin{tabular}{c} **Right** \\ **Sub-Line** \\ \end{tabular}  & \ \begin{tabular}{c} **Initial** \\ **Solution \(b\)** \\ \end{tabular}  & \begin{tabular}{c} **Optimal** \\ **Solution \(b^{*}\)** \\ \end{tabular}  & \(P(b^{*})\) \\ \hline \(L\) & \((M_{1},B_{1},...,M_{5})\) & \(L_{1}\) & \(L_{2}\) & \((30,31,31,30)\) & \((37,50,51,37)\) & 0.850054 \\ \(L_{1}\) & \((M_{1},B_{1},...,M_{3})\) & \(L_{1.1}\) & \(L_{1.2}\) & \((13,13)\) & \((30,31)\) & 0.850417 \\ \(L_{1.1}\) & \((M_{1},B_{1},M_{2})\) & & & \((0)\) & \((13)\) & 0.850610 \\ \(L_{1.2}\) & \((M_{2},B_{2},M_{3})\) & & & \((Consider the production line \(L\) in Figure 5, which consists of machines \(M_{1},...,M_{K}\) and buffers \(B_{1},...,B_{K-1}\). Let \(s=\lfloor K/3\rfloor\) be the largest integer less than or equal to \(K/3\). The line \(L\) is decomposed into a left sub-line \(L_{1}\), which consists of machines \(M_{1},...,M_{K-s}\) and buffers \(B_{1},...,B_{K-s-1}\), and a right sub-line \(L_{2}\), which consists of machines \(M_{s+1},...,M_{K}\) and buffers \(B_{s+1},...,B_{K-1}\). Clearly, when \(K>3\), the two sub-lines have overlapping buffers \(B_{s+1},...,B_{K-s-1}\). As in the previous case, the sub-lines \(L_{1}\) and \(L_{2}\) operate independently and they are recursively decomposed until the decomposed sub-lines have only three machines. Figure 6 shows the flowchart of the ROD algorithm and the pseudocode is given in Algorithm 3. ```
Step 1: Solve the base case  If \(K\leq 3\)  call the gradient search algorithm to solve \(\text{BAP}(M_{1},B_{1},...,M_{K},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}\) \(s:=\lfloor K/3\rfloor\) \(L_{1}:=(M_{1},B_{1},...,M_{K-s})\) \(L_{2}:=(M_{s+1},B_{s+1},...,M_{K})\) Step 3: Solve the BAP in the left sub-line \(L_{1}\)  call the ROD algorithm to recursively solve \(\text{BAP}(M_{1},B_{1},...,M_{K-s},P^{*})\). let \(x=(x_{1},...,x_{K-s-1})\) be the obtained solution. Step 4: Solve the BAP in the right sub-line \(L_{2}\)  call the ROD algorithm to recursively solve \(\text{BAP}(M_{s+1},B_{s+1},...,M_{K},P^{*})\). let \(y=(y_{s+1},...,y_{K-1})\) be the obtained solution. Step 5: Solve the BAP in the original line \(L\) \(b:=(x_{1},...,x_{s},\max(x_{s+1},y_{s+1}),...,\max(x_{K-s-1},y_{K-s-1}),y_{K-s },...,y_{K-1})\)  call the gradient search algorithm to solve \(\text{BAP}(M_{1},B_{1},...,M_{K},P^{*})\) with the initial solution \(b\). return the obtained solution \(b^{*}\). ```  
**Algorithm 3** Recursive overlapping decomposition algorithm (ROD)  
Figure 5: Recursive overlapping decomposition of a production line. Table 4 shows how the ROD algorithm solves the BAP described in the previous subsection. The line \(L\) is decomposed into two sub-lines \(L_{1}\) and \(L_{2}\), which are further decomposed into sub-lines \(L_{1.1}\), \(L_{1.2}\), \(L_{2.1}\), and \(L_{2.2}\). These three-machine, two-buffer systems belong to the base case and they have the same solution \((30,31)\). Then, the solutions of \(L_{1.1}\) and \(L_{1.2}\) are combined as the initial solution \((30,31,31)\) for the gradient algorithm to obtain the optimal solution of \(L_{1}\), i.e., \((35,46,36)\). The BAP in \(L_{2}\) is solved similarly.