# Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times
## 5 Computational Experiments
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Algorithm** & \(n=10\) & \(20\) & \(30\) \\ \hline MEDD & 1.048 (0) 1  & 1.371 (0) & 2.711 (0) \\ NEH & 0.096 (4) & 0.158 (0) & 0.266 (0) \\ IG(50) & 0.003 (21) & \(-\)0.001 (20) & \(-\)0.007 (29) \\ IG(100) & 0.003 (21) & \(-\)0.001 (20) & \(-\)0.008 (30) \\ SA(50) & 0.006 (19) & 0.002 (16) & \(-\)0.001 (27) \\ SA(100) & 0.006 (19) & 0.002 (16) & \(-\)0.001 (27) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Performance of the heuristic algorithms (vs. CPLEX). measured by the relative percentage deviation (RPD), defined as \((obj_{x}-obj_{\min})/obj_{\min}\). The results are summarized in Table 4, which shows the average RPD. Overall, the proposed IG and SA outperformed by far TS from [26], except for only one case of (\(n=50\), \(h=0.5\), \(\alpha=0.9\)). Hence, we focused on the comparison between IG and SA. When the problem size is small and medium, IG found better solutions than SA, However, as the problem size increased, SA showed better performance than IG. This is probably because IG needs to check all insertion positions and this repeated procedure can be a significant computational burden for large size problems. In contrast, because SA generates a neighborhood solution with a simple insertion, the time to generate a new solution is almost the same for large size problems. According to the results, it can be said that IG is more efficient for a small size problem, whereas SA works better for a large size problem. Based on the results, we plotted the interaction between algorithms and problem parameters (\(n\), \(h\) and \(\alpha\)) to check the effect on the performance of the algorithms. The interval plots are given in Figure 6, the 95% confidence interval for the mean RDIs. For the number of jobs \(n\), as we stated, IG was better than SA with up to \(n=200\). However, SA outperformed IG in problem instances over \(n=300\). For the proportion (\(h\)) of urgent jobs to all jobs, SA showed better performance when \(h=0.3\) and \(0.5\). However, when \(h=0.7\), IG was superior to SA, and TS also showed good performance. In other words, three algorithms can be used in complement to one another when there are more urgent jobs than normal jobs. For the weight for total tardiness of urgent jobs (\(\alpha\)), SA and IG far outperformed TS, and SA performed a little better than IG. Finally, to see statistically significant differences in the performance of IG and SA, Kruskal-Wallis (KW) tests, which are non-parametric methods, were performed with a commercial statistical analysis problem SPSS. For these tests, instances were divided into two groups according to the number of jobs. This is because IG worked well on small sized instances, whereas SA performed better on large sized instances. Thus, one was a small group (\(n=10\), \(20\), \(30\), \(50\) and \(100\)), and the other was a large group (\(n=200\), \(300\), \(400\), and \(500\)). Since objective values have different scales according to \(n\), RPD values among IG(50), IG(100), SA(50) and SA(100) were set as the dependent variable for the tests. To perform the tests, a significance level was set to \(0.05\). In addition, to check the effectiveness of problem parameters (\(h\) and \(\alpha\)) on the performance of the proposed algorithms, KW tests were performed for (algorithms \(\times\)\(h\) values) and (algorithms \(\times\)\(\alpha\) values) as well as algorithms. For the small group, all \(p\)-values in the three KW tests were close to zero, i.e., less than the significance level. Detailed results were summarized in Table 5, which shows the results of pairwise comparisons from KW tests. The results confirmed a statistically significant difference between the performances of IG and SA. Thus, it can be said that IG is superior to SA for the small group. In addition, the performance of SA(50) and SA(100) was not different for the small group. Figure 6: Mean plots for interaction between algorithms and problem parameters. This problem can be extended in several directions in the future.