An energy-aware scheduling algorithm under maximum power consumption constraints

This research investigates the production scheduling problems under maximum power consumption constraints. Probabilistic models are developed to model dispatching-dependent and stochastic machine energy consumption. A multi-objective scheduling algorithm called the energy-aware scheduling optimization method is proposed in this study to enhance both production and energy efficiency. The explicit consideration of the probabilistic energy consumption constraint and the following factors makes this work distinct from other existing studies in the literature: 1) dispatching-dependent energy consumption of machines, 2) stochastic energy consumption of machines, 3) parallel machines with different production rates and energy consumption pattern, and 4) maximum power consumption constraints. The proposed three-stage algorithm can quickly generate near-optimal solutions and outperforms other algorithms in terms of energy efficiency, makespan, and computation time. While minimizing the total energy consumption in the first and second stages, the proposed algorithm generates a detailed production schedule under the probabilistic constraint of peak energy consumption in the third stage. Numerical results show the superiority of the scheduling solution with regard to quality and computational time in real problems instances from manufacturing industry. While the scheduling solution is optimal in total energy consumption, the makespan is within 0.6 % of the optimal on average.     

Resource scheduling based on energy consumption for sustainable manufacturing

The paper proposes an agent-based approach for measuring in real time energy consumption of resources in job-shop manufacturing processes. Data from industrial robots is collected, analysed and assigned to operation types, and then integrated in an optimization engine in order to estimate how alternating between makespan and energy consumption as objective functions affects the performances of the whole system. This study focuses on the optimization of energy consumption in manufacturing processes through operation scheduling on available resources. The decision making algorithm relies on a decentralized system collecting data about resources implementing thus an intelligent manufacturing control system; the optimization problem is implemented using IBM ILOG OPL.     

改进松鼠搜索算法求解分布式节能柔性调度

为了优化同时考虑最大完工时间和机器能耗的双目标分布式柔性作业车间调度问题,提出了一种改进的多目标松鼠搜索算法。引入了基于升序排列规则的转换机制,实现了松鼠位置向量与调度解之间的转换,并针对机器空闲时间设计了从半主动到主动的解码策略。针对不同优化目标设计了三种种群初始化策略。同时提出了动态捕食者策略来更好地协调算法的全局探索和局部开发能力。设计了四种领域搜索策略用于增加种群多样。20个实例上的实验结果验证了改进后的算法求得解的质量和多样性更好,从而证明了其可有效求解分布式节能柔性调度问题。     

基于多层虚拟拓扑节能的SDN数据中心网络流量调度算法

针对“富连接”数据中心网络在低负载时能源利用率较低的问题,提出一种节能的多层虚拟拓扑流量调度算法(EMV-SDN)。建立节能流量调度问题的整形线性规划(Integral Linear Programing,ILP)优化数学模型,使得在承载所有网络负载的前提下,网络能源消耗最小。提出节能的多层虚拟拓扑流量调度算法来求解数学优化模型,得到数据流的节能调度方案。通过休眠高层的虚拟拓扑和交换机端口实现节能,降低网络能源消耗。实验结果表明,在网络能耗和数据流平均完成时间等方面,EMV-SDN算法均优于ECMP(Equal-Cost Multi-Path Routing)以及Dijkstra最短路径算法。     

云计算环境下资源的节能调度

在云计算环境下,如何在有效地进行资源调度,缩短任务执行时间的同时,降低能耗,已经成为一个重要问题。对此,以任务执行时间与能耗作为优化目标,建立了一个节能调度模型,并通过采用特殊的种群初始化方法以及引入学习机制等方法对非支配排序遗传算法(NSGA-Ⅱ)进行改进,将其应用于云计算的节能调度问题。最后通过算例测试,验证了所提算法能够在减少任务执行时间的同时,有效降低能耗。     

An energy-efficient task scheduling for mobile devices based on cloud assistant

Mobile cloud computing is an emerging service model to extend the capability and the battery life of mobile devices. Mostly one network application can be decomposed into fine-grained tasks which consist of sequential tasks and parallel tasks. With the assistance of mobile cloud computing, some tasks could be offloaded to the cloud for speeding up executions and saving energy. However, the task offloading results in some additional cost during the communication between cloud and mobile devices. Therefore, this paper proposes an energy-efficient scheduling of tasks, in which the mobile device offloads appropriate tasks to the cloud via a Wi-Fi access point. The scheduling aims to minimize the energy consumption of mobile device for one application under the constraint of total completion time. This task scheduling problem is reconstructed into a constrained shortest path problem and the LARAC method is applied to get the approximate optimal solution. The proposed energy-efficient strategy decreases 81.93% of energy consumption and 25.70% of time at most, compared with the local strategy. Moreover, the applicability and performance of the proposed strategy are verified in different patterns of applications, where the time constraint, the workload ratio between communication and computation are various.     

Multi-objective energy aware multiprocessor scheduling using bat intelligence

In this paper, a new heuristic called bat intelligence (BI) is introduced for solving energy aware multiprocessor scheduling problems. Bat intelligence is a novel optimization method that models prey hunting behaviors of bats. Bat intelligence and genetic algorithm (GA) are used to solve single-objective multiprocessor scheduling problem using, makespan, tardiness, and energy consumption as objective functions. Bat intelligence shows considerable improvement in terms of solution quality when compared with GA. Different combinations of these objectives are used to solve bi-objective multiprocessor scheduling problems, (makespan vs. energy, and also tardiness vs. energy). Tri-objective multiprocessor scheduling problem is also presented at the end. To generate desirable efficient alternatives, a Normalized Weighted Additive Utility Function is used. Simulation shows that BI identifies a set of efficient solutions that correspond to the assigned weights. The computational simulation also shows conflicting relationships between makespan and energy, and also between tardiness and energy.     

Hybridization of Metaheuristics Based Energy Efficient Scheduling Algorithm for Multi-Core Systems

The developments of multi-core systems (MCS) have considerably improved the existing technologies in the field of computer architecture. The MCS comprises several processors that are heterogeneous for resource capacities, working environments, topologies, and so on. The existing multi-core technology unlocks additional research opportunities for energy minimization by the use of effective task scheduling. At the same time, the task scheduling process is yet to be explored in the multi-core systems. This paper presents a new hybrid genetic algorithm (GA) with a krill herd (KH) based energy-efficient scheduling technique for multi-core systems (GAKH-SMCS). The goal of the GAKH-SMCS technique is to derive scheduling tasks in such a way to achieve faster completion time and minimum energy dissipation. The GAKH-SMCS model involves a multi-objective fitness function using four parameters such as makespan, processor utilization, speedup, and energy consumption to schedule tasks proficiently. The performance of the GAKH-SMCS model has been validated against two datasets namely random dataset and benchmark dataset. The experimental outcome ensured the effectiveness of the GAKH-SMCS model interms of makespan, processor utilization, speedup, and energy consumption. The overall simulation results depicted that the presented GAKH-SMCS model achieves energy efficiency by optimal task scheduling process in MCS.     

学习驱动的分布式异构混合流水车间批量流能效调度优化

本文研究了分布式异构混合流水车间批量流能效调度问题, 其中每个工厂的加工效率不同, 工件可以分割成若干子批进入加工系统. 以最大完成时间和总能耗为优化目标, 建立了混合整数规划模型. 本文提出了一种学习驱动的多目标进化算法, 包括学习驱动的全局搜索和局部搜索. 引入Q学习作为学习引擎, 以种群和非支配解集的评价作为环境反馈信号, 通过不断的学习来动态指导搜索操作的选择; 基于问题特征, 设计了算法的状态集、动作集和奖励机制. Q学习的引入能够及时感知当前搜索的状态, 减少搜索操作的盲目性, 提高搜索的效率. 通过对仿真数据集的测试, 表明所提出算法能够有效地求解分布式异构混合流水车间批量流能效调度问题.     

CLPS-GA: A case library and Pareto solution-based hybrid genetic algorithm for energy-aware cloud service scheduling

Since the appearance of cloud computing, computing capacity has been charged as a service through the network. The optimal scheduling of computing resources (OSCR) over the network is a core part for a cloud service center. With the coming of virtualization, the OSCR problem has become more complex than ever. Previous work, either on model building or scheduling algorithms, can no longer offer us a satisfactory resolution. In this paper, a more comprehensive and accurate model for OSCR is formulated. In this model, the cloud computing environment is considered to be highly heterogeneous with processors of uncertain loading information. Along with makespan, the energy consumption is considered as one of the optimization objectives from both economic and ecological perspectives. To provide more attentive services, the model seeks to find Pareto solutions for this bi-objective optimization problem. On the basis of classic multi-objective genetic algorithm, a case library and Pareto solution based hybrid Genetic Algorithm (CLPS-GA) is proposed to solve the model. The major components of CLPS-GA include a multi-parent crossover operator (MPCO), a two-stage algorithm structure, and a case library. Experimental results have verified the effectiveness of CLPS-GA in terms of convergence, stability, and solution diversity.     

Multi-objective energy-efficient workflow scheduling using list-based heuristics

Workflow applications are a popular paradigm used by scientists for modelling applications to be run on heterogeneous high-performance parallel and distributed computing systems. Today, the increase in the number and heterogeneity of multi-core parallel systems facilitates the access to high-performance computing to almost every scientist, yet entailing additional challenges to be addressed. One of the critical problems today is the power required for operating these systems for both environmental and financial reasons. To decrease the energy consumption in heterogeneous systems, different methods such as energy-efficient scheduling are receiving increasing attention. Current schedulers are, however, based on simplistic energy models not matching the reality, use techniques like DVFS not available on all types of systems, or do not approach the problem as a multi-objective optimisation considering both performance and energy as simultaneous objectives. In this paper, we present a new Pareto-based multi-objective workflow scheduling algorithm as an extension to an existing state-of-the-art heuristic capable of computing a set of tradeoff optimal solutions in terms of makespan and energy efficiency. Our approach is based on empirical models which capture the real behaviour of energy consumption in heterogeneous parallel systems. We compare our new approach with a classical mono-objective scheduling heuristic and state-of-the-art multi-objective optimisation algorithm and demonstrate that it computes better or similar results in different scenarios. We analyse the different tradeoff solutions computed by our algorithm under different experimental configurations and we observe that in some cases it finds solutions which reduce the energy consumption by up to 34.5% with a slight increase of 2% in the makespan.     

Energy‐efficient scheduling algorithms for batch‐of‐tasks (BoT) applications on heterogeneous computing systems

One of the major design constraints of a heterogeneous computing system is optimal scheduling, that is, mapping of tasks on the processing nodes in order to optimize the QoS parameters. Because of the huge energy consumption by computing resources, negative environmental effects and reduced system reliability, energy has unavoidably been added as a new parameter to the list of QoS parameters. Energy optimization in scheduling strategies along with makespan makes it an even more challenging combinatorial optimization problem. This work proposes two energy‐aware scheduling algorithms G1 and G2 to schedule a batch‐of‐tasks, made of a collection of independent tasks, on heterogeneous processors in order to minimize the makespan and the energy consumption. The proposed algorithms schedule tasks based on weighted aggregation cost function to the appropriate processors followed by task migration phase designed to further minimize the makespan and the energy consumption. The study evaluates the performance of the proposed algorithms with some of the peers, that is, MinMin, MINSuff on account of makespan, energy consumption, flowtime, and utilization. An experimental study reveals that the proposed algorithm (G2) consistently performs better under various test conditions. Copyright © 2015 John Wiley & Sons, Ltd.     

遗传算法在考虑能耗的单机批调度中的应用

能耗总成本已成为生产调度中一个重要考虑因素,需要在最大完成时间和能耗总成本之间进行权衡,论文将遗传算法（GA）应用到考虑能耗的单机批调度中,并建立同时优化最大化完成时间和最小化能耗总成本的差异工件单机批调度模型.通过遗传算法在考虑能耗（CEC）和不考虑能耗（IEC）下求出非支配解集,利用工件分批的优化和对遗传选择算子的改进,以保证搜索的效率.实验结果表明,与IEC相比,在CEC下使用遗传算法求出的解效果更好,且随着问题规模的增大和工件加工功率的增加,所得解的优势更加明显.     

一种云工作流任务调度能效优化算法

工作流任务执行时带来的高能耗不仅会增加云资源提供方的经济成本,而且会降低云系统的可靠性。为了满足截止时间的同时,降低工作流执行能耗,提出一种工作流能效调度算法CWEES。算法将能效优化调度划分为三个阶段：初始任务映射、处理器资源合并和任务松驰。初始任务映射旨在通过任务自底向上分级排序得到任务调度初始序列,处理器资源合并旨在通过重用松驰时间合并相对低效率的处理器,降低资源使用数量,任务松驰旨在为每个任务重新选择带有合适电压/频率等级的最优目标资源,在不违背任务顺序和截止时间约束前提下降低工作流执行总能耗。通过随机工作任务模型对算法的性能进行了仿真实验分析。结果表明,CWEES算法不仅资源利用率更高,而且可以在满足截止时间约束下降低工作流执行能耗,实现执行效率与能耗的均衡。     

基于多频段传感器辅助认知无线电网络的高能效传感器调度算法

在传感器协助认知无线电网络中,传统的高能效传感器调度问题只考虑了一个频段。多频段的传感器调度问题有许多新的研究领域。建立了一种多频段传感器调度问题的模型,提出了一种用于提高认知网络通信容量的基于遗传算法的高能效调度算法。模型考虑了传感器切换频段的能量消耗。在问题模型中,认知基站基于提高能效的目标为每个频段分配一组传感器进行协作感知。基于遗传算法的高能效调度算法通过优化传感器的调度使认知网络达到最大的通信容量,从而达到高能效的目标。仿真结果表明,本文的算法可以比贪心算法以及其他算法取得更高的网络通信容量。     

A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems

In this paper, we investigate the problem of scheduling precedence-constrained parallel applications on heterogeneous computing systems (HCSs) like cloud computing infrastructures. This kind of application was studied and used in many research works. Most of these works propose algorithms to minimize the completion time (makespan) without paying much attention to energy consumption.We propose a new parallel bi-objective hybrid genetic algorithm that takes into account, not only makespan, but also energy consumption. We particularly focus on the island parallel model and the multi-start parallel model. Our new method is based on dynamic voltage scaling (DVS) to minimize energy consumption.In terms of energy consumption, the obtained results show that our approach outperforms previous scheduling methods by a significant margin. In terms of completion time, the obtained schedules are also shorter than those of other algorithms. Furthermore, our study demonstrates the potential of DVS.     

Yard crane scheduling in a container terminal for the trade-off between efficiency and energy consumption

Green transportation has recently been the focus of the transportation industry to sustain the development of global economy. Container terminals are key nodes in the global transportation network and energy-saving is a main goal for them. Yard crane (YC), as one type of handling equipment, plays an important role in the service efficiency and energy-saving of container terminals. However, traditional methods of YC scheduling solely aim to improve the efficiency of container terminals and do not refer to energy-saving. Therefore, it is imperative to seek an appropriate approach for YC scheduling that considers the trade-off between efficiency and energy consumption. In this paper, the YC scheduling problem is firstly converted into a vehicle routing problem with soft time windows (VRPSTW). This problem is formulated as a mixed integer programming (MIP) model, whose two objectives minimize the total completion delay of all task groups and the total energy consumption of all YCs. Subsequently, an integrated simulation optimization method is developed for solving the problem, where the simulation is designed for evaluating solutions and the optimization algorithm is designed for exploring the solution space. The optimization algorithm integrates the genetic algorithm (GA) and the particle swarm optimization (PSO) algorithm, where the GA is used for global search and the PSO is used for local search. Finally, computational experiments are conducted to validate the performance of the proposed method.     

Coalition theory based task scheduling algorithm using DLFC-NN model

Resource management and job scheduling are essential in today's cloud computing world. Due to task scheduling and users' diverse submission of large-scale requests, co-located VM instances negatively impacted the performance of leased VM instances. This workload further led to resource rivalry across co-located VMs. In order to address the aforementioned problems, numerous strategies have been presented, however, they fail to take the asynchronous nature of the cloud environment into account. To address this issue, a novel “CTA using DLFC-NN model” is proposed. This proposed approach combines the coalition theory and DLFC-NN techniques by including IRT-OPTICS for task size clustering, digital metrology based on ionized information (DMBII) for defect detection in virtue machines (VM), and the dynamic levy flight hamster optimization algorithm for processing time optimization of the clusters. However, the implementation of task scheduling in an online environment is limited by a number of presumptions or oversimplifications made by current scheduling systems. As a result, a unique coalition theory is applied to efficiently schedule activities. In addition, the DLFC-NN model is used to reduce resource consumption, span time, and be highly accurate and energy-efficient when working on both online and offline jobs. Nevertheless, while optimizing the clusters' overall execution time, earlier approaches only decreased the make-span time for task scheduling. However, the DLFC-NN model solves the computation problem by using a fully weighted bipartite graph and the pseudo method to determine the fitness of the least makespan time. The enhanced methodology used in this study reduces the scheduling cost and minimizes job completion times according to different task counts when compared to the existing techniques.     

移动网络中基于数据到达速率的数据传输能耗优化策略

数据传输能耗是移动网络能耗的重要部分,提高数据传输能耗效率是优化移动网络能耗的重要课题。考虑数据具有传输延时的要求,研究了基于数据到达速率的数据传输平均能耗最小化问题。利用无线信道质量随机变化的特征,构建基于数据到达速率的平均能耗最小化问题,然后将其转化为最优停止问题,证明最优停止规则存在。最后通过求解最优近视停止规则来获得各侦测时刻的最优传输速率阈值,实现基于数据到达速率的数据传输能耗优化策略。对提出的策略与其他策略就平均能耗、平均传递率和平均调度周期进行了仿真对比,结果表明提出的策略具有较小的平均能耗和较高的平均传递率,取得了较好的能耗优化效果。     

Multi-objective list scheduling of workflow applications in distributed computing infrastructures

Executing large-scale applications in distributed computing infrastructures (DCI), for example modern Cloud environments, involves optimization of several conflicting objectives such as makespan, reliability, energy, or economic cost. Despite this trend, scheduling in heterogeneous DCIs has been traditionally approached as a single or bi-criteria optimization problem. In this paper, we propose a generic multi-objective optimization framework supported by a list scheduling heuristic for scientific workflows in heterogeneous DCIs. The algorithm approximates the optimal solution by considering user-specified constraints on objectives in a dual strategy: maximizing the distance to the user’s constraints for dominant solutions and minimizing it otherwise. We instantiate the framework and algorithm for a four-objective case study comprising makespan, economic cost, energy consumption, and reliability as optimization goals. We implemented our method as part of the ASKALON environment (Fahringer et al., 2007) for Grid and Cloud computing and demonstrate through extensive real and synthetic simulation experiments that our algorithm outperforms related bi-criteria heuristics while meeting the user constraints most of the time.