An improved heuristic for permutation flowshop scheduling
by Uday Kumar Chakraborty, Dipak Laha
International Journal of Information and Communication Technology (IJICT), Vol. 1, No. 1, 2007

Abstract: Flowshop scheduling deals with determination of optimum sequence of jobs to be processed on some machines in a fixed order so as to satisfy certain scheduling criteria. The general problem of scheduling has been shown to be NP-complete. Exact algorithms, such as integer programming and branch-and-bound, guarantee optimality but do not yield the optimum solution in polynomial time even for problems of small size. Heuristics have been shown to yield good working solutions (not necessarily optimal) in reasonable time. Although much research on the flowshop problem has been done over several decades starting from Johnson's lgorithm, only a few good algorithms exist. The Nawaz-Enscore-Ham heuristic, used for minimisation of makespan, continues to be the most popular algorithm because of its simplicity, solution quality and time-complexity. In the present paper we have modified the NEH algorithm, achieving significant improvement in the quality of the solution while maintaining the same algorithmic complexity. The proposed approach derives its strength from the use of a population-based technique. Experimental comparisons have been made on a large number of randomly generated test problems of varying problem sizes. Our approach is shown to outperform both the original NEH and NEH's best-known competitor to date, the HFC heuristic. Statistical tests of significance are performed to substantiate the claims of improvement.

Online publication date: Thu, 19-Apr-2007

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
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 Information and Communication Technology (IJICT):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your 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