An improved NEH heuristic to minimize makespan for flow shop scheduling problems

Abstract

Flow shop scheduling problems with rudimentary criteria of minimum makespan are the most important investigated problems in the field of scheduling. Generally during the process of generating an optimal sequence, multiple partial sequences claiming the optimal value of makespan are observed. In this paper a novel tie-breaking rule to select one of the best optimal sequences out of all possible partial sequences is developed which then applied to Nawaz-Enscore-Ham (NEH) heuristic to solve the scheduling problems in permutation flowshop without increasing the computational complexity. The performance of proposed heuristic is tested with other existing tie-breaking heuristics of similar complexity over Taillard and VRF's instances. Computational results reveal that in terms of solution quality, the proposed heuristic outperforms over the other NEH based heuristics of the same complexity reported in literature.