# Buffer Allocation via Bottleneck-Based Variable Neighborhood Search
## 3 Solution Methodology  
Previous studies typically achieved the desired throughput by allocating several buffers at different locations in the production line. This method allows adding buffers at unsuitable locations; however, it increases the computation time of buffer allocation. Thus, to decrease unsuitable buffer allocation, it is effective to add one buffer at the bottleneck of a production line in each buffer update.  
Figure 1 presents the framework of the proposed bottleneck-based variable neighborhood search algorithm. The Algorithm 1 presents the pseudocode of the proposed bottleneck-based variable neighborhood search algorithm. The algorithm detects the bottleneck of a production line using an active probability index. The initial neighborhood structure is set to detect the bottleneck with a small number of searches, which decreases the computation time of buffer allocation. When no satisfactory solution is generated in the initial neighborhood structure, an additional neighborhood structure is used to assess more candidate nodes, which improves the solution quality of the buffer allocation. The algorithm ends with no throughput increasing by allocating buffers or available computation time being exceeded.  
Figure 1: Framework of the bottleneck-based variable neighborhood search algorithm.  
```
1 Initialize parameters \(T_{sol}=1\) Input arrival rates \(\lambda_{i}\), service rates of nodes \(\mu_{i}\), nodes \(\mathit{nod}=\{1,\cdots,i,l,\cdots\}\), edges \(\mathit{edg}=\{\cdots,(i,l),\cdots\}\) between nodes, service discipline \(\mathit{sed}=\{\cdots,(i,\mathit{FCFS}),\cdots\}\) at merging or splitting node \(i\) while\(T_{sol}>T_{comparison}\) and \(t_{sol}<t_{available}\)do
5\(j=j+1\)if\(j=1\)then
6 Calculate system state probability \(\mathit{sta}\) by QMTAA
7 else
8 if\(j>2\)then
9\(T_{comparison}=T_{hig}^{j-1}\)
11 endif
12 Update \(\lambda_{i}\), \(\mu_{i}\), \(\mathit{nod}\), \(\mathit{edg}\), \(\mathit{sed}\), \(\mathit{sta}\)
13 Calculate active probability index \(\beta_{i}\) of node \(i\) based on \(\mathit{sta}\)
14 Calculate total number of candidate bottlenecks \(V_{\mathit{bot}}\)
15 for\(k=1\) to initial search times \(C_{\mathit{ori}}\)do
16\(V_{\mathit{hot}}=V_{\mathit{hot}}-C_{\mathit{ori}}\)
17 Add one buffer before one candidate bottleneck based on \(\beta_{i}\) from high value to low value and generate new \(\lambda_{i}\), \(\mu_{i}\), \(\mathit{nod}\), \(\mathit{edg}\), \(\mathit{sed}\).
18 Calculate throughput of the new \(\lambda_{i}\), \(\mu_{i}\), \(\mathit{nod}\), \(\mathit{edg}\), \(\mathit{sed}\) by QMTAA and put it into throughput set \(\mathit{thr}\)
19 Recover \(\lambda_{i}\), \(\mu_{i}\), \(\mathit{nod}\), \(\mathit{edg}\), \(\mathit{sed}\)
20 endfor
21\(T_{hig}^{j}=\mathit{max}\)\(\mathit{thr}\)
22 while\(\frac{T_{hig}^{j}-T_{hig}^{j-1}}{T_{hig}^{j+1}}<\varepsilon\) and \(V_{\mathit{hot}}>0\)do
23\(V_{\mathit{hot}}=V_{\mathit{hot}}-C_{\mathit{add}}\)
24 Set \(\mathit{thr}=\{\}\) and put \(T_{hig}^{j}\) into \(\mathit{thr}\)
25 for\(k=1\) to additional search times \(C_{\mathit{add}}\)do
26 Add one buffer before one candidate bottleneck based on \(\beta_{i}\) from high value to low value and generate new \(\lambda_{i}\), \(\mu_{i}\), \(\mathit{nod}\), \(\mathit{edg}\), \(\mathit{sed}\).
27 Calculate throughput of the new \(\lambda_{i}\), \(\mu_{i}\), \(\mathit{nod}\), \(\mathit{edg}\), \(\mathit{sed}\) by QMTAA and put it into throughput set \(\mathit{thr}\)
28 Recover \(\lambda_{i}\), \(\mu_{i}\), \(\mathit{nod}\), \(\mathit{edg}\), \(\mathit{sed}\)
29 endfor
30\(T_{hig}^{j}=\mathit{max}\)\(\mathit{thr}\)
31 endwhile
32\(T_{sol}=T_{hig}^{j}\)
33\(N_{\mathit{sat}}=N_{hig}^{j}\)
34\(B_{\mathit{sol}}=B_{hig}^{j}\)
35 endif
36 endwhile
```  
**Algorithm 1**bottleneck-based variable neighborhood search algorithm