Title: A comprehensive review and evaluation of LPT, MULTIFIT, COMBINE and LISTFIT for scheduling identical parallel machines

Authors: Dipak Laha; Dhiren Kumar Behera

Addresses: Department of Mechanical Engineering, Jadavpur University, Kolkata 700032, India ' Department of Mechanical Engineering, Jadavpur University, Kolkata 700032, India

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.

Keywords: scheduling; parallel machine scheduling; makespan; optimisation; algorithm.

DOI: 10.1504/IJICT.2017.086246

International Journal of Information and Communication Technology, 2017 Vol.11 No.2, pp.151 - 165

Received: 22 Jul 2014
Accepted: 26 Oct 2014
Published online: 04 Sep 2017 *

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