Heuristic rules for tie-breaking in the implementation of the NEH heuristic for permutation flow-shop scheduling

Suchithra Rajendran, Chandrasekharan Rajendran and Rainer Leisten

International Journal of Operational Research, 2017, vol. 28, issue 1, 87-97

Abstract: In this paper, we propose two new heuristic tie-breaking rules in the implementation of the well-known NEH heuristic for permutation flow-shop scheduling. While implementing this heuristic, it is known that ties do frequently occur when the initial ordering of jobs is obtained and when the choice of the best partial sequence among the sequences having the same makespan is done. In this paper, we propose two heuristic tie-breaking rules called NEHMSWG and NEHMinS-PS. We investigate their performance and that of the best-known heuristic tie-breaking rule, relative to the optimal/best-known upper bounds on the makespan, by considering benchmark permutation flow-shop scheduling problem instances. The results of performance evaluation reveal that the proposed tie-breaking rules are simple and effective, and improve the solutions with respect to many problem instances in comparison to the best known heuristic rule reported in the literature.

Keywords: flowshop scheduling; makespan; NEH heuristic; tie-breaking rules; permutation flowshops; performance evaluation. (search for similar items in EconPapers)
Date: 2017
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=80597 (text/html)
Access to full text is restricted to subscribers.

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:ids:ijores:v:28:y:2017:i:1:p:87-97

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().