# Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion
## 4 Second Improvement Method NEH-SS2
### Results and Discussion  
The algorithm NEH-SS2 was tested after the application of the first heuristic NEH-SS1. The NEH-SS2 heuristic was not tested in isolation because its results would have been exposed to the first bias treated with the NEH-SS1 heuristic. The results obtained with the values of _Size_LPS1_ equal to 2, 3, and 5 are presented in Table 4, under their respective NEH-SS2 (_Size_LPS1_) column, in terms of accuracy (in %) and computing time (in s). These results give both average relative percentage deviation (ARPD) over optimum and average CPU times, over the 10 problems per instance size of [PERSON]'s benchmarks [17]. The last column presents the improvement measured with the three proposed sizes of _Size_LPS1_, and is calculated with the following equation:  
\[\text{Improvement = [NEH - min(NEH-SS2(2); NEH-SS2(3); NEH-SS2(5))]/(NEH)} \tag{4}\]  
The experiments confirmed that the heuristic time is globally dependent and increases quickly with _Size_LPS1_. On average, with _Size_LPS1_ = 10, two hours are necessary to solve one problem with 500 jobs and 20 machines. However, the computing time does not vary significantly for the values of _Size_LPS1_ reported. For higher values of _Size_LPS1_, combinatory explosion occurs and computing time becomes unreasonable. For heuristic methods designed to treat operational level problems, it would be harmful to improve already efficient methods in terms of accuracy by too widely increasing the computing time. If the computing time is relatively acceptable up to 200 jobs, it becomes unreasonable for instances of 500 jobs. In terms of precision, NEH-SS2 further improved the results already obtained with NEH-SS1 with all the tested couples, for all the problem instances. This is already the case from _Size_LPS1_ = 2. For the problem instances with a high number of jobs, precision decreases when _Size_LPS1_ increases. On the contrary, for problem instances with a fewer number of jobs, variability of results as a function of _Size_LPS1_ is negligible. Indeed, for instances with a low numbers of jobs, values taken by _Size_LPS1_ are not limiting, and allow coverage of a significant portion of the total tree. This consideration becomes less true as the number of jobs increases. The order in which the jobs are considered in the NEH method seems to have greater influence on results as the number of jobs increases. For the use of this method, it can be recommended to set the value _Size_LPS1_ = 3, with the tests realized, in order not to be too time consuming. This choice seems to be the best compromise between gain in precision and computing time. With this combination, on average the two methods improve the existing method by 19%, with a best average relative percentage deviation of 2.42%. \begin{table}
\begin{tabular}{c c c c c c c c c c c c} \hline \hline  & \multicolumn{2}{c}{**NEH**} & \multicolumn{2}{c}{**NEH-SS1**} & \multicolumn{2}{c}{**NEH-SS2 (2)**} & \multicolumn{2}{c}{**NEH-SS2 (3)**} & \multicolumn{2}{c}{**NEH-SS2 (5)**} & \multicolumn{2}{c}{**Improvement**} \\ \hline
**J/M** & (\%) & (s) & (\%) & (s) & (\%) & (s) & (\%) & (s) & (\%) & (s) & (\%) \\
**20/5** & 3.11 & 0.0 & 3.02 & 0.0 & 2.58 & 0 & 2.58 & 0 & **2.40** & 0 & 22.8 \\
**20/10** & 4.50 & 0.0 & 4.50 & 0.0 & **3.61** & 0 & **3.61** & 0 & **3.61** & 0 & 19.8 \\
**20/20** & 3.76 & 0.0 & 3.76 & 0.0 & **3.14** & 0 & **3.14** & 0 & **3.14** & 0 & 16.5 \\
**50/5** & 0.52 & 0.0 & 0.27 & 28.6 (\({}^{\dagger}\)) & 0.27 & 124 & 0.27 & 128 & **0.26** & 196 & 50.0 \\
**50/10** & 3.66 & 0.0 & 2.91 & 1.3 & **2.53** & 6.5 & **2.53** & 6.7 & 2.60 & 9.1 & 30.9 \\
**50/20** & 6.39 & 0.0 & 5.94 & 1.5 & 5.78 & 5.6 & 5.78 & 5.9  
One weakness of this method is that it only partially takes into account the ranking bias; nonetheless, it is better than only taking one out of all possible sequences. [PERSON] et al.