Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds

We present new approximation algorithms for the problem of scheduling precedence-constrained jobs on parallel machines that are uniformly related. That is, there arenjobs andmmachines; each jobjrequirespjunits of processing, and is to be processed on one machine without interruption; if it is assigned to machinei, which runs at a given speedsi, it takespj/sitime units. There also is a partial order ≺ on the jobs, wherej ≺ kimplies that jobkmay not start processing until jobjhas been completed. We consider two objective functions:Cmax = maxj Cj, whereCjdenotes the completion time of jobj, and ∑jwjCj, wherewjis a weight that is given for each jobj. For the first objective, the best previously known result is anOm-approximation algorithm, which was shown by Jaffe more than 15 years ago. We give anO(log m)-approximation algorithm. We also show how to extend this result to obtain anO(log m)-approximation algorithm for the second objective, albeit with a somewhat larger constant. These results also extend to settings in which each jobjhas a release daterjbefore which the job may not begin processing. In addition, we obtain stronger performance guarantees if there are a limited number of distinct speeds. Our results are based on a new linear programming-based technique for estimating the speed at which each job should be run, and a variant of the list scheduling algorithm of Graham that can exploit this additional information.