# Near-Optimal Heuristics for Just-In-Time Jobs Maximization in Flow Shop Scheduling
## 5 Computational Experiments and Results
### Experiment 1: Relative Comparison of the Proposed Heuristics
#### Enumeration Method  
Step **E**numerate the \(n!\) possible sequences and consider the one with the best \(n_{\Pi T}\). Step **2**Apply the timing adjustment procedure. **Algorithm 12**. Pseudo-code of the enumeration method. Figure 2 graphically presents the results, with 95% confidence intervals of the average RPD obtained by each heuristic method for both Groups 1 and 2. The 95% confidence interval means that the results (RPD) of 95 cases among 100 are within the displayed range. The global analysis of results revealed that H6 clearly outperformed the other heuristics, with a RPD of 0.2% for both Groups 1 and 2 (as can be seen in Table 4) which indicates that it provided the best or very close to the best solutions for many cases. Figure 1: Example of different schedules with the same sequence of jobs: (**a**) only \(J_{3}\) is just-in-time; (**b**) \(J_{2}\) and \(J_{1}\) are just-in-time; and (**c**) \(J_{2}\) and \(J_{3}\) are just-in-time. Figure 2: Comparison of performances of heuristics by group with 95% confidence interval of average RPD: (**a**) related to EM for Group 1; and (**b**) related to the best H1–H10 solution for Group 2. The results from H6 were similar to those from H5 which ranked second for overall performance with RPDs of 0.4% in Group 1 and 0.3% in Group 2, as shown in Table 4. Both these heuristics considered the EDD rule as the initial order and iteratively placed the first tardy job at the end of the sequence. However, H6 also employed insertion and permutation neighborhood searches. Therefore, it can be seen that, although this improvement phase provided better performance, H6 had already produced very good results before the neighborhood searches (explained by the behavior of H5). Following the rankings, H2 and H1 were third and fourth, respectively, and both exhibited similar behavior by considering the EDD rule as the initial order and then employing the insertion method to construct the sequence. The difference between them is that H2 employs neighborhood searches before attempting to insert the new job in the partial sequence. In addition, it may be noted in Table 4 that the rankings for Groups 1 and 2 were almost the same, with the sole exception of the inversion between heuristics H8 and H10 in eighth and ninth places. Another observation is that, in the five worst methods, the deviations in Group 1 were much lower than those in Group 2 which indicated that there is a greater dispersion of solution quality for medium and large instances, as can be seen in Figure 2.  
The worst method was H7 which considered the MST rule as the initial order and iteratively placed the first tardy job at the end of the sequence. Although it is very similar to H5, as the only difference between them was in their initial orders (the EDD rule was used in H5), the discrepancies in their results were quite significant. This demonstrated that, of the two options used for the initial rule, the EDD was always more advantageous than the MST, as was obvious for every pair of heuristics which were only differentiated by these rules, that is, H1 and H3, H2 and H4, H5 and H7, H6 and H8, and H9 and H10. Tables 5-8 provide detailed average results for the instances according to the group and size for each heuristic considering different numbers of jobs and machines. As the number of jobs grows, the four best methods, H6, H5, H2 and H1, had relatively stable performances for Groups 1 (Table 5) and Group 2 (Table 6), with very low RPD values (below 1.5). The exception was H1 for Group 2 (Table 6), which had decreasing relative deviations ranging from 3.9% with 15 jobs to 0.6% with 100. The other heuristics had increasing RPD values with increasing numbers of jobs, except H7 and H8 for Group 2 which had decreasing values for instances with up to 100 jobs. Furthermore, H3 showed a slight decrease in instances with 15 to 50 jobs, and an increase in those with 80 and 100.