A New Improved NEH Heuristic for Permutation Flowshop Scheduling Problems

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.