Analysis of job insertion technique for different initial sequences in permutation flow shop scheduling problems Online publication date: Thu, 13-Aug-2015
by A. Baskar; M. Anthony Xavior
International Journal of Enterprise Network Management (IJENM), Vol. 6, No. 3, 2015
Abstract: A permutation flow shop scheduling problem involves the determination of the order of processing the required number of jobs having different processing times over different machines with an objective of minimising a performance parameter. For makespan minimisation, the problem is NP-complete and many heuristics have been developed over the years. It is generally accepted that the heuristic developed by Nawaz, Enscore and Ham (NEH heuristic) is the most efficient so far among the simple heuristics. NEH algorithm sorts the jobs in descending order of their total processing times. Initial sequence is constructed by selecting the first two jobs and other jobs are inserted one by one to obtain the makespan and the corresponding sequence. This paper analyses the powerful job insertion technique of NEH algorithm using different combinations of the total processing time and total machine idle time for different initial sequences. Taillard benchmark problems are used for the analysis.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Enterprise Network Management (IJENM):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com