Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> The theory of deterministic sequencing and scheduling has expanded rapidly during the past years. In this paper we survey the state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory. Special cases considered are single machine scheduling, identical, uniform and unrelated parallel machine scheduling, and open shop, flow shop and job shop scheduling. We indicate some problems for future research and include a selective bibliography. <s> BIB001 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> The energy usage of computer systems is becoming an important consideration, especially for battery-operated systems. Various methods for reducing energy consumption have been investigated, both at the circuit level and at the operating systems level. In this paper, we propose a simple model of job scheduling aimed at capturing some key aspects of energy minimization. In this model, each job is to be executed between its arrival time and deadline by a single processor with variable speed, under the assumption that energy usage per unit time, P, is a convex function, of the processor speed s. We give an off-line algorithm that computes, for any set of jobs, a minimum-energy schedule. We then consider some on-line algorithms and their competitive performance for the power function P(s)=s/sup p/ where p/spl ges/2. It is shown that one natural heuristic, called the Average Rate heuristic, uses at most a constant times the minimum energy required. The analysis involves bounding the largest eigenvalue in matrices of a special type. <s> BIB002 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> We consider the problem of job scheduling on a variable voltage processor with d discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for n jobs in O(dnlog n) time. Previous approaches solve this problem by first computing the optimal continuous solution in O(n3) time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that O(nlog n) time is required, hence the algorithm is optimal for fixed d. <s> BIB003 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> Current dynamic voltage scaling techniques allow the speed of processors to be set dynamically to save energy consumption, which is a major concern in microprocessor design. A theoretical model for min-energy job scheduling was first proposed a decade ago, and it was shown that for any convex energy function, the min-energy schedule for a set of n jobs has a unique characterization and is computable in O(n3) time. This algorithm has remained as the most efficient known despite many investigations of this model. In this work, we give an algorithm with running time O(n2 log n) for finding the min-energy schedule. In contrast to the previous algorithm, which outputs optimal speed levels from high to low iteratively, our algorithm is based on finding successive approximations to the optimal schedule. At the core of the approximation is an efficient partitioning of the job set into high and low speed subsets by any speed threshold, without computing the exact speed function. <s> BIB004 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> 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 Pruhs et al. to give an arbitrarilygood approximation for scheduling equal-work jobs on a multiprocessor. <s> BIB005 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this article we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable-speed processor so as to minimize the total cost consisting of the energy consumption and the total flow time of all jobs. We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the article is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time. <s> BIB006 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> 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. <s> BIB007 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> Speed scaling is a power management technique that involves dynamically changing the speed of a processor. We study policies for setting the speed of the processor for both of the goals of minimizing the energy used and the maximum temperature attained. The theoretical study of speed scaling policies to manage energy was initiated in a seminal paper by Yao et al. [1995], and we adopt their setting. We assume that the power required to run at speed s is P(s) e sα for some constant α > 1. We assume a collection of tasks, each with a release time, a deadline, and an arbitrary amount of work that must be done between the release time and the deadline. Yao et al. [1995] gave an offline greedy algorithm YDS to compute the minimum energy schedule. They further proposed two online algorithms Average Rate (AVR) and Optimal Available (OA), and showed that AVR is 2α − 1 αα-competitive with respect to energy. We provide a tight αα bound on the competitive ratio of OA with respect to energy. We initiate the study of speed scaling to manage temperature. We assume that the environment has a fixed ambient temperature and that the device cools according to Newton's law of cooling. We observe that the maximum temperature can be approximated within a factor of two by the maximum energy used over any interval of length 1/b, where b is the cooling parameter of the device. We define a speed scaling policy to be cooling-oblivious if it is simultaneously constant-competitive with respect to temperature for all cooling parameters. We then observe that cooling-oblivious algorithms are also constant-competitive with respect to energy, maximum speed and maximum power. We show that YDS is a cooling-oblivious algorithm. In contrast, we show that the online algorithms OA and AVR are not cooling-oblivious. We then propose a new online algorithm that we call BKP. We show that BKP is cooling-oblivious. We further show that BKP is e-competitive with respect to the maximum speed, and that no deterministic online algorithm can have a better competitive ratio. BKP also has a lower competitive ratio for energy than OA for α ≥5. Finally, we show that the optimal temperature schedule can be computed offline in polynomial-time using the Ellipsoid algorithm. <s> BIB008 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> In this paper we investigate algorithmic instruments leading to low powerconsumption in computing devices. While previous work on energy-efficient algorithms has mostly focused on single processor environments, in this paper we investigate multi-processor settings. We study the basic problem of scheduling a set of jobs, each specified by a release time, a deadline and a processing volume, on variable speed processors so as to minimize the total energy consumption. We first settle the complexity of speed scaling with unit size jobs. More specifically, we devise a polynomial time algorithm for agreeable deadlines and prove NP-hardness results for arbitrary release dates and deadlines. For the latter setting we also develop a polynomial time algorithm achieving a constant factor approximation guarantee that is independent of the number of processors. Additionally, we study speed scaling of jobs with arbitrary processing requirements and, again, develop constant factor approximation algorithms. We finally transform our offline algorithms into constant competitive online strategies. <s> BIB009 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> The rapidly increasing energy consumption by computing and communications equipment is a significant economic and environmental problem that needs to be addressed. Ethernet network interface controllers (NICs) in the US alone consume hundreds of millions of US dollars in electricity per year. Most Ethernet links are underutilized and link energy consumption can be reduced by operating at a lower data rate. In this paper, we investigate adaptive link rate (ALR) as a means of reducing the energy consumption of a typical Ethernet link by adaptively varying the link data rate in response to utilization. Policies to determine when to change the link data rate are studied. Simple policies that use output buffer queue length thresholds and fine-grain utilization monitoring are shown to be effective. A Markov model of a state-dependent service rate queue with rate transitions only at service completion is used to evaluate the performance of ALR with respect to the mean packet delay, the time spent in an energy-saving low link data rate, and the oscillation of link data rates. Simulation experiments using actual and synthetic traffic traces show that an Ethernet link with ALR can operate at a lower data rate for over 80 percent of the time, yielding significant energy savings with only a very small increase in packet delay. <s> BIB010 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> We consider online scheduling algorithms in the dynamic speedscaling model, where a processor can scale its speed between 0 andsome maximum speed T. The processor uses energy at ratesαwhen run at speed s,where α> 1 is a constant. Most modern processorsuse dynamic speed scaling to manage their energy usage. This leadsto the problem of designing execution strategies that are bothenergy efficient, and yet have almost optimum performance. ::: ::: We consider two problems in this model and give essentiallyoptimum possible algorithms for them. In the first problem, jobswith arbitrary sizes and deadlines arrive online and the goal is tomaximize the throughput, i.e. the total size of jobs completedsuccessfully. We give an algorithm that is 4-competitive forthroughput and O(1)-competitive for the energy used. Thisimproves upon the 14 throughput competitive algorithm of Chan etal. [10]. Our throughput guarantee is optimal as any onlinealgorithm must be at least 4-competitive even if the energy concernis ignored [7]. In the second problem, we consider optimizing thetrade-off between the total flow time incurred and the energyconsumed by the jobs. We give a 4-competitive algorithm to minimizetotal flow time plus energy for unweighted unit size jobs, and a (2+ o(1)) α/ln α-competitivealgorithm to minimize fractional weighted flow time plus energy.Prior to our work, these guarantees were known only when theprocessor speed was unbounded (T= ∞) [4]. <s> BIB011 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> Server farms today consume more than 1.5% of the total electricity in the U.S. at a cost of nearly $4.5 billion. Given the rising cost of energy, many industries are now seeking solutions for how to best make use of their available power. An important question which arises in this context is how to distribute available power among servers in a server farm so as to get maximum performance. By giving more power to a server, one can get higher server frequency (speed). Hence it is commonly believed that, for a given power budget, performance can be maximized by operating servers at their highest power levels. However, it is also conceivable that one might prefer to run servers at their lowest power levels, which allows more servers to be turned on for a given power budget. To fully understand the effect of power allocation on performance in a server farm with a fixed power budget, we introduce a queueing theoretic model, which allows us to predict the optimal power allocation in a variety of scenarios. Results are verified via extensive experiments on an IBM BladeCenter. We find that the optimal power allocation varies for different scenarios. In particular, it is not always optimal to run servers at their maximum power levels. There are scenarios where it might be optimal to run servers at their lowest power levels or at some intermediate power levels. Our analysis shows that the optimal power allocation is non-obvious and depends on many factors such as the power-to-frequency relationship in the processors, the arrival rate of jobs, the maximum server frequency, the lowest attainable server frequency and the server farm configuration. Furthermore, our theoretical model allows us to explore more general settings than we can implement, including arbitrarily large server farms and different power-to-frequency curves. Importantly, we show that the optimal power allocation can significantly improve server farm performance, by a factor of typically 1.4 and as much as a factor of 5 in some cases. <s> BIB012 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> Energy use of computer communication systems has quickly become a vital design consideration. One effective method for reducing energy consumption is dynamic speed scaling, which adapts the processing speed to the current load. This paper studies how to optimally scale speed to balance mean response time and mean energy consumption under processor sharing scheduling. Both bounds and asymptotics for the optimal speed scaling scheme are provided. These results show that a simple scheme that halts when the system is idle and uses a static rate while the system is busy provides nearly the same performance as the optimal dynamic speed scaling. However, the results also highlight that dynamic speed scaling provides at least one key benefit - significantly improved robustness to bursty traffic and mis-estimation of workload parameters. <s> BIB013 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> Algorithmic solutions can help reduce energy consumption in computing environs. <s> BIB014 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> Numerous studies have shown that datacenter computers rarely operate at full utilization, leading to a number of proposals for creating servers that are energy proportional with respect to the computation that they are performing. In this paper, we show that as servers themselves become more energy proportional, the datacenter network can become a significant fraction (up to 50%) of cluster power. In this paper we propose several ways to design a high-performance datacenter network whose power consumption is more proportional to the amount of traffic it is moving -- that is, we propose energy proportional datacenter networks. We first show that a flattened butterfly topology itself is inherently more power efficient than the other commonly proposed topology for high-performance datacenter networks. We then exploit the characteristics of modern plesiochronous links to adjust their power and performance envelopes dynamically. Using a network simulator, driven by both synthetic workloads and production datacenter traces, we characterize and understand design tradeoffs, and demonstrate an 85% reduction in power --- which approaches the ideal energy-proportionality of the network. Our results also demonstrate two challenges for the designers of future network switches: 1) We show that there is a significant power advantage to having independent control of each unidirectional channel comprising a network link, since many traffic patterns show very asymmetric use, and 2) system designers should work to optimize the high-speed channel designs to be more energy efficient by choosing optimal data rate and equalization technology. Given these assumptions, we demonstrate that energy proportional datacenter communication is indeed possible. <s> BIB015 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> We study network optimization that considers power minimization as an objective. Studies have shown that mechanisms such as speed scaling can significantly reduce the power consumption of telecommunication networks by matching the consumption of each network element to the amount of processing required for its carried traffic. Most existing research on speed scaling focuses on a single network element in isolation. We aim for a network-wide optimization. Specifically, we study a routing problem with the objective of provisioning guaranteed speed/bandwidth for a given demand matrix while minimizing power consumption. Optimizing the routes critically relies on the characteristic of the speed-power curve f(s), which is how power is consumed as a function of the processing speed s. If f is superadditive, we show that there is no bounded approximation in general for integral routing, i.e., each traffic demand follows a single path. This contrasts with the well-known logarithmic approximation for subadditive functions. However, for common speed-power curves such as polynomials f(s) = μsα, we are able to show a constant approximation via a simple scheme of randomized rounding. We also generalize this rounding approach to handle the case in which a nonzero startup cost σ appears in the speed-power curve, i.e., f(s) = {σ + μsα, if s >; 0; 0, if s = 0. We present an O((σ/μ)1/α)-approximation, and we discuss why coming up with an approximation ratio independent of the startup cost may be hard. Finally, we provide simulation results to validate our algorithmic approaches. <s> BIB016 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> We consider the following variant of the speed scaling problem introduced by Yao, Demers, and Shenker. 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. Moreover, 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 Lp-norm objective. <s> BIB017 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> The Information and Communication Technology sector is considered to be a major consumer of energy and has become an active participant in Green House Gas emissions. Lots of efforts have been devoted to make network infrastructure and network protocols power-aware and green. Among these efforts, Adaptive Link Rate (ALR) is one of the most widely discussed approaches. This survey highlights the most recent ALR approaches with a brief taxonomy and the state of the art. <s> BIB018 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> While previous work on energy-efficient algorithms focused on assumption that tasks can be assigned to any processor, we initially study the problem of task scheduling on restricted parallel processors. The objective is to minimize the overall energy consumption while speed scaling (SS) method is used to reduce energy consumption under the execution time constraint (Makespan Cmax). In this work, we discuss the speed setting in the continuous model that processors can run at arbitrary speed in [smin,smax]. The energy-efficient scheduling problem, involving task assignment and speed scaling, is inherently complicated as it is proved to be NP-Complete. We formulate the problem as an Integer Programming (IP) problem. Specifically, we devise a polynomial time optimal scheduling algorithm for the case tasks have an uniform size. Our algorithm runs in O(mn3logn) time, where m is the number of processors and n is the number of tasks. We then present a polynomial time algorithm that achieves an approximation factor of $2^{\alpha-1}(2-\frac{1}{m^{\alpha}})$ (α is the power parameter) when the tasks have arbitrary size work. <s> BIB019 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> This paper investigates the problem of scheduling jobs on multiple speed-scaled processors, i.e., we have constant ?>1 such that running a processor at speed s results in energy consumption s ? 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, flow time, and weighted 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 ?. The generated schedule is without migration, but we compare it to an optimal schedule with migration. Hence, this result holds for migratory and non-migratory schedules. 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. <s> BIB020 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> Different from the previous work on energy-efficient algorithms, which focused on assumption that a task can be assigned to any processor, we study the problem of task Scheduling with the objective of Energy Minimization on Restricted Parallel Processors (SEMRPP). Restriction accounts for affinities between tasks and processors, that is, a task has its own eligible processing set of processors. It assumes all tasks have a prescribed deadline on the execution time. We study the processors run at a finite number of distinct speeds, and the processors cannot change its speed during the computation of a task. Our work is motivated by the practical variable voltage processors that they cannot run at arbitrary speed and the task may be failure if the processor adjusts its speed during the computation of the task. We assess the complexity of the problem and present a polynomial time approximation algorithm with a bounded factor related to the adjacent speed ratio. <s> BIB021 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> Despite some proposals for energy-efficient topologies, most of the studies for saving energy in data center networks are focused on traffic engineering, i.e., consolidating flows and switching off unnecessary network devices. The major weakness of this approach is network oscillation brought by the frequent change of network topology when traffic fluctuates very fast. In this paper, we propose to incorporate rate adaptation into green data center networks. With rate adaptive network devices, we aim at approaching network-wide energy proportionality by routing optimization. We formalize the problem with an integer program and propose an efficient approximation algorithm - TSRR, solving the problem quickly while guaranteeing a constant performance ratio. Extensive range of simulations confirm that more than 40% of the energy can be saved while introducing very slight stretch on network delay. <s> BIB022 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed scalable processors in a fully heterogeneous setting. For both the preemptive-non-migratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-non-migratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem. <s> BIB023 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> In this paper, we present an analytical framework for characterizing and optimizing the power-performance tradeoff in Software-as-a-Service (SaaS) cloud platforms. Our objectives are two-folded: 1) We maximize the operating revenue when serving heterogeneous SaaS applications with unpredictable user requests. 2) We minimize the power consumption when processing the user requests. To achieve these objectives, we construct a unified profit-maximizing objective to jointly consider revenue and cost in an economic view. An offline solution to maximize the supreme bound of the objective is first developed, to 1) justify the validity of our theoretical model, and 2) establish a benchmark to examine the effectiveness of other control solutions. As a highlight of our contributions, we take advantage of the Lyapunov optimization techniques to design and analyze an optimal yet practical control framework, which makes online decisions on request admission control, routing, and virtual machine (VMs) scheduling. Our control framework can accommodate a variety of design choices and operational requirements in a datacenter. Specifically, buffering facilities can be introduced to alleviate the bursty admitted requests and to improve the robustness of the system, and a power budget can be enforced to improve the datacenter performance (dollar) per watt. Our mathematical analyses and simulations have demonstrated both the optimality (in terms of the cost-effective power-performance tradeoff) and stability (in terms of robustness and adaptivity to time-varying and bursty user requests) achieved by our proposed control framework. <s> BIB024 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> We improve complexity bounds for energy-efficient non-preemptive scheduling problems for both the single processor and multi-processor cases. As energy conservation has become a major concern, traditional scheduling problems have been revisited in the past few years to take into account the energy consumption [1]. We consider the speed scaling setting introduced by Yao et al. [20] where a set of jobs, each with a release date, deadline and work volume, are to be scheduled on a set of identical processors. The processors may change speed as a function of time and the energy they consume is the \(\alpha \)th power of their speed integrated over time. The objective is then to find a feasible non-preemptive schedule which minimizes the total energy used. <s> BIB025 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> A. Dynamic Speed Scaling (SS) <s> 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 α units of energy per time unit, where α 1 is a small constant. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption to be 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. As the preemptive case is known to be polynomially solvable for both the single-processor and the multiprocessor case, we explore the idea of transforming an optimal preemptive schedule to a non-preemptive one. We prove that the preemptive optimal solution does not preserve enough of the structure of the non-preemptive optimal solution, and more precisely that the ratio between the energy consumption of an optimal non-preemptive schedule and the energy consumption of an optimal preemptive schedule can be very large even for the single-processor case. Then, we focus on some interesting families of instances: (i) equal-work jobs on a single-processor, and (ii) agreeable instances in the multiprocessor case. In both cases, we propose constant factor approximation algorithms. In the latter case, our algorithm improves the best known algorithm of the literature. Finally, we propose a (non-constant factor) approximation algorithm for general instances in the multiprocessor case. <s> BIB026
This scheme, which is also known as Dynamic Voltage and Frequency Scaling (DVFS), focuses on lowering the frequency/speed of devices to save energy. Dynamic speed scaling allows for power savings as power consumption is approximately proportional to the supply voltage or the device speed s (e.g., following the cube-root rule, s  , or a more general function f (s, α), where α is a constant power parameter) BIB002 ,  , BIB014 . The goal is to determine the processing speeds and job assignment to minimize the total energy cost and guarantee the prescribed performance constraints. Intensive research, initiated by Yao et al. BIB002 , has been conducted in pursuit of saving energy by speed scaling. Some efforts address the problem of scheduling via job deadlines BIB004 and the optimization of job flow times BIB006 . Other approaches consider the problem of makespan minimization BIB005 , incorporate precedence constraints defined between jobs BIB007 and account for affinities between jobs and processors BIB019 . The research on variablespeed architectures includes single processors BIB002 , BIB008 , parallel processors BIB009 , BIB020 , and network devices BIB010 , BIB016 , BIB023 with preemption or nonpreemption settings BIB017 , BIB026 . Some studies also have addressed realistic speed models in which only a finite set of discrete speed levels is available BIB003 , BIB021 or in which the speeds are bounded on an interval BIB011 . In addition, Bampis et al. BIB023 studied a heterogeneous multiprocessor preemptive problem, in which it was assumed that each processor had a different speed-to-power function. We can present all these efforts in a consistent fashion by extending the standard threefield notation of BIB001 ; we summarize the algorithmic results obtained for dynamic speed scaling in Tables I and II, and the  symbols used are defined in Table III . When a large-scale warehouse is considered, speed scaling is adopted to seek solutions for optimizing the energy consumption based on the current load BIB012 , BIB013 , BIB024 . Higher speeds allow for faster execution but also result in higher power consumption. Gandhi et al. BIB012 studied the problem of finding the optimal power allocating in terms of determining the optimal frequencies of the servers in a server farm to minimize mean response time after measuring the power-to-frequency relationship of each server for a given workload. The authors noted that use of the optimal power allocation significantly improved the response time, by a factor of typically 1.4 and, in some cases, as much as a factor of 5. In BIB013 , the authors considered how to balance the mean response time and mean energy consumption in processor sharing scheduling when dynamic speed scaling is applied to reduce energy consumption. They identified a scheme that provided results that were nearly identical to the optimal objective of dynamic speed scaling, i.e., that simultaneously minimized energy consumption and response time. Speed scaling has also been studied in the arbitration of power consumption and system throughput. In BIB024 , the authors provided a probabilistic framework in which online decisions were made on request for admission control, routing, and virtual machine (VM) allocation. They modeled a unified objective function to balance the power consumption of the servers and the system throughput for application requests. At the network level, an Adaptive Link Rate (ALR) can be applied on links to reduce energy consumption BIB018 , BIB010 , BIB015 , BIB022 . Gunaratne et al. BIB010 proposed a Markovian model to reduce the energy consumption of a typical Ethernet link by adaptively varying the link data rate in response to utilization. The authors found that their scheme allows an Ethernet link to operate at a lower data rate for more than 80% of the time, yielding approximately $70 million in energy savings per year BIB023 (12(1 + ǫ)) α−1 BIB025 Multiple homogeneous processors NP-hard BIB019 , BIB009 PTAS BIB019 , BIB009  NP-hard (m≥2) BIB009 α α 2 4α BIB009 , B ⌈α⌉ [27] Online α α 2 4α BIB009  Discrete speed scaling )  Multiple homogeneous processors BIB021  Multiple heterogeneous processors Discrete speed scaling Single processor BIB022 presented a rate-adaptation-based solution with the intent of approaching network-wide energy proportionality via routing optimization. The simulation results indicated that the scheme could achieve up to 40% energy savings while introducing a very slight increase in network delay.