A comprehensive review and evaluation of LPT, MULTIFIT, COMBINE and LISTFIT for scheduling identical parallel machines
by Dipak Laha; Dhiren Kumar Behera
International Journal of Information and Communication Technology (IJICT), Vol. 11, No. 2, 2017

Abstract: This paper addresses the problem of scheduling n independent jobs processed non-preemptively on m identical parallel machines with the objective of minimising makespan. We consider four popular construction algorithms, LPT, MULTIFIT, COMBINE, and LISTFIT from the literature, which are used for minimising makespan for solving identical parallel machine scheduling problems. The objectives of this study are two-fold: first, a critical review of previous literature of these algorithms for minimising makespan in parallel machine scheduling is reported; next, we present an experimental framework to investigate performance of these algorithms for a comprehensive comparative evaluation. The computational results reveal that LISTFIT performs best among the four algorithms in most of the problem instances considering different problem sizes. Regarding the computational times, it has been observed that LISTFIT due to its higher time complexity requires more time compared to those of MULTIFIT and COMBINE, whereas LPT consumes the least computational time.

Online publication date: Mon, 04-Sep-2017

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