A new improved NEH heuristic for permutation flowshop scheduling problems

Weibo Liu, Yan Jin and Mark Price

International Journal of Production Economics, 2017, vol. 193, issue C, 21-30

Abstract: 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.

Keywords: Scheduling; Heuristic; Flowshop; Makespan (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527317301998
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:proeco:v:193:y:2017:i:c:p:21-30

DOI: 10.1016/j.ijpe.2017.06.026

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().