Received Sep 11, 2017; Revised Feb 6, 2018; Accepted Feb 27, 2018
This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1. Introduction
Identical parallel machine scheduling (IPMS) with the objective of minimizing the makespan is one of the combinational optimization problems. It is known to be NP-hard by Garey and Johnson [1] since it does not have a polynomial time algorithm. Exact algorithms such as branch and bound [2] and cutting plane algorithms [3] solve this type of IPM and find optimal solution for small size instances. As the problem size increases, the exact algorithms are inefficient and take much time to get a solution.
That disadvantages bring a need for heuristics and metaheuristics that give optimal or near optimal solution within a reasonable amount of time. Longest Processing Time Rule (LPT) proposed by Mokotoff [4] is the first heuristic applied in IPMS which has a tight worst case performance of bound of 4/3–1/3, where is the number of parallel machines. LPT is based on distributing jobs on machines according to maximum processing time and the remaining jobs go one by one to the least loaded machine until assigning all the jobs to the machines. The LPT heuristic performs well for makespan criteria but the solution obtained is often local optima. Later, Coffman et al. [5] proposed MULTIFIT algorithm that is based on techniques from bin-packing. Blackstone Jr. and Phillips [6] proposed a simple heuristic for improving LPT sequence by exchange jobs between processors to reduce makespan. Lee and Massey [7] combine two heuristics, LPT and MULTIFIT, to form a new one. The heuristic uses LPT heuristic as an initial solution for the MULTIFIT heuristic. The performance of the combined heuristic is better than LPT and the error bound is not worse than the MULTIFIT. Yue [8] proved the bound for MULTIFIT to be 13/11. Lee and Massey [9] extend the MULTIFIT algorithm and show that the error bound of implementing the algorithm is only 1/10. Garey and Johnson [1] proposed that 3-phase composite heuristic consists of constructive phase and two improvement phases with no preliminary sort of processing...
