Title: An improvement heuristic for permutation flow shop scheduling

Authors: Kewal Krishan Nailwal; Deepak Gupta; Kawal Jeet; Sameer Sharma

Addresses: Department of Mathematics, A.P.J. College of Fine Arts, Jalandhar, Punjab, India ' Department of Mathematics, M.M. University, Mullana, Ambala, Haryana, India ' Department of Computer Science, D.A.V. College, Jalandhar, Punjab, India ' Department of Mathematics, D.A.V. College, Jalandhar, Punjab, India

Abstract: An improvement heuristic algorithm is proposed in this paper for solving flow shop scheduling problem (F_m / prmu / C_max). To test its efficiency, firstly the performance of the proposed algorithm is done against the six heuristics existing in the literature including the best NEH heuristic on 120 Taillard benchmarks. Further, this set of 120 Taillard instances is increased to 266 benchmark problem instances which include Carlier's, some Reeves and some new hard VRF instances from Vallada et al. (2015). On these instances, the performance of the proposed algorithm is tested against the best NEH and the famous CDS heuristic with the best known upper bounds. Further, a brief analysis of the other heuristics and metaheuristics existing in literature is done on Taillard problem instances. The proposed heuristic outperforms all the heuristics reported in this paper.

Keywords: flow shop scheduling; makespan; heuristic; algorithm.

DOI: 10.1504/IJPMB.2019.097823

International Journal of Process Management and Benchmarking, 2019 Vol.9 No.1, pp.124 - 148

Received: 06 May 2016
Accepted: 03 Dec 2016
Published online: 13 Feb 2019 *

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