Improving N-NEH+ algorithm by using Starting Point method
Radosław Puka, Bartosz Łamasz, Iwona Skalna · Annals of Computer Science and Information Systems · 2022
The N-NEH+ algorithm is one of the most efficient construction algorithms for solving the permutation flow-shop problem with the makespan criterion.It extends the well-known NEH heuristic with the N-list technique.In this paper, we propose the Starting Point (SP) method that employs a new strategy for using the N-list technique.The SP method allows to obtain an algorithm that is a combination of NEH and an N-list-based algorithm.Extensive numerical experiments on the standard set of Taillard's and VRF benchmarks show that the SP method significantly improves the results (average relative percentage deviation) of the NEH and N-NEH+ algorithms.