Break the Ties for NEH Heuristic in Solving the Permutation Flow Shop Problems

This study deals with the Permutation Flow Shop Scheduling Problem （PFSP） based on the maximum completion time （makespan）. NEH （ the algorithm of Nawaz, Eascore and Ham） is the concluded most efficient constructive method in solving this NP-hard problem. The principal features of its strengths are the initial arrangement of jobs and the job insertion phase. In some instances, ties will occur in both the initial permutation and the partial sequences. The problem of ties breaking may have a significant impact on the NEH performance, but evaluate all the ties will be non-polynomial in the worst case. Several kinds of methods are presented in the paper to break the ties in a quick time. Together with the basic one, all 22 methods are tested on the famous Taillard＇s benchmarks and the most suitable ties breaking policy is recommended.