Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Heuristic strategy for Energy Efficient Scheduling <s> We address the problem of scheduling directed a-cyclic task graph (DAG) on a heterogeneous distributed processor system with the twin objectives of minimizing finish time and energy consumption. Previous scheduling heuristics have assigned DAGs to processors to minimize overall run-time of the application. But applications on embedded systems, such as high performance DSP in image processing, multimedia, and wireless security, need schedules which use low energy too. ::: ::: We develop a new scheduling algorithm called Energy Aware DAG Scheduling (EADAGS) on heterogeneous processors that can run on discrete operating voltages. Such processors can scale down their voltages and slow down to reduce energy whenever they idle due to task dependencies. EADAGS combines dynamic voltage scaling (DVS) with Decisive Path Scheduling (DPS) to achieve the twin objectives. Using simulations we show average energy consumption reduction over DPS by 40%. Energy savings increased with increasing number of nodes or increasing Communication to Computation Ratios and decreased with increasing parallelism or increasing number of available processors. These results were based on a software simulation study over a large set of randomly generated graphs as well as graphs for real-world problems with various characteristics. <s> BIB001 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Heuristic strategy for Energy Efficient Scheduling <s> Precedence-constrained parallel applications are one of the most typical application model used in scientific and engineering fields. Almost all efforts, on this kind of applications, have focused on the minimization of makespan (completion time). It is only recently that much attention has been paid to energy consumption. In this paper, we address the precedence-constrained parallel applications on heterogeneous computing systems (HCSs). We propose a new bi-objective hybrid genetic algorithm that takes into account, not only makespan, but also energy consumption. This metaheuristic adopts dynamic voltage scaling (DVS) to minimize energy consumption. Our study provides promising results showing the significance and potential of DVS. The experimental results from our comparative evaluation study confirm the superior performance of our approach over the other known heuristics on the two criteria energy saving and completion time. <s> BIB002 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Heuristic strategy for Energy Efficient Scheduling <s> Temperature-constraint computing environments are emerging those years, especially in embedding computing. A game theoretic temperature-aware scheduling algorithm for multi-core systems is proposed in this paper, namely, GTFTTS (Generalized Tit-For-Tat Temperature-aware Scheduling). GTFTTS is designed to work in a resource-rich environment where resources always compete for tasks. A generalized Tit-for-Tat based method, where whether a core will corporate or not is decided by a hardness factor, is considered in this paper. The algorithm is implemented in our TASS simulator. Simulations results show that the proposed game can reduce the temperature difference between different group of cores which effectively avoids the local hotspot of a processor. <s> BIB003 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Heuristic strategy for Energy Efficient Scheduling <s> There is growing demand on datacenters to serve more clients with reasonable response times, demanding more hardware resources, and higher energy consumption. Energy-aware datacenters have thus been amongst the forerunners to deploy virtualization technology to multiplex their physical machines (PMs) to as many virtual machines (VMs) as possible in order to utilize their hardware resources more effectively and save power. The achievement of this objective strongly depends on how smart VMs are consolidated. In this paper, we show that blind consolidation of VMs not only does not reduce the power consumption of datacenters but it can lead to energy wastage. We present four models, namely the target system model, the application model, the energy model, and the migration model, to identify the performance interferences between processor and disk utilizations and the costs of migrating VMs. We also present a consolidation fitness metric to evaluate the merit of consolidating a number of known VMs on a PM based on the processing and storage workloads of VMs. We then propose an energy-aware scheduling algorithm using a set of objective functions in terms of this consolidation fitness metric and presented power and migration models. The proposed scheduling algorithm assigns a set of VMs to a set of PMs in a way to minimize the total power consumption of PMs in the whole datacenter. Empirical results show nearly 24.9% power savings and nearly 1.2% performance degradation when the proposed scheduling algorithm is used compared to when other scheduling algorithms are used. <s> BIB004 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Heuristic strategy for Energy Efficient Scheduling <s> Computation grids and computational clouds are becoming increasingly popular in the organizations which require massive computational capabilities. Building such infrastructures makes a lucrative business case, thanks to availability of cheap hardware components and affordable software. Maintaining computational grids or cloud, however, require careful planning as in such dedicated environments, round-the-clock availability of workstations is very crucial. Ensuring uninterrupted availability, not only demands mechanism for failover redundancy but also results in constant power drainage. The tradeoff between the cost and the performance is the constant dilemma that the operations of the data centers face today. In this paper, we propose various heuristics for power-aware scheduling algorithms for scheduling jobs with dependent tasks onto the computational grid. We formulate the problem as a multi-objective function which results in various cost-performance tradeoffs each lying within the solution boundary. <s> BIB005 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Heuristic strategy for Energy Efficient Scheduling <s> Large-scale distributed computing systems (LDSs), such as grids and clouds are primarily designed to provide massive computing capacity. These systems dissipate often excessive energy to both power and cool them. Concerns over greening these systems have prompted a call for scheduling policies with energy awareness (e.g., energy proportionality). The dynamic and heterogeneous nature of resources and tasks in LDSs is a major hurdle to be overcome for energy efficiency when designing scheduling policies. In this paper, we address the problem of scheduling tasks with different priorities (deadlines) for energy efficiency exploiting resource heterogeneity. Specifically, our investigation for energy efficiency focuses on two issues: (1) balancing the workload in the way utilization is maximized and (2) power management by controlling execution of tasks on processor for ensuring the energy is optimally consumed. We form a hierarchical scheduler that exploits the multi-core architecture for effective scheduling. Our scheduling approach exploits the diversity of task priority for proper load balancing across heterogeneous processors while observing energy consumption in the system. Simulation experiments prove the efficacy of our approach, and the comparison results indicate our scheduling policy helps improve energy efficiency of the system. <s> BIB006 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Heuristic strategy for Energy Efficient Scheduling <s> Power efficiency is one of the main challenges in large-scale distributed systems such as datacenters, Grids, and Clouds. One can study the scheduling of applications in such large-scale distributed systems by representing applications as a set of precedence-constrained tasks and modeling them by a Directed Acyclic Graph. In this paper we address the problem of scheduling a set of tasks with precedence constraints on a heterogeneous set of Computing Resources (CRs) with the dual objective of minimizing the overall makespan and reducing the aggregate power consumption of CRs. Most of the related works in this area use Dynamic Voltage and Frequency Scaling (DVFS) approach to achieve these objectives. However, DVFS requires special hardware support that may not be available on all processors in large-scale distributed systems. In contrast, we propose a novel two-phase solution called PASTA that does not require any special hardware support. In its first phase, it uses a novel algorithm to select a subset of available CRs for running an application that can balance between lower overall power consumption of CRs and shorter makespan of application task schedules. In its second phase, it uses a low-complexity power-aware algorithm that creates a schedule for running application tasks on the selected CRs. We show that the overall time complexity of PASTA is $$O(p.v^{2})$$ where $$p$$ is the number of CRs and $$v$$ is the number of tasks. By using simulative experiments on real-world task graphs, we show that the makespan of schedules produced by PASTA are approximately 20 % longer than the ones produced by the well-known HEFT algorithm. However, the schedules produced by PASTA consume nearly 60 % less energy than those produced by HEFT. Empirical experiments on a physical test-bed confirm the power efficiency of PASTA in comparison with HEFT too. <s> BIB007 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Heuristic strategy for Energy Efficient Scheduling <s> The sensitivity analysis of a Cellular Genetic Algorithm (CGA) with local search is used to design a new and faster heuristic for the problem of mapping independent tasks to a distributed system (such as a computer cluster or grid) in order to minimize makespan (the time when the last task finishes). The proposed heuristic improves the previously known Min-Min heuristic. Moreover, the heuristic finds mappings of similar quality to the original CGA but in a significantly reduced runtime (1,000 faster). The proposed heuristic is evaluated across twelve different classes of scheduling instances. In addition, a proof of the energy-efficiency of the algorithm is provided. This convergence study suggests how additional energy reduction can be achieved by inserting low power computing nodes to the distributed computer system. Simulation results show that this approach reduces both energy consumption and makespan. <s> BIB008
There are many energy efficient schedulings that adopted heuristic strategy (i.e., Power-Efficient Distributed Scheduling BIB004 , PASTA BIB007 , Power Aware PRISM BIB005 , Priority-Based Scheduling BIB006 , EADAG BIB001 , Bi-Objective Hybrid Genetic BIB002 , EETS  and 2 Phase Heuristic BIB008 ). By applying heuristic strategy, certain level of knowledge and experience need to be effectively guessed and achieved. Power-Efficient Distributed Scheduling by Sharifi et al. BIB004 proposed strategy of assigning a set of virtual machines (VMs) to physical machines (PMs) in data centers. Based on the authors, the 'blind consolidation' of VMs is one of the causes of energy wastage. The state of system in their work is calculated based on VMs and PMs Disk utilization. The consolidation fitness then determined the right VMs that need to be redistributed to other PMs, while the current PMs are switched off. The work proved that the scheduling approach is 24.9% better in energy efficiency compared to static assignment. By dynamically assigning VMs to PMs, scheduling performance improved, however the challenge is to determine the best VM due to unpredictable changes in the system workload. Power-Aware Solution to Scheduling of Precedenceconstrained Tasks (PASTA) proposed by Sharifi et al. BIB007 is based on Dynamic Voltage and Frequency Scaling (DVFS). Their versatile DVFS approach is able to utilize all processors even though not every processor in the distributed systems has the DVFS capability. In two phases, PASTA selects a subset of computing resources (CRs) from a pool of available CRs to balance between performance and energy consumption. Then, it uses low-complexity energy aware algorithm to create a schedule that executed jobs on the selected CRs. Based on their experiments, PASTA achieved 60% energy efficiency than Heterogeneous Earliest Finish Time (HEFT). However, PASTA's makespan is longer compared to HEFT's. It is because there is higher duration of time that an application spends in the selected CRs in PASTA and it affects the result. Power Aware PRISM by Aziz and El-Rewini BIB005 is based on Priority Scheduling in Management Architecture for Resource Services (PRISM) framework. They adopted various heuristic for energy-aware scheduling algorithms that employed multi-objective function for diverse efficiency-performance trade-offs. Their scheduling algorithms consist of three steps (i.e., job clustering, reevaluating to give better scheduling alternatives and selecting the best schedule). Power Aware PRISM provides 25% to 94% better energy consumption where 25% energy efficiency is based on performance heuristic while 94% assessing is based on minimum cost heuristic. However, the experiments have been conducted in a homogeneous environment where the time between machines transition is fixed. Priority-Based Scheduling by Hussin et al. BIB006 proposed task scheduling that caters different priorities (deadlines) while exploiting the heterogeneous resources. Their scheduling approach applied hierarchical scheduler by utilizing two levels of queues (i.e., global and local schedulers). The queue in the global scheduler follows first come first serve basis. The jobs are then categorized based on their deadlines; high, medium or low. Priority-Based scheduling is proven to achieve 30% to 50% better energy efficiency compared to random selection scheduling. This research successfully balanced the energy efficiency and processing performance as it applied priority queue. By categorizing the jobs in the local (priority) queue it contributes for better makespan. The queue waiting time is also reduced, hence it becomes possible to improve the resource utilization and to minimize energy consumption. Energy Aware Directed Acyclic Graph (EADAG) by Baskiyar et al. BIB001 proposed combination of Decisive Path Scheduling (DPS) and Dynamic Voltage Scaling (DVS) techniques for heterogeneous processors. The scheduling approach calculated the energy consumption rate based on processors idle time (i.e., the higher unutilized processors the more energy efficient). Particularly, the processors idle time increase when there are high numbers of processing nodes or communication to computation ratios. EADAG employed the DPS on the Directed Acyclic Graph for better makespan while applying the DVS for the slack time to achieve energy efficiency. EADAG is proven to be 40% more energy efficient than DSP with better makespan. The work, however, does not consider types of tasks (e.g., independent and interdependent). Bi-Objective Hybrid Genetic by Mezmaz et al. BIB002 used hybrid scheduling approach by combining genetic algorithm and energy-conscious scheduling heuristic (ECS). It inherits the strength of exploration in genetic algorithm (GA) and the strong heuristic capability in ECS. Their scheduling approach basically created the task parts of each gene, then formed the processor parts of these genes. Finally, it calculated the fitness of a solution in terms of energy consumption and makespan. The Bi-Objective Hybrid Genetic scheduling was able to achieve 47.49% energy efficiency. The high energy efficiency achieved in this scheduling strategy is related to the hybrid approach of GA and heuristic technique. However, based on the experiment results, the energy efficiency decreased as the number of tasks increased. This gap needs to be explored in order to tackle larger and more complex tasks in the real environment. Energy Efficient Task Scheduling (EETS) by Yao et al.  adopted the offloading process on Cloud and nonoffloading process for mobile devices. The scheduling algorithm decides whether to change offload or non-offload status that was based on data size, data source, data storage, data compression and bandwidth speed. EETS calculated energy consumption from both offloading and nonoffloading status, and then selected the lower energy consumption from the workload status for task execution. EETS was able to effectively reach 99% better performance compared to other scheduling algorithms in the experiments. The energy consumption of EETS depends on bandwidth, however, it is hard to determine its current state due to rapid bandwidth fluctuation. There is an opportunity to solve the issue by using compression technique. As high compression is able to reduce data size, thus it saves energy consumption in communication. 2Phase Heuristic (2PH) by Pinel et al. BIB008 based on MinMin heuristic adopted Parallel Asynchronous Cellular Genetic Algorithm (PA-CGA) in the scheduling approach. 2PH basically was executed on sequences of Min-Min and the local search operator called Highest To Lower Loaded (H2LL). The scheduling approach highlights the incorporation of low-energy computing nodes in heterogeneous distributed computing systems and its ability to improve energy efficiency. The approach was able to prevent overloading or overheating that was capable to impact the nodes lifetime. 2PH provides better energy consumption compared to Min-Min Heuristic. The scheduling was designed for independent tasks, therefore there is an opportunity to enhance the scheduling approach for dependence-constraint tasks as future work. Some of the researchers BIB005 BIB006 BIB008 BIB003 proposed an energy efficient scheduling and managed to reach an appropriate balance between the system performance and the energy consumption. However, the dynamicity and heterogeneity on their computing environment is limited to some extent. Table  1 summarizes the metrics and system behaviors from the above heuristic scheduling approaches to design the energy model. There are various energy models adopted by heuristic strategy for energy efficiency. Most of them take the resource utilization and idle time of resources in calculating energy consumption into account. For scheduling approaches that adopted the DVFS technique they have additional parameters such as voltage and frequency in their energy model. 