Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem

The polynomial heuristic of Nawaz/Enscore/Ham (NEH) is one of the best heuristics to minimize makespan in static-deterministic permutation flowshop problems. The NEH approach consists of two steps: (1) the generation of an initial order of jobs with respect to an indicator value and (2) the iterative insertion of jobs into a partial sequence according to the initial order of step 1. We generalize this approach to minimization of makespan, idletime and flowtime, construct 177 different initial orders, and evaluate their performance in the NEH-insertion approach. Based on a comprehensive numerical study, we propose heuristics for all three objective functions that outperform significantly the compared literature-based heuristics.