A New Improved NEH Heuristic for Permutation Flowshop Scheduling Problems

Weibo Liu, Yan Jin, Mark Price

Research output: Contribution to journalArticlepeer-review

41 Citations (Scopus)
503 Downloads (Pure)


Job evaluation and differentiation are crucial in scheduling. Since jobs can be represented by vectors of processing times, the average, standard deviation, and skewness of job processing times can be defined as the moments of their probability distribution. The first and the second moments of processing times are effective in sorting jobs (Dong et al., 2008), however they are not yet optimized to characterize and differentiate distributions of similar jobs. In this paper, skewness is utilized for the first time to construct a new priority rule, which is applied to the Nawaz-Enscore-Ham (NEH) heuristic (Nawaz et al., 1983), for solving scheduling problems in permutation flowshops. A novel tie-breaking rule is also developed by minimizing partial system idle time without increasing computational complexity of the NEH heuristic, in order to further improve the heuristic performance. Computational results show that the new heuristic outperforms the best NEH-based heuristics reported in the literature in terms of solution quality.
Original languageEnglish
Pages (from-to)21-30
JournalInternational Journal of Production Economics
Early online date21 Jun 2017
Publication statusPublished - Nov 2017


Dive into the research topics of 'A New Improved NEH Heuristic for Permutation Flowshop Scheduling Problems'. Together they form a unique fingerprint.

Cite this