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 are n jobs and m machines; each job j requires p j units of processing, and is to be processed on one machine without interruption; if it is assigned to machine i, which runs at a given speed s i , it takes p j =s i time units. There also is a partial order OE on the jobs, where j OE k implies that job k may not start processing until job j has been completed. We shall consider two objective functions: Cmax = max j C j , where C j denotes the completion time of job j, and P j w j C j , where w j is a weight that is given for each job j.