An efficient approximation algorithm for minimizing makespan on uniformly related machines

We give a new and efficient approximation algorithm for scheduling precedence-constrained jobs on machines with different speeds. The problem is as follows. We are given n jobs to be scheduled on a set of in machines. Jobs have processing times and machines have speeds. It takes p(j)/s(i) units of time for machine i with speed s(i) to process job j with processing requirement p(j) Precedence constraints between jobs are given in the form of a partial order. If j