Project Topics
Get Complete Project Material File(s) Now! »
Energy Minimization without Preemptions
In this section, we turn our attention to the non-preemptive energy minimization problem S, 1|rj, dj|E. First, we show that the ratio between the energy consumption of any optimal non-preemptive schedule and the energy consumption of an optimal preemptive schedule can be (nα−1). Next, we propose an (1 + wmax wmin )α-approximation algorithm which is based on the idea of transforming an optimal preemptive schedule to a non-preemptive one, where wmax = maxJj∈J {wj} and wmin = minJj∈J {wj}. This algorithm is 2α-approximate for equal-work instances. Finally, we present another 2α−1ρ- approximation algorithm for S, 1|rj, dj|E which uses as a black box any ρ-approximation algorithm for the multiprocessor non-migratory preemptive energy minimization problem S,P|ri,j, di,j,pmtn|E.
In the problem S, 1|rj, dj|E, there is a set of jobs J = {J1, J2, . . . , Jn} which have to be executed non-preemptively on a single processor. The fact that we do not allow preemptions means that each job must be executed consecutively without any interruptions between its starting time and its completion time. Each job Jj ∈ J comes with anamount of work wj , a release date rj and a deadline dj . In a feasible schedule, every job Jj ∈ J is executed entirely during the interval [rj , dj).
From Single-Processor Preemptive Schedules
In the following theorem, we show that, for general instances, the ratio between the energy consumption of an optimal non-preemptive schedule to the energy consumption of an optimal preemptive one can be very large.
Theorem 2.1. The ratio of the energy consumption of an optimal non-preemptive schedule to the energy consumption of an optimal preemptive schedule of the single-processorenergy minimization problem can be (nα−1).
Proof. Consider the instance consisting of n − 1 unit-work jobs J1, J2, . . . , Jn−1 and the job Jn of work equal to n. Each job Jj , 1 ≤ j ≤ n − 1, has release date rj = 2j − 1 and deadline dj = 2j, while rn = 0 and dn = 2n − 1. The optimal preemptive schedule S∗ pr (see Figure 2.3) for this instance assigns to all jobs a speed equal to one. Each job Jj , 1 ≤ j ≤ n − 1, is executed during its whole active interval, while Jn is executed during the remaining n unit length intervals. The total energy consumption of this schedule is E∗ pr = (n − 1) · 1α + n · 1α.
From Multiprocessor Non-Migratory Preemptive Schedules
Next, we present a 2α−1ρ approximation algorithm for the non-preemptive problem S, 1|rj, dj|E which uses, as a black box, a ρ-approximation algorithm for the multiprocessor preemptive problem S,P|ri,j, di,j,pmtn|E. Our algorithm applies a first a transformation to the initial instance. Note that this transformation was first introduced in an algorithm of Antoniadis et al. [9] for the same problem. Then, we give a transformation to the heterogeneous multiprocessor speedscaling problem without migrations.
We consider the time points t0, t1, t2, . . . , tτ , tτ+1 as follows. Let t1 be the smallest deadline of any job in J , i.e. t1 = minJj∈J {dj}. Let R1 ⊆ J be the subset of jobs which are released before t1, i.e. R1 = {Jj ∈ J : rj < t1}. Next, we set t2 = minJj∈J \R1{dj} and R2 = {Jj ∈ J : t1 ≤ rj < t2}, and we continue this procedure until all jobs are assigned into a subset of jobs. Let τ be the number of subsets of jobs that have been created. Moreover, let t0 = minJj∈J {rj} and tτ+1 = maxJj∈J {dj}. The way we define the time points is depicted in the Figure 2.4.
Energy Minimization with Migrations and Preemptions
In this section, we consider the problem S,P|rj, dj, mgtn|E for which we propose two optimal polynomial time algorithms. The former one is based on a series of maximum flow computations while the latter one is based on a single minimum convex cost flow calculation.
In the problem S,P|rj, dj, mgtn|E, we have to schedule a set of n jobs J = {J1, J2, . . . , Jn} on a set of m parallel processors P = {P1, P2, . . . , Pm} so as to minimize the total energy consumption. Each job Jj ∈ J is specified by a work wj , a release date rj and a deadline dj and it must be entirely executed during the interval [rj , dj). We allow preemptions and migrations of the jobs, i.e. a job may be executed, suspended and resumed later from the point of suspension on the same or on another processor. However, we do not allow parallel execution of a job. That is, each job can be executed by at most one processor at each time.
Optimal Algorithm based on Maximum Flow
In the following, we present a maximum flow based algorithm for S,P|rj, dj, mgtn|E. In order to establish this polynomial algorithm, we first formulate the problem as a convex program. This convex programming formulation gives a straightforward polynomial time algorithm for the problem because we can solve convex programs in polynomial time by applying the Ellipsoid algorithm. Next, we apply the KKT conditions to this convex program and we derive some necessary and sufficient conditions for optimality. Then, we define an optimal algorithm for the problem which always constructs a solution satisfying the KKT conditions. The algorithm is based on a series of repeated maximum flow computations on an appropriate graph.
We define the times t0 < t1 < . . . < tτ so that there is exactly one time tk, 0 ≤ k ≤ τ for every possible release date and deadline. Note that τ = O(n). Let Ik = [tk−1, tk), for 1 ≤ k ≤ τ , and I = {I1, I2, . . . , Iτ}. We denote by |Ik| the length of the interval Ik, i.e. |Ik| = tk − tk−1. We say that the job Jj ∈ J is active during the interval Ik ∈ I if Ik ⊆ [rj , dj). Let A(Ik) the set of the jobs which are active during Ik. Additionally, let nk = |A(Ik)| be the number of the active jobs during Ik.
Next, we describe a problem which is a variation of our problem and we call it the Work Assignment Problem (or WAP). We have a set of n jobs J = {J1, J2, . . . , Jn}, a set of m parallel processors P = {P1, P2, . . . , Pm} and a set of τ disjoint intervals I = {I1, I2, · · · , Iτ}. Each job Jj is associated with an amount of work wj . For a given interval Ik ∈ I and a job Jj ∈ J there are two cases: either the job Jj can be executed during Ik or it cannot. In the first case, we say that Jj is active during Ik. Following our existing definition, we denote by A(Ik) and nk the set and the number of active jobs during Ik. During each interval Ik ∈ I there is a set P(Ik) of mk available processors. Preemptions and migrations of jobs are allowed but no parallel execution of a job is permitted. Moreover, we are given a speed value v. Our objective is to find whether or not there is a feasible schedule that executes all jobs in J with constant speed v. Note that a schedule is feasible if and only if each job is entirely executed during its active intervals and it is executed by at most one among the available processor at each time. Note that the WAP is a generalization of the multiprocessor feasibility scheduling problem P|rj, dj, mgtn|− where, given a set of jobs J = {J1, J2, . . . , Jn} such that each job Jj has a processing time pj , a release date rj and a deadline dj , and a set of identical parallel processors, we ask whether there exists a feasible preemptive and migratory schedule that executes each job between its release date and its deadline. The problem P|rj, dj, mgtn|− is almost the same as the WAP with the difference that, in the WAP, not all intervals have the same number of available processors. Note that each job has a fixed processing time in the WAP since the speed is part of the problem’s instance. The WAP is polynomially solvable by applying a variant of an optimal algorithm for P|rj, dj, mgtn|− (see [1]).
Table of contents :
1 Introduction
1.1 Energy and Thermal Models
1.2 Problem Definitions
1.3 Notation for Scheduling Problems
1.4 Algorithm Analysis
1.5 Related Work
1.6 Contributions
2 Single Processor
2.1 Energy Minimization with Preemptions
2.2 Energy Minimization without Preemptions
2.2.1 From Single-Processor Preemptive Schedules
2.2.2 From Multiprocessor Non-Migratory Preemptive Schedules
2.3 Maximum Lateness Minimization
2.3.1 Offline
2.3.2 Online
3 Homogeneous Parallel Processors
3.1 Energy Minimization with Migrations and Preemptions
3.1.1 Optimal Algorithm based on Maximum Flow
3.1.2 Optimal Algorithm based on Convex Cost Flow
3.2 Energy Minimization without Migrations or Preemptions
4 Heterogeneous Environments
4.1 Energy Minimization with Migrations and Preemptions
4.2 Energy Minimization without Migrations with Preemptions
4.3 Average Completion Time Plus Energy Minimization
5 Shop Environments
5.1 Energy Minimization in an Open Shop
5.1.1 Optimal Primal-Dual Algorithm
5.1.2 Experimental Evaluation of the Primal-Dual Algorithm
5.1.3 Optimal Algorithm based on Minimum Convex Cost Flow
5.2 Energy Minimization in a Job Shop
6 Temperature-Aware Scheduling
6.1 Makespan Minimization
6.1.1 Inapproximability
6.1.2 Approximation Algorithm based on a transformation to P||Cmax .
6.1.3 LPT oriented Approximation Algorithm
6.2 Maximum and Average Temperature Minimization
7 Conclusion
