Heuristics for Scheduling Uniform Machines

A new Modified Longest Processing Time algorithm and an Iterated Local Search algorithm are developed for the scheduling problem in which independent jobs are nonpreemptively scheduled on uniform parallel machines with the objective of minimizing the makespan, i.e., the completion time of the last job. Our computational results show that the Modified Longest Processing Time algorithm is able to reduce the average error, to increase the number of optimal solutions, and to determine a greater number of best solutions with respect to the Longest Processing Time algorithm. Furthermore, the Iterated Local Search algorithm is shown to be effective in reducing the average error significantly and yielding optimal solutions in over 80% of the tested instances.