# Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion
## 5 Conclusions  
In this paper, an examination was made of the flowshop scheduling problem and its resolution with the NEH method, which is the best heuristic method, to date, for solving this kind of problem. Two improvements are proposed for this method, based on its two independent phases where a choice between two equivalent possibilities has to be made. The first phase occurs when the jobs are sorted in decreasing order of total operating time. The second occurs recurrently in the method process when, at each step, insertions of a new job in the current partial sequence leading to the best partial makespan are kept.  
Equalities can occur during both procedures, and the improvement methods have been designed to be the least sensitive to the cases of equality. Factorial basis decomposition was introduced and developed in order to insure that all possible orders are tested for instances of small problems. For large problem instances, this factorial basis decomposition allows the random choice of particular orders from all of the possible options. NEH results were significantly improved with the research methods presented in this paper, which are easily implementable in already existing code. This improvement is one of the most significant enhancements to heuristic methods applied to flowshop scheduling since the work of [PERSON], [PERSON], and [PERSON] in 1983. Each of the two proposed methods significantly improves the quality of the solutions given by the original NEH algorithm. Moreover, the combination of the two improvement methods (NEH-SS) shows good efficiency and a global improvement of 19% compared to the classic NEH, as well as an average relative improvement compared to the best existing improvement methods of between 10% and 25% for large problem instances. Indeed, the improvement of NEH-SS1 method is further improved with the subsequent application of the NEH-SS2 method.  
In future work, the efficiency of this method could be further improved, especially in terms of computation time for the second choice improvement method. In particular, it would be of interest to detect, among all possibilities of jobs orders, the job orders that were most likely to result in an improvement, in order to reduce the number of tests and time taken to identify the best solutions, especially for big problems. More generally, due to the effectiveness of heuristic methods, hybrids with more generic meta-heuristics are promising, and this research would be an interesting approach to further improve the performance of global algorithms.  
Figure 3: ARPD (in %) of different improvement methods compared to [PERSON]’s benchmark problem sizes, and improvement percentage over the best of the other heuristics (in dotted line, secondary scale).  
**Author Contributions:** [PERSON] proposed the idea, designed and developed the programs as well as the computing tests. He prepared and wrote the original draft manuscript. [PERSON] acknowledged the ideas, supervised this work and the methodology, reviewed and edited the original draft manuscript. All authors have read and agreed to the published version of the manuscript.  
**Funding:** This research received no external funding.  
**Conflicts of Interest:** The authors declare no conflict of interest.