# Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times
## 5 Computational Experiments  
This section reports and analyzes the performance of the proposed algorithms through computational experiments on randomly generated problem instances. All the tested algorithms were coded in Java programming language, and the experiments were conducted on a personal computer with a 2.6 GHz CPU. To generate problem instances, (urgent and normal) jobs and limited waiting times were generated by the methods used in [25] and [28], respectively. Processing times were randomly generated from a discrete uniform distribution with a range of [1, 100], i.e., \(U[1,100]\). Let \(h\) be the proportion of urgent jobs to all jobs. For urgent jobs, three levels (0.3, 0.5 and 0.7) were considered for \(h\), and three levels (0.5, 0.7 and 0.9) were considered for the weight for total tardiness of urgent jobs (\(\alpha\)). The release times of urgent jobs were generated randomly from \(U[0,LB]\), where \(LB\) is a lower bound on the makespan of normal jobs. The lower bound is obtained by scheduling only normal jobs with [PERSON]'s rule [45], assuming that their waiting times are infinite. Note that if all release times are zero or greater than \(LB\), the problem can be solved more easily. In addition, limited waiting times were randomly generated from \(U[0,100]\). Prior to evaluating the proposed algorithms, calibration for the suggested two metaheuristic algorithms were performed to achieve better performance, because performance of metaheuristic algorithms generally depends on their parameters. For the calibration experiments, three levels of \(n\) = (50, 200, and 400) were considered, and three instances for each combination of (\(n\), \(h\), and \(\alpha\)) were generated. For the termination condition, the maximum computation time was set to 50\(n\) milliseconds. Because the IG and SA are stochastic algorithms, they can find a good or bad solution coincidentally. To avoid such a coincidental solution, both algorithms solved each instance three times independently, and the average objective value was used. In addition, to compare the objective values obtained by the algorithms, the relative deviation index (RDI) was used as a measure, defined as \((obj_{x}-obj_{min})/(obj_{max}-obj_{min})\) where \(obj_{x}\), \(obj_{min}\) and \(obj_{max}\) are the objective function value from algorithm \(x\), the minimum and the maximum, respectively. The proposed IG has only one parameter which is the destruction size, \(d\). To find the most appropriate value of \(d\) for the considered problem, eight IGs with different \(d\) = (4, 8, 10, 12, 14, 16, 18 and 20) were tested, respectively. Note that the original IG in [43] used \(d=4\), which showed the best performance in the computational experiment. The results are summarized in Figure 4 which shows the average RDIs. As shown in the figure, IG with \(d=14\) showed the lowest RDI, which means the best performance. Unlike the original IG, the RDI of IG with \(d=4\) was the highest among the test results. In addition, the _bath-curve_ was observed, meaning that both lower and higher values from \(d=14\) deteriorate the performance and hence 14 is validated for the appropriate destruction size. Consequently, \(d=14\) was used in the subsequent experiments. Figure 3: Procedure of the proposed SA algorithm. The proposed SA has two types of parameters: cooling ratio \(\gamma\) and epoch length \(E\). For the calibration, four levels of \(\gamma\) and \(E\) were considered, i.e., \(\gamma\) = (0.99, 0.993, 0.996, and 0.999) and \(E\) = (40, 80, 120, and 160). Hence, a total of 16 combinations were tested in this calibration. The results were summarized in Figure 5. Similar to the IG calibration, the bath-curves were observed for the cooling ratio and epoch length. Therefore, (\(\gamma\) and \(E\)) = (0.996 and 80) were used in the subsequent experiments. The performance of the proposed MIP was evaluated using a commercial optimization solver, CPLEX 12.10.