Open AccessRevisiting the NEH algorithm- the power of job insertion technique for optimizing the makespan in permutation flow shop scheduling
Author(s) -
A. Baskar
Publication year - 2016
Publication title -
international journal of industrial engineering computations
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.564
H-Index - 26
eISSN - 1923-2926
pISSN - 1923-2934
DOI - 10.5267/j.ijiec.2015.9.001
Subject(s) - job shop scheduling , heuristics , flow shop scheduling , mathematical optimization , minification , algorithm , computation , scheduling (production processes) , permutation (music) , mathematics , computer science , routing (electronic design automation) , computer network , physics , acoustics
Permutation flow shop scheduling problems have been an interesting area of research for over six decades. Out of the several parameters, minimization of makespan has been studied much over the years. The problems are widely regarded as NP-Complete if the number of machines is more than three. As the computation time grows exponentially with respect to the problem size, heuristics and meta-heuristics have been proposed by many authors that give reasonably accurate and acceptable results. The NEH algorithm proposed in 1983 is still considered as one of the best simple, constructive heuristics for the minimization of makespan. This paper analyses the powerful job insertion technique used by NEH algorithm and proposes seven new variants, the complexity level remains same. 120 numbers of problem instances proposed by Taillard have been used for the purpose of validating the algorithms. Out of the seven, three produce better results than the original NEH algorithm