# Elimination Properties for a Probabilistic Scheduling Problem
## 7 Computational Experiments
### Algorithm Stability
#### 7.2.2 Algorithms' Stability  
The main purpose of the conducted computational experiments was to examine the individual stability of individual algorithms, i.e., resistance of solutions determined by these algorithms for random changes (disturbances) of parameters.  
Let \(\mathcal{D}\) be a set of deterministic data, \(\hat{\mathcal{D}}\) the corresponding set of probabilistic data, and \(\mathcal{Z}\) the set of disturbed data. Based on this data, the stability coefficients of individual algorithms were designated. Comparative results are shown in Tables 2-4 (best values in a group are marked in bold).  
In general, the Tabu search algorithm with blocks is much more resistant to disturbed data disorders. The comparative results generated for 3 groups of examples with the size \(n=40\) (Table 3), \(n=50\) (Table 4), and \(n=100\) (Table 5) clearly indicate that for almost every group of examples the value of the resistant coefficient is lower for the \(TS_{\mathcal{P}+\mathcal{B}}\) algorithm compared to the value of this coefficient for the \(TS_{\mathcal{P}}\) algorithm. The only exceptions are the groups of examples 026-050, \(c=0.05\) and \(c=0.1\); 010-125, \(c=0.05\) and \(c=0.1\) for \(n=40\); 026-050, \(c=0.05\), \(c=0.1\) and 101-125, \(c=0.05\) for \(n=50\); 101-125, \(c=0.1\) and 076-100.  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Instance Group**} & \multicolumn{2}{c}{\(\boldsymbol{\epsilon=0.05}\)} & \multicolumn{2}{c}{\(\boldsymbol{c=0.1}\)} & \multicolumn{2}{c}{\(\boldsymbol{c=0.2}\)} \\ \cline{2-7}  & \(TS_{\mathcal{P}}\) & \(TS_{\mathcal{P+\mathcal{B}}}\) & \(TS_{\mathcal{P}}\) & \(TS_{\mathcal{P+\mathcal{B}}}\) & \(TS_{\mathcal{P}}\) & \(TS_{\mathcal{P+\mathcal{B}}}\) \\ \hline
000–025 & 0.0175 & \(-\)**0.0170** & 0.0183 & **0.0044** & 0.0912 & **0.0850** \\
026–050 & **0.0087** & 0.0221 & 3.7938 & **3.1483** & 0.2869 & **0.2023** \\
050–075 & 0.0009 & \(-\)**0.0036** & 0.0247 & **0.0177** & 2.4646 & **2.2704** \\
076–100 & 0.0009 & \(-\)**0.0288** & 20.6039 & **18.0087** & 0.2451 & **0.1578** \\
101–125 & **0.0013** & 0.0033 & **0.4440** & 0.7487 & 13.2248 & **12.6221** \\ \hline Average & 0.0059 & \(-\)**0.0048** & 4.9769 & **4.3856** & 3.2625 & **3.0675** \\ \hline \hline \end{tabular}
\end{table}
Table 2: Computational results \(\mathcal{S}(A,\hat{\mathcal{P}})\) for the \(wt40\) instance group.  
\(c=0.2\) for \(n=100\), but they do not affect significantly the overall value of the immunity coefficient. The negative value of the coefficient is related to receiving better than reference solutions by the tested algorithm.  
A summary of the results obtained is given in Table 5 (the best values are marked in bold). The stability coefficients of both algorithms increase with the increase of parameter \(c\). This parameter has a direct impact on the variance of the distribution from which the data are drawn. The \(TS_{\mathcal{P}+\mathcal{B}}\) algorithm has a lower stability factor, so the solutions determined by this algorithm are more resistant to data disturbances. In addition, this algorithm, at the same time of calculations, determines much better solutions than the \(TS_{\mathcal{P}}\) algorithm (see Table 1). For the number of tasks \(n=100\), the relative error is almost 10 times smaller. Summing up, the use of blocks in the tabu search algorithm, compared eith the algorithm without blocks, gives a significant improvement in the value of the determined solutions and their stability.