# Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings
## 5 Computer Experiments
We also observe that running times of the TS metaheuristic are much shorter than that of the B&B method, staying under 35 ms. In this test, \(\pi^{*}\) was the solution provided by B&B (i.e., the optimal solution). Thus, the TS metaheuristic on average provided solutions with a makespan under 2.3% away from optimum even for instances of size \(5\times 5\). For the second experiment, we used instance set B to compare four algorithms against each other. The algorithms are as follows:  
* TS metaheuristic from Section 4 employing the block swap move proposed in this paper. * Same as above, but employing the regular swap move. * Same as above, but employing the adjacent swap move. * The baseline GA metaheuristic from Section 4. Since GA is a probabilistic method, we have run it 10 times. The reported results are averaged over those 10 runs. The stopping condition in all four cases was a time limit. Moreover, for each instance, \(C_{\max}(\pi^{*}(I))\) was set to the best makespan found by those four algorithms in the given time limit. The results, averaged over instances for each size group, are shown in Table 4. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \multirow{2}{*}{\(n\times m\)} & \multicolumn{5}{c}{**Branch \& Bound**} & \multicolumn{3}{c}{**Tabu Search**} \\ \cline{2-7}  & \(\mathbf{T_{1}}\) & \(\mathbf{T_{2}}\) & \(\mathbf{T_{3}}\) & \(\mathbf{T_{4}}\) & \(\mathbf{T_{5}}\) & \(\mathbf{T^{\dagger}}\) & \(\mathbf{PRD^{\dagger}}\) \\ \hline \(4\times 4\) & 0.54 & 0.16 & 0.07 & 0.05 & 0.05 & 0.004 & 0.54 \\ \(4\times 5\) & 1.71 & 0.77 & 0.10 & 0.07 & 0.07 & 0.010 & 0.58 \\ \(5\times 4\) & 46.33 & 18.13 & 2.15 & 0.50 & 0.51 & 0.015 & 1.28 \\ \(5\times 5\) & 213.56 & 65.61 & 1.37 & 0.85 & 0.75 & 0.034 & 2.30 \\ \hline \end{tabular} \({}^{\dagger}\) Averaged over all instance groups 1–5 (the differences were insignificant).  
\end{table} 
Table 3: Average running times \(T\) (in seconds) and average \(PRD\) (in percent) for instances from groups 1–5 and set A. No PRD is reported for B&B, as it is an exact method. We observe that, for five size groups (marked by \(\dagger\) in the table), the best solution was always found by the TS method employing the block swap neighborhood. In fact, this method found the best solution out of all four algorithms in 523 out of 600 instances (87.17%). Moreover, \(PRD\) for that neighborhood did not exceed 1.65%, with an average of 0.35%. The most difficult instances for this neighborhood were the ones with \(m=5\). Without those, \(PRD\) for that neighborhood generally did not exceed 0.43. The next best algorithm was TS with adjacent swap move, followed by TS with a swap move and then finally by the GA method. However, average \(PRD\) values for those last three algorithms were dozens of times larger. These results indicate that the block elimination property from Theorem 2 was a deciding factor, allowing the TS method to outperform its other variants and the baseline GA method in the given time limit. Moreover, the TS method with block neighborhood converged very quickly, obtaining good solutions in under one second for instances of size up to \(100\times 10\) (1000 operations), meaning 75% of all instances. However, due to average neighborhood size, the total complexity of TS method is \(O(n^{2}m^{2})\), resulting in longer running times (up to 20 min) for largest instances. However, this is true for the remaining TS variants as well. To verify the statistical significance of the differences between the performances of the algorithms, a Wilcoxon signed-rank test was used. The results were grouped by the instance sizes, and then the algorithms were compared pairwise for each group. With significance \(p<0.05\) reported, for the majority of algorithms pairs, \(H_{0}\) was rejected. The three cases where the hypothesis could not be rejected are:  
* \(20\times 5\) group, TS with adjacent neighborhood and TS with swap neighborhood;
* \(50\times 5\) group, TS with block neighborhood and TS with adjacent neighborhood;
* \(100\times 5\) group, TS with block neighborhood and GA.