Heuristics for scheduling unrelated parallel machines

The problem of non-preemptively scheduling jobs on unrelated parallel machines to minimize the maximum completion time is considered. Previous studies evaluate heuristic methods solely with respect to their worst-case performance. In this paper, however, the practical implementation and the likely performance of the heuristics is also taken into account. Special attention is given to two-phase heuristics which use linear programming in their first phase to schedule some of the jobs and then apply another heuristic in their second phase to schedule the remaining jobs. Also considered is a natural and easily implemented method known as the earliest completion time heuristic. Some impovement procedures whereby an attempt is made to reduce the maximum completion time of a heuristic schedule through the rescheduling of jobs, are also described. A report on extensive computational tests to evaluate the effectiveness of these heuristics is provided. Results indicate that, unless an improvement procedure is included, the quality of the heuristic schedules is rather unsatisfactory.