Bounds on the performance of a heuristic to schedule precedence-related jobs on parallel machines

We propose a heuristic procedure that constructs a schedule for N unit jobs with arbitrary precedence on m identical processors in parallel. The criterion is the minimization of the total weighted completion times. The procedure translates the optimal solution on one processor into a solution on the m-processors. Two bounds on the worst-ease performance of the procedure are derived, with the second being the stronger of the two, but at the expense of requiring slightly more computing effort. In view of the fact that the one-processor solutions may be hard to obtain, the proposed heuristic is applied to one processor near optimal solutions and the experimental results presented indicate that the heuristic performs equally well.