We consider offline scheduling algorithms that incorporate speed scaling to address the bicriteria problem of minimizing energy consumption and a scheduling metric. For makespan, we give linear-time algorithms to compute all non-dominated solutions for the general uniprocessor problem and for the multiprocessor problem when every job requires the same amount of work. We also show that the multiprocessor problem becomes NP-hard when jobs can require different amounts of work. For total flow, we show that the optimal flow corresponding to a particular energy budget cannot be exactly computed on a machine supporting arithmetic and the extraction of roots. This hardness result holds even when scheduling equal-work jobs on a uniprocessor. We do, however, extend previous work by to give an arbitrarily-good approximation for scheduling equal-work jobs on a multiprocessor.
Pruhs, van Stee, and Uthaisombut @cite_10 consider the laptop problem version of minimizing makespan for jobs having precedence constraints where all jobs are released immediately and @math . Their main observation, which they call the power equality , is that the sum of the powers of the machines is constant over time in the optimal schedule. They use binary search to determine this value and then reduce the problem to scheduling on related fixed-speed machines. Previously-known @cite_8 @cite_1 approximations for the related fixed-speed machine problem then give an @math -approximation for power-aware makespan. This technique cannot be applied in our setting because the power equality does not hold for jobs with release dates.
@cite_1 @cite_10 @cite_8
2012989825 2097541335 2607875432
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 m machines. Jobs have processing times and machines have speeds. It takes pj si units of time for machine i with speed si to process job j with processing requirement pj. Precedence constraints between jobs are given in the form of a partial order. If j?k, processing of job k cannot start until job j's execution is completed. The objective is to find a non-preemptive schedule to minimize the makespan of the schedule. Chudak and Shmoys (1997, “Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),” pp. 581?590) gave an algorithm with an approximation ratio of O(log m), significantly improving the earlier ratio of O(m) due to Jaffe (1980, Theoret. Comput. Sci.26, 1?17). Their algorithm is based on solving a linear programming relaxation. Building on some of their ideas, we present a combinatorial algorithm that achieves a similar approximation ratio but runs in O(n3) time. Our algorithm is based on a new and simple lower bound which we believe is of independent interest. We consider the problem of speed scaling to conserve energy in a multiprocessor setting where there are precedence constraints between tasks, and where the performance measure is the makespan. That is, we consider an energy bounded version of the classic problem Pm | prec | Cmax. We show that, without loss of generality, one need only consider constant power schedules. We then show how to reduce this problem to the problem Qm | prec | Cmax to obtain a poly-log(m)-approximation algorithm. 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=maxjCj, 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(logm)-approximation algorithm. We also show how to extend this result to obtain anO(logm)-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.