We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed s then the energy consumption is s^ per time unit, where >1. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption is minimized. While most previous works have studied the preemptive case of the problem, where a job may be interrupted and resumed later, we focus on the non-preemptive case where once a job starts its execution, it has to continue until its completion without any interruption. We propose improved approximation algorithms for particular instances of the multiprocessor non-preemptive speed-scaling problem.
As mentioned above, for the preemptive single-processor case, @cite_3 proposed an optimal algorithm for finding a feasible schedule with minimum energy consumption. Using an extension of the classical three-field notation, this problem can be denoted as @math . The multiprocessor case, @math , where there are @math available processors has been solved optimally in polynomial time when preemption and migration of jobs are allowed @cite_2 @cite_12 @cite_7 . The migration assumption means that a job may be interrupted and resumed on the same processor or on another processor. However, the parallel execution of parts of the same job is not allowed.
@cite_7 @cite_12 @cite_3 @cite_2
2789021212 1984630032 2099961254 2049060423
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. 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α. 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. In this paper we provide a tight bound for the price of preemption for scheduling jobs on a single machine (or multiple machines). The input consists of a set of jobs to be scheduled and of an integer parameter @math . Each job has a release time, deadline, length (also called processing time) and value associated with it. The goal is to feasibly schedule a subset of the jobs so that their total value is maximal; while preemption of a job is permitted, a job may be preempted no more than k times. The price of preemption is the worst possible (i.e., largest) ratio of the optimal non-bounded-preemptive scheduling to the optimal k-bounded-preemptive scheduling. Our results show that allowing at most k preemptions suffices to guarantee a Θ( +1 n, log_k+1 P ) @math . As part of the proof, we introduce the notion of the Bounded-Degree Ancestor-Free Sub-Forest (BAS). We investigate the problem of computing the maximal-value BAS of a given forest and give a tight bound for the loss factor, which is Θ(log_k+1 n)$ as well, where n is the size of the original forest and k is the bound on the degree of the sub-forest.