New priority rule for NEH algorithm to minimize makespan in flowshop scheduling

Permutation flowshop scheduling problem (PFSP) has drawn much attention in academia. With makespan criterion, PFSP is NP-hard and many well-known heuristics were developed to deal with the problem including Johnson’s rule,... [ view full abstract ]

Permutation flowshop scheduling problem (PFSP) has drawn much attention in academia. With makespan criterion, PFSP is NP-hard and many well-known heuristics were developed to deal with the problem including Johnson’s rule, Palmer, CDS and NEH, etc. Among these heuristics NEH is commonly regarded as the best constructive heuristic for PFSP. Several NEH-based heuristics were proposed by employing priority rules and tie-breaking rules. Popular ones are NEHKK1, NEH-D and NEHKK2 which have been widely used as benchmarks. In this paper, three new priority rules considering mean (AVG), standard deviation (STD), skewness (SKE) and kurtosis (KUR) of operation times are proposed for NEH modifications. And two hypotheses are developed that the job with larger skewness and lower kurtosis should be given high priority. Thus, a full picture of operation time distribution is depicted and used as priority rule. Test results show that the new priority rules are effective.