# Buffer Allocation via Bottleneck-Based Variable Neighborhood Search
## 3 Solution Methodology
### Active Probability Index (API)  
A bottleneck is a blocking point in a production line. A bottleneck indicator (BI), such as inventory [24] and active time [25], is an evaluation parameter that can be used to identify the bottleneck of the production line. The inventory indicator is the probability of full capacity, and a machine with a high inventory can easily become the bottleneck of a production line. The active time is the time when the machine is in the processing state; a machine with a long active time has a high possibility to be the bottleneck of a production line. Active time is effective in finding the real bottleneck [25]. However, QMTAA calculates the throughput of the production line based on steady-state probabilities but not on processing time. Therefore, based on the definition of the active time, the active probability index as a bottleneck indicator is proposed:  
\[\beta_{i}=\pi(n_{i}=1,n_{l}=0)+\pi(n_{h}=1,n_{i}=1,n_{l}=0) \tag{5}\]  
Here, \(\pi(n_{i}=1,n_{l}=0)\) is the state probability of one job being at node \(i\) and no jobs being at its following node \(l\). The state of \(\pi(n_{i}=1,n_{l}=0)\) is described as shown in Figure 4; the red circle represents the job at node \(i\). The term \(\pi(n_{h}=1,n_{i}=1,n_{l}=0)\) is the state probability of one job being at node \(h\) and its following node \(i\), respectively, while no jobs are at node \(l\). The state of \(\pi(n_{h}=1,n_{i}=1,n_{l}=0)\) is described as shown in Figure 5.  
In the case of a high arrival rate, \(\pi(n_{i}=1,n_{l}=0)\) is effective to detect the bottleneck of a production line. However, when the external arrival rate is low, and few jobs are in a production line, the states of each node may be similar. This can decrease the effectiveness of \(\pi(n_{i}=1,n_{l}=0)\). Considering that jobs are usually blocked before the bottleneck as the state is shown in Figure 5, \(\pi(n_{h}=1,n_{i}=1,n_{l}=0)\) is used to improve the effectiveness of \(\beta_{i}\) in the case of low arrival rates. Using QMTAA, the state  
Figure 4: State of \(\pi(n_{i}=1,n_{l}=0)\).  
Figure 3: Framework of QMTAA.  
probabilities of nodes in a production line can be obtained via a throughput calculation process. By substituting the state probabilities into Equation (5), the specific values of the active probability index of each node can be obtained.  
If node \(i\) is a merging node as shown in Figure 6, two active probability indexes can be obtained as  
\[\beta_{i-g}=\pi(n_{i}=1,n_{l}=0)+\pi\Big{(}n_{g}=1,n_{i}=1,n_{l}=0\Big{)} \tag{6}\]  
\[\beta_{i-h}=\pi(n_{i}=1,n_{l}=0)+\pi(n_{h}=1,n_{i}=1,n_{l}=0) \tag{7}\]  
where \(\beta_{i-g}\) refers to the active probability index for the location between nodes \(g\) and \(i\); meanwhile \(\beta_{i-h}\) refers to the active probability index for the location between nodes \(h\) and \(i\).  
If node \(i\) is a splitting node as shown in Figure 7, there are two routes after node \(i\). Because each job at node \(i\) can only enter one route, two active probability indexes of two routes can be calculated, respectively. The maximum value between the two active probability indexes is used as the active probability index for node \(i\).  
\[\beta_{i}=\max\left\{\begin{array}{l}\pi(n_{i}=1,n_{l}=0)+\pi(n_{h}=1,n_{i} =1,n_{l}=0),\\ \pi\Big{(}n_{i}=1,n_{p}=0\Big{)}+\pi\Big{(}n_{h}=1,n_{i}=1,n_{p}=0\Big{)} \end{array}\right\} \tag{8}\]