text: 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.
  @cite_5: We consider the classical problem of scheduling parallel unrelated machines. Each job is to be processed by exactly one machine. Processing job j on machine i requires time p ij . The goal is to find a schedule that minimizes the l p norm. Previous work showed a 2-approximation algorithm for the problem with respect to the l ∞ norm. For any fixed l p norm the previously known approximation algorithm has a performance of θ(p). We provide a 2-approximation algorithm for any fixed l p norm (p>1). This algorithm uses convex programming relaxation. We also give a √ 2-approximation algorithm for the l 2 norm. This algorithm relies on convex quadratic programming relaxation. To the best of our knowledge, this is the first time that general convex programming techniques (apart from SDPs and CQPs) are used in the area of scheduling. We show for any given l p norm a PTAS for any fixed number of machines. We also consider the multidimensional generalization of the problem in which the jobs are d-dimensional. Here the goal is to minimize the l p norm of the generalized load vector, which is a matrix where the rows represent the machines and the columns represent the jobs dimension. For this problem we give a (d+1)-approximation algorithm for any fixed l p norm (p>1).
  @cite_9: We consider the power-aware problem of scheduling non-preemptively a set of jobs on a single speed-scalable processor so as to minimize the maximum lateness. We consider two variants of the problem: In the budget variant we aim in finding a schedule minimizing the maximum lateness for a given budget of energy, while in the aggregated variant our objective is to find a schedule minimizing a linear combination of maximum lateness and energy. We present polynomial time algorithms for both variants of the problem without release dates and we prove that both variants become strongly ( NP )-hard in the presence of arbitrary release dates. Moreover, we show that, for arbitrary release dates, there is no O(1)-competitive online algorithm for the budget variant and we propose a 2-competitive one for the aggregated variant.
  @cite_6: 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 extend the standard 3-field notation and denote this problem as Sm|prec, energy|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.
  @cite_11: 
summary: In Table , we summarize the most related results of the literature. Several other results concerning scheduling problems in the speed-scaling setting have been presented, involving the optimization of some QoS criterion under a budget of energy, or the optimization of a linear combination of the energy consumption and some QoS criterion (see for example @cite_9 @cite_5 @cite_6 ). The interested reader can find more details in the recent survey @cite_11 .