# Heuristics for a Two-Stage Assembly-Type Flow Shop with Limited Waiting Time Constraints
## 4 Computational Experiments
the comparison results, which shows the average percentage gaps of heuristic solutions from a solution using CPLEX, and Figure 11 represents the number of instances for which the heuristic solutions are better than or equal to the CPLEX solutions. The negative percentage gap indicates that the heuristic solutions are better than those of the CPLEX. Overall, the IG algorithm exhibited the best performance. For 179 out of 180 instances, IG found solutions better than or equal to those of CPLEX. Both algorithms were better than CPLEX, and SA outperformed GA. For the three levels of _tf,_ only a few changes were observed in all cases. This indicates that the proposed metaheuristics can find a solution close to an optimal solution within a short computation time for instances of up to \(n=50\). These experimental results verified the effectiveness and efficiency of the proposed metaheuristics. Meanwhile, MNEH showed percentage gaps of approximately 2% in Set A and less than 1% in Sets B and C. Although MNEH was overwhelmed by the metaheuristics, its performance is acceptable, bearing in mind that MNEH is a constructive heuristic. We also examined the performance of the heuristics on large instances with \(n=100\), \(200\), \(300\), \(400\), and \(500\). A summary of the comparison results is in Figure 12 which shows the RDI values of the heuristic algorithms and Figure 13 which represents the number of instances that the heuristic found the best solution. Overall, SA outperformed the other algorithms, and even SA\({}_{30}\) was better than GA\({}_{90}\) and IG\({}_{90}\). These results were remarkably different from those of the previous test with small instances of up to \(n=50\). This is probably because of the trade-off relationship between solution quality and computation time. In IG, the greedy reinsertion method checks all possible positions to find the best one, and thus, this mechanism is very effective in small instances. However, this technique becomes computationally burdensome when \(n\) increases. In contrast, the SA procedure, which uses only a local search method with insertion and interchange, is relatively simple. That is, SA generates a new solution by slightly changing the current solution, and the  
Figure 10: SA calibration. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Heuristic** & **Set A** & **Set B** & **Set C** \\ \hline MNEH & \(2.110\)1 & \(0.408\) & \(0.356\) \\ GA\({}_{30}\) & \(-1.299\) & \(-0.032\) & \(-0.121\) \\ GA\({}_{60}\) & \(-1.362\) & \(-0.035\) & \(-0.128\) \\ GA\({}_{90}\) & \(-1.393\) & \(-0.036\) & \(-0.130\) \\ IG\({}_{30}\) & \(-1.869\) &time to create a new solution rarely increases even if \(n\) increases. Therefore, in terms of the trade-off relation, it can be said that SA is much more effective and efficient. On the contrary, for the instances with \(m=(2\) and 5) of Sets B and C, there was no difference in the performance of all algorithms, including MNEH. However, for instances with \(m=10\), SA overwhelmed the other algorithms, and IG performed better than GA. A summary of the experimental results thus far reveals that attempts to improve the solution by changing the sequence slightly are desirable in this scheduling problem. In addition, we performed statistical tests to see statistically significant differences in the performance of the proposed metaheuristics. This test used RDI values obtained from GA\({}_{90}\), IG\({}_{90}\), and SA\({}_{90}\) on large-size instances of \(n\) = 100, 200, 300, 400, and 500. Figure 14 shows the 95% confidence interval for the mean RDIs of the algorithms. As shown in Figure 14, SA\({}_{90}\) performed significantly better in terms of the mean RDI. We also performed Kruskal-Wallis tests which is a non-parametric method. Table 9 shows the results of pairwise comparisons from the tests. For the tests in Set A, SA\({}_{90}\) significantly outperformed GA\({}_{90}\) and IG\({}_{90}\). However, there is no significant difference between SA and IG in Sets B and C. This is likely because the RDIs for \(m\) = 2 and 5 were zero.