## 7 Computational Experiments  
The parallel tabu search MWWTS algorithm has been implemented in C++ using the MPI library. The calculations were made on the BEM cluster installed in the Wroclaw Network and Supercomputing Center. Parallel computing tasks were run on Intel Xeon E5-26702.30 GHz on processors under the control of the PBS queue system. Examples of test data of various sizes and degrees of difficulty, on which the calculations were made, were divided into two groups:  
Figure 2: Tabu Search MWPTSA parallelization scheme. (a) the first group includes 375 examples of three different sizes (\(n=40,50,100\)). Together with the best solutions, they are placed on the OR-Library [44] website. (b) the second group embracing test instances for \(n=200,500,1000\) was generated in following way:  
* random integer from range \([1,100]\) with uniform distribution,
* random integer from range \([1,10]\) with uniform distribution,
* random integer from range \([P(1-T_{F}-R_{DD}/2),P(1-T_{F}+R_{DD}/2)]\) with uniform distribution. Where \(P=\sum_{i=1}^{n}p_{i}\), \(R_{DD}=0.2,0.4,0.6,0.8,1.0\) (relative range of due dates) and \(F_{T}=0.2,0.4,0.6,0.8,1.0\) (average tardiness factor). For each of the 25 pairs of values of \(R_{DD}\) and \(F_{T}\) five instances were generated. Overall, 325 instances were generated - 125 for each value of \(n\). Test instances was published on web page [45]. Computational experiments of the algorithms presented in the work were carried out in several stages. First, the construction algorithms SWPT, EDD, COVERT, AU and META algorithms, presented in Section 5.1, were compared. Calculations were made on examples from group a). The obtained results (percentage relative error (11)) are presented in Table 1, compared to the reference solutions taken, as well as benchmarks data, from the OR-Library [44]. The best solutions were determined by the META algorithm [30]. The solutions of this algorithm are the starting point of the TSA algorithm. When running these algorithms on multiple processors, each of them started from a different initial solution. Differentiation of initial solutions was made by running a sequential algorithm with a small number of iterations \(10i\), \(i=1,2,\ldots,p\), where \(p\) is the number of processors. To determine the values of the parameters of approximation algorithms, preliminary calculations were made on a small number of randomly determined examples. Based on the analysis of the results obtained, the following were adopted:  
* length of tabu list: 7,
* length of the list for a long-term memory: 5,
* algorithm for determining the startup solution: META,
* algorithm's stop condition: computation time \(t=120\) s.  
As the solution of the parallel algorithm there was the best solution obtained by individual processors. The percentage relative error was determined for each solution:  
\[PRD=\frac{F_{ref}-F_{alg}}{F_{ref}}\cdot 100\%, \tag{11}\]  
where:  
\(F_{ref}\)--value of the reference solution obtained with META algorithm,  
\(F_{alg}\)--the value of the solution determined by tested algorithm. Table 2 contains PRD improvement values relative to the solution obtained by the META algorithm, which is also a starting solution for TSA (that is why they are negative) for bigger instances of the sizes (\(n=200\), \(500\) and \(1000\)). \begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**Instance Group** & \(SWPT\) & \(COVERT\) & \(AU\) & \(EDD\) & \(META\) \\ \hline \(wt40\) & 579.92 & 152.39 & 15.77 & 138.55 & 10.46 \\ \(wt50\) & 4315.94 & 951.99 & 21.93 & 155.21 & 10.21 \\ \(wt100\) & 4692.65 & 1417.07 & 23.64 & 143.28 & 12.90 \\ \hline average & 3196.17 & 840.49 & 20.45 & 145.68 & 11.19 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: PRD [%] to the best-known solutions for SWPT, EDD, COVERT, AU and META algorithms.