We are given a set of @math jobs that have to be executed on a set of @math speed-scalable machines that can vary their speeds dynamically using the energy model introduced in [, FOCS'95]. Every job @math is characterized by its release date @math , its deadline @math , its processing volume @math if @math is executed on machine @math and its weight @math . We are also given a budget of energy @math and our objective is to maximize the weighted throughput, i.e. the total weight of jobs that are completed between their respective release dates and deadlines. We propose a polynomial-time approximation algorithm where the preemption of the jobs is allowed but not their migration. Our algorithm uses a primal-dual approach on a linearized version of a convex program with linear constraints. Furthermore, we present two optimal algorithms for the non-preemptive case where the number of machines is bounded by a fixed constant. More specifically, we consider: (a) the case of identical processing volumes, i.e. @math for every @math and @math , for which we present a polynomial-time algorithm for the unweighted version, which becomes a pseudopolynomial-time algorithm for the weighted throughput version, and (b) the case of agreeable instances, i.e. for which @math if and only if @math , for which we present a pseudopolynomial-time algorithm. Both algorithms are based on a discretization of the problem and the use of dynamic programming.
The multiple machine case where the preemption and the migration of jobs are allowed can be solved in polynomial time in @cite_24 , @cite_15 and @cite_22 . @cite_18 considered the multiple machine problem where the preemption of jobs is allowed but not their migration. They showed that the problem is polynomial-time solvable for agreeable instances when the jobs have the same processing volumes. They have also showed that it becomes strongly NP-hard for general instances even for jobs with equal processing volumes and for this case they proposed an @math -approximation algorithm. For the case where the jobs have arbitrary processing volumes, they showed that the problem is NP-hard even for instances with common release dates and common deadlines. proposed a @math -approximation algorithm for instances with common release dates, or common deadlines, and an @math -approximation algorithm for instances with agreeable deadlines. @cite_21 proposed a @math -approximation algorithm for general instances, where @math is the @math -th Bell number. Recently, the approximation ratio for agreeable instances has been improved to @math in @cite_10 . For the non-preemptive multiple machine energy minimization problem, the only known result is a non-constant approximation algorithm presented in @cite_10 .
@cite_18 @cite_22 @cite_21 @cite_24 @cite_15 @cite_10
2126119137 2049060423 1984630032 2041438374
This paper investigates the problem of scheduling jobs on multiple speed-scaled processors without migration, i.e., we have constant α > 1 such that running a processor at speed s results in energy consumption s#945; per time unit. We consider the general case where each job has a monotonously increasing cost function that penalizes delay. This includes the so far considered cases of deadlines and flow time. For any type of delay cost functions, we obtain the following results: Any β-approximation algorithm for a single processor yields a randomized βBα-approximation algorithm for multiple processors, where Bα is the αth Bell number, that is, the number of partitions of a set of size α. Analogously, we show that any β-competitive online algorithm for a single processor yields a βBα-competitive online algorithm for multiple processors. Finally, we show that any β-approximation algorithm for multiple processors with migration yields a deterministic βBα-approximation algorithm for multiple processors without migration. These facts improve several approximation ratios and lead to new results. For instance, we obtain the first constant factor online and offline approximation algorithm for multiple processors without migration for arbitrary release times, deadlines, and job sizes. All algorithms are based on the surprising fact that we can remove migration with a blowup of Bα in expectation. We investigate a very basic problem in dynamic speed scaling where a sequence of jobs, each specified by an arrival time, a deadline and a processing volume, has to be processed so as to minimize energy consumption. Previous work has focused mostly on the setting where a single variable-speed processor is available. In this paper we study multi-processor environments with m parallel variable-speed processors assuming that job migration is allowed, i.e. whenever a job is preempted it may be moved to a different processor. We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time. In contrast to a previously known strategy, our algorithm does not resort to linear programming. We develop a fully combinatorial algorithm that relies on repeated maximum flow computations. The approach might be useful to solve other problems in dynamic speed scaling. For the online problem, we extend two algorithms Optimal Available and Average Rate proposed by [16] for the single processor setting. We prove that Optimal Available is αα-competitive, as in the single processor case. Here α>1 is the exponent of the power consumption function. While it is straightforward to extend Optimal Available to parallel processing environments, the competitive analysis becomes considerably more involved. For Average Rate we show a competitiveness of (3 )α 2 + 2α. In this paper we investigate dynamic speed scaling, a technique to reduce energy consumption in variable-speed microprocessors. While prior research has focused mostly on single processor environments, in this paper we investigate multiprocessor settings. We study the basic problem of scheduling a set of jobs, each specified by a release date, a deadline and a processing volume, on variable-speed processors so as to minimize the total energy consumption. We consider the following offline variant of the speed scaling problem introduced by We are given a set of jobs and we have a variable-speed processor to process them. The higher the processor speed, the higher the energy consumption. Each job is associated with its own release time, deadline, and processing volume. The objective is to find a feasible schedule that minimizes the energy consumption. In contrast to , no preemption of jobs is allowed. Unlike the preemptive version that is known to be in P, the non-preemptive version of speed scaling is strongly NP-hard. In this work, we present a constant factor approximation algorithm for it. The main technical idea is to transform the problem into the unrelated machine scheduling problem with @math -norm objective.