# Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion
## 3 First Improvement Method, NEH-SS1
### Results and Discussion
The number of different possible job orders after job ranking (first sort), for each of [PERSON]'s benchmark problems, are presented in Table 2. It can be noted that, from the Ta001 to Ta060 problems, it is conceivable to test all of the possible initial orders with a computer, because the maximal number of permutation cases to be treated is 2304 (for the Ta_037 problem) and remains less than 100 in the wide majority of cases. However, for the problems with 100 or more jobs, it is far more complicated to test all of the possible permutation cases. Such instances will thus remain an ongoing source of difference between authors. In the following paragraphs, all the possible equivalent orders for problems with 20 and 50 jobs have been treated, thanks to the factorial basis decomposition. Improvement may or may not be significant in the function of how the first jobs ranking can be different. Impressive improvement is visible for problems with 50 jobs/5 machines due to the relatively higher number of job rankings tested (see Table 2). This comes at the cost of higher computing time. A total of 219 s were necessary to solve instance Ta037, and 36 s to solve Ta034, instead of between 1 and 9 s to solve the others. It is difficult to conclude whether a high number of possibilities improves accuracy. Even if a good improvement for problems of 50 jobs/10 machines (20.5%) can be observed, relatively weak improvements for other problems with a number of jobs fewer than 50 can also be noted. If the causality link between Table 2 and the results obtained with the SS1 heuristic presented in Table 3 is difficult to establish, an outstanding improvement for large problem instances can be noted. Testing all the possibilities indicates that they were reasonably effective. Thus, examination of this first improvement reaffirms that the NEH method is good and globally robust in terms of the first sort, at least in cases of up to 50 jobs. Nevertheless, even when the improvement is slight, it is useful to be able to propose an improvement to an already efficient method. Indeed, [PERSON] and [PERSON] presented NEH as the best existing heuristic for flowshop problems [3]. Thus, further improving the best existing heuristic is a \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**J/M**} & \multirow{2}{*}{**Benchmark**} & \multicolumn{2}{c}{**NEH**} & \multicolumn{2}{c}{**NEH-SS1**} & \multicolumn{2}{c}{**Improvement**} \\  & & **(\%)** & **(s)** & **(\%)** & **(s)** & **(\%)** \\ \hline
20/5 & Ta001-Ta010 & 3.11 & 0.0 & 3.02 & 0.0 & 2.9 \\
20/10 & Ta011-Ta020 & 4.50 & 0.0 & 4.50 & 0.0 & 0.0 \\
20/20 & Ta021-Ta030 & 3.76 & 0.0 & 3.76 & 0.0 & 0.0 \\
50/5 & Ta031-Ta040 & 0.52 & 0.0 & 0.27 & 28.6 (\({}^{\dagger}\)) & 48.1 (\({}^{\dagger}\)) \\
50/10 & Ta041-Ta050 & 3.66 & 0.0 & 2.91 & 1.3 & 20.5 \\
50/20 & Ta051-Ta060 & 6.39 & 0.0 & 5.94 & 1.5 & 7.0 \\ \hline
100/5 & Ta061-Ta070 & 0.44 & 0.0 & 0.32 & 2.0 & 27.3 \\
100/10 & Ta071-Ta080 & 2.00 & 0.0 & 1.81 & 2.6 & 9.5 \\
100/20 & Ta081-Ta090 & 5.27 & 1.0 & 4.95 & 4.3 & 6.1 \\
200/10 & Ta091-Ta100 & 1.14 & 7.0 & 0.99 & 25.9 & 13.2 \\
200/20 & Ta101-Ta110 & 3.46 & 10.1 & 3.26 & 39.1 & 5.8 \\
500/20 & Ta111-Ta120 & 1.65 & 157.4 & 1.48 & 429.0 & 10.3 \\ Average & & 2.99 & 2.77 & & 7.4 \\ \hline \hline \end{tabular} \({}^{(\dagger)}\) The surprising time result given for (50/5) problems requires explanation. This disproportional time is due to the fact that all possible equivalent jobs orders are treated; Table 2 shows that Ta037 comprises 2304 equivalent orders. Since all the possible orders up to the Ta060 problem are treated, these 2304 launches of the NEH method take an amount of time that is no longer negligible.  
\end{table} 
Table 3: NEH-SS1 improvement heuristic results (average relative percentage deviation (ARPD) in % and average CPU times in s). desirable result. Average improvement of 7.4% is obtained with the NEH-SS1 heuristic. In the next section, another improvement is proposed, which further improves these good results.