The permutation flow-shop scheduling problem (PFSP) is an important problem in production industry.The problem has been a subject of many research and various algorithms to solve PFSP have been developed over the years.The newly developed algorithms are usually tested on Taillard and VRF benchmarks and their results are compared using various measures that assess the size of error made by an algorithm and the computation time.In this paper, we propose two new measures to assess the quality of results of algorithms for solving PFSP with the makespan criterion.The first ARD.NEH measure gives similar results as the well known ARPD measure but is robust to updates of the best known solutions of benchmark problems.The second ARID measure is an intervalbased measure which is able to assess whether the good quality of an algorithm results stems from its good behavior of this algorithm for a few instances or from its good behavior for most instances.The computational experiments confirm the usefulness of the proposed quality measures.

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.