Multiprocessor scheduling: Combining LPT and MULTIFIT (Q1109673)

The paper considers the problem of scheduling a set of n independent jobs on m identical machines with the objective of minimizing the total finishing time. Two well-known heuristic algorithms, namely LPT and MULTIFIT, are reviewed with respect to their advantages and drawbacks. A new algorithm called COMBINE is proposed which uses the result of LPT as the incumbent and then applies MULTIFIT with fewer iterations. The performance of the proposed new algorithm is better than that of LPT becauses it uses LPT as an incumbent. Furthermore, it is shown that the error bound of the new algorithm is never worse than that of MULTIFIT. Although it is not known for the general multiprocessor problem how much improvement is obtained in the error bound for COMBINE over MULTIFIT, it is shown that the improvement is significant for the two-processor system. Empirical comparison results are finally provided.