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

Authors: Suchithra Rajendran; Chandrasekharan Rajendran; Rainer Leisten

Addresses: Harold and Inge Marcus Department of Industrial and Manufacturing Engineering, Pennsylvania State University, University Park, State College, PA 16801, USA ' Department of Management Studies, Indian Institute of Technology Madras, Chennai – 600 036, India ' Faculty of Engineering Sciences – Industrial Engineering, University of Duisburg-Essen, 47048 Duisburg, Germany

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.

DOI: 10.1504/IJOR.2017.080597

International Journal of Operational Research, 2017 Vol.28 No.1, pp.87 - 97

Received: 15 Jun 2014
Accepted: 28 Jun 2014
Published online: 01 Dec 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article