## 7 Computational Experiments
Table 3 contains PRD improvement values relative to the solution obtained by the META algorithm, which is also a starting solution for parallel TSA (that is why they are negative) for bigger instances of the sizes (\(n=200\), \(500\) and \(1000\)). Experiments have been conducted for the number of processors \(p=8,16,32\) and \(64\). One can observe that increasing of the number of processors results in improving of the quality of the obtained solutions especially for algorithm with blocks. Tables 4 and 5 contain speedup results. The values have been calculated from the relationship \(s=t_{s}/t_{p}\), where  
* \(t_{s}\) time during which the sequential algorithm obtains the \(F\) solution,
* \(t_{p}\) is the time after which the parallel algorithm obtains the \(F\) solution. From the results presented in the table, it can be seen that high speedups are obtained for smaller size problems (\(s_{TS_{b}}\) values over \(60,000\) for \(n=40\)). The block algorithm gives better acceleration (on average more than \(2600\) times better). Such results are probably the result of the fact that the size of the problem solution space (\(40\)!, \(50\)!, \(100\)!, \(200\)!, \(500\)!, \(1000\)!) increases much faster than the number of processors increases (8, 16, 32, 64). The increase in speedup within a single size of the problem is also not large as shown above. The large disproportion in speedup of the algorithm with and without blocks results from the fact that the block algorithm strongly limits the space of the solutions being reviewed. As one can see increasing the size of the problem reduces the value of the speedup obtained - which is probably due to the limited computation time for a larger space for search solutions; however, increasing the number of processors does not have a big impact on acceleration values even when increasing the size of the problem. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Instance Group**} & \multicolumn{2}{c}{\(wt200\)} & \multicolumn{2}{c}{\(wt500\)} & \multicolumn{2}{c}{\(wt1000\)} \\ \cline{2-7}  & \(TS\) & \(TS_{b}\) & \(TS\) & \(TS_{b}\) & \(TS\) & \(TS_{b}\) \\ \hline \(001\)–\(025\) & \(-18.43\) & \(-18.49\) & \(-15.55\) & \(-16.85\) & \(-5.21\) & \(-7.54\) \\ \(026\)–\(050\) & \(-11.38\) & \(-11.29\) & \(-13.68\) & \(-13.88\) & \(-4.05\) & \(-3.54\) \\ \(051\)–\(075\) & \(-9.84\) & \(-9.78\) & \(-9.18\) & \(-9.14\) & \(-3.79\) & \(-3.65\) \\ \(076\)–\(100\) & \(-5.77\) & \(-5.73\) & \(-3.32\) & \(-3.46\) & \(-4.60\) & \(-3.82\) \\ \(101\)–\(125\) & \(-2.80\) & \(-2.79\) & \(-3.99\) & \(-3.93\) & \(-1.32\) & \(-0.78\) \\ \hline average & \(-9.64\) & \(-9.62\) & \(-9.15\) & \(-9.45\) & \(-3.79\) & \(-3.87\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Computational results for sequential tabu search algorithm (\(t=120\) s, META as reference). \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Number of Processors**} & \multicolumn{2}{c}{\(wt200\)} & \multicolumn{2}{c}{\(wt500\)} & \multicolumn{2}{c}{\(wt1000\)} \\ \cline{2-7}  & \(TS\) & \(TS_{b}\) & \(TS\) & \(TS_{b}\) & \(TS\) & \(TS_{b}\) \\ \hline \(1\) & \(-9.64\) & \(-9.62\) & \(-9.15\) & \(-9.45\) & \(-3.79\) & \(-3.87\) \\ \(8\) & \(-9.65\) & \(-9.63\) & \(-9.17\) & \(-9.53\) & \(-3.88\) & \(-3.91\) \\ \(16\) & \(-9.65\) & \(-9.64\) & \(-9.17\) & \(-9.55\) & \(-3.88\) & \(-3.92\) \\ \(32\) & \(-9.65\) & \(-9.66\) & \(-9.17\) & \(-9.55\) & \(-3.88\) & \(-3.94\) \\ \(64\) & \(-9.66\) & \(-9.71\) & \(-9.19\) & \(-9.59\) & \(-3.88\) & \(-3.95\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Computational results for parallel tabu search algorithm (\(t=120\) s, META as reference).