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.     

Online optimization for scheduling preemptable tasks on IaaS cloud systems

In Infrastructure-as-a-Service (IaaS) cloud computing, computational resources are provided to remote users in the form of leases. For a cloud user, he/she can request multiple cloud services simultaneously. In this case, parallel processing in the cloud system can improve the performance. When applying parallel processing in cloud computing, it is necessary to implement a mechanism to allocate resource and schedule the execution order of tasks. Furthermore, a resource optimization mechanism with preemptable task execution can increase the utilization of clouds. In this paper, we propose two online dynamic resource allocation algorithms for the IaaS cloud system with preemptable tasks. Our algorithms adjust the resource allocation dynamically based on the updated information of the actual task executions. And the experimental results show that our algorithms can significantly improve the performance in the situation where resource contention is fierce.     

Reactive and energy-aware scheduling of flexible manufacturing systems using potential fields

This paper presents a reactive scheduling approach for flexible manufacturing systems, which integrates the overall energy consumption of the production. This work is justified by the growing needs of manufacturers for energy-aware control, due to new important environmental criteria, which holds true in the context of high reactivity. It makes production hard to predict. The proposed reactive scheduling model is based on potential fields. In this model, resources that sense the intentions from products are able to switch to standby mode to avoid useless energy consumption and emit fields to attract products. Simulations are provided, featuring three indicators: makespan, overall energy consumption and the number of resource switches. Real experiments were carried out to illustrate the feasibility of the approach on a real system and validate the simulation results.     

基于膜计算的蝙蝠算法在云计算资源调度的研究

如何进一步实现云计算环境下的资源利用最大化是目前研究的热点.建立云计算环境下的资源分配模型,云计算资源调度使用蝙蝠算法,同时引入膜计算概念,提出一种基于膜计算的蝙蝠算法,将膜系统内部分解为主膜和辅助膜,在辅助膜内进行蝙蝠的个体局部寻优,将优化后的个体传送到主膜间进行全局优化,从而达到了云计算资源优化分配要求.通过CloudSim平台与其他算法进行仿真对比表明算法提高了云计算环境下的系统处理时间和效率,使得云计算环境下的资源分配更加合理.     

Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints

This paper presents a novel, two-level mixed-integer programming model of scheduling N jobs on M parallel machines that minimizes bi-objectives, namely the number of tardy jobs and the total completion time of all the jobs. The proposed model considers unrelated parallel machines. The jobs have non-identical due dates and ready times, and there are some precedence relations between them. Furthermore, sequence-dependent setup times, which are included in the proposed model, may be different for each machine depending on their characteristics. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches or optimization tools is extremely difficult. This paper proposes an efficient genetic algorithm (GA) to solve the bi-objective parallel machine scheduling problem. The performance of the presented model and the proposed GA is verified by a number of numerical experiments. The related results show the effectiveness of the proposed model and GA for small and large-sized problems.     

基于改进粒子群算法的云计算任务调度算法

如何对任务进行高效合理的调度是云计算需要解决的关键问题之一,针对云计算的编程模型框架,在传统粒子群优化算法（PSO）的基础上,提出了一种具有双适应度的粒子群算法（DFPSO）。通过该算法不但能找到任务总完成时间较短的调度结果,而且此调度结果的任务平均完成时间也较短。仿真分析结果表明,在相同的条件设置下,该算法优于传统的粒子群优化算法,当任务数量增多时,其综合调度性能优点明显。     

基于改进GA的云计算任务调度算法

云计算通常需要处理大量的计算任务,任务调度策略在决定云计算效率方面起着关键作用。如何合理地分配计算资源,有效地调度任务运行,使所有任务运行完成所需的时间较短、成本较小是个重要的问题。提出一种考虑时间-成本约束的遗传算法(TCGA),通过此算法调度产生的结果不仅能使任务完成所需的时间较短,而且成本较小。通过实验,将TCGA与考虑时间约束的遗传算法(TGA)、考虑成本约束的遗传算法(CGA)进行比较,实验结果表明,该算法是云计算中一种有效的任务调度算法。     

A hybrid heuristic workflow scheduling algorithm for cloud computing environments

Cloud computing is a relatively new concept in the distributed systems and is widely accepted as a new solution for high performance and distributed computing. Its dynamisms in providing virtual resources for organisations and laboratories and its pay-per-use policy make it very popular. A workflow models a process consisting of a series of steps that shape an application. Workflow scheduling is the method for assigning each workflow task to a processing resource in a way that specific workflow rules are satisfied. Some scheduling algorithms for workflows may assume some quality of service parameter such as cost and deadline. Some efforts have been done on workflow scheduling on cloud computing environments with different service level agreements. But most of them suffer from low speed. Here, we introduce a new hybrid heuristic algorithm based on particle swarm optimisation (PSO) and gravitation search algorithms. The proposed algorithm, in addition to processing cost and transfer cost, takes deadline limitations into account. The proposed workflow scheduling approach can be used by both end-users and utility providers. The CloudSim toolkit is used as a cloud environment simulator and the Amazon EC2 pricing is the reference pricing used. Our experimental result shows about 70% cost reduction, in comparison to non-heuristic implementations, 30% cost reduction in comparison to PSO, 30% cost reduction in comparison to gravitational search algorithm and 50% cost reduction in comparison to hybrid genetic-gravitational algorithm.     

Dynamic power management in energy-aware computer networks and data intensive computing systems

Energy awareness is an important aspect of modern network and computing system design and management, especially in the case of internet-scale networks and data intensive large scale distributed computing systems. The main challenge is to design and develop novel technologies, architectures and methods that allow us to reduce energy consumption in such infrastructures, which is also the main reason for reducing the total cost of running a network. Energy-aware network components as well as new control and optimization strategies may save the energy utilized by the whole system through adaptation of network capacity and resources to the actual traffic load and demands, while ensuring end-to-end quality of service. In this paper, we have designed and developed a two-level control framework for reducing power consumption in computer networks. The implementation of this framework provides the local control mechanisms that are implemented at the network device level and network-wide control strategies implemented at the central control level. We also developed network-wide optimization algorithms for calculating the power setting of energy consuming network components and energy-aware routing for the recommended network configuration. The utility and efficiency of our framework have been verified by simulation and by laboratory tests. The test cases were carried out on a number of synthetic as well as on real network topologies, giving encouraging results. Thus, we come up with well justified recommendations for energy-aware computer network design, to conclude the paper.     

Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm

Purpose

The objective of this study is to optimize task scheduling and resource allocation using an improved differential evolution algorithm (IDEA) based on the proposed cost and time models on cloud computing environment.

Methods

The proposed IDEA combines the Taguchi method and a differential evolution algorithm (DEA). The DEA has a powerful global exploration capability on macro-space and uses fewer control parameters. The systematic reasoning ability of the Taguchi method is used to exploit the better individuals on micro-space to be potential offspring. Therefore, the proposed IDEA is well enhanced and balanced on exploration and exploitation. The proposed cost model includes the processing and receiving cost. In addition, the time model incorporates receiving, processing, and waiting time. The multi-objective optimization approach, which is the non-dominated sorting technique, not with normalized single-objective method, is applied to find the Pareto front of total cost and makespan.

Results

In the five-task five-resource problem, the mean coverage ratios C(IDEA, DEA) of 0.368 and C(IDEA, NSGA-II) of 0.3 are superior to the ratios C(DEA, IDEA) of 0.249 and C(NSGA-II, IDEA) of 0.288, respectively. In the ten-task ten-resource problem, the mean coverage ratios C(IDEA, DEA) of 0.506 and C(IDEA, NSGA-II) of 0.701 are superior to the ratios C(DEA, IDEA) of 0.286 and C(NSGA-II, IDEA) of 0.052, respectively. Wilcoxon matched-pairs signed-rank test confirms there is a significant difference between IDEA and the other methods. In summary, the above experimental results confirm that the IDEA outperforms both the DEA and NSGA-II in finding the better Pareto-optimal solutions.

Conclusions

In the study, the IDEA shows its effectiveness to optimize task scheduling and resource allocation compared with both the DEA and the NSGA-II. Moreover, for decision makers, the Gantt charts of task scheduling in terms of having smaller makespan, cost, and both can be selected to make their decision when conflicting objectives are present.     

Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems

This research compares the performance of various heuristics and one metaheuristic for unrelated parallel machine scheduling problems. The objective functions to be minimized are makespan, total weighted completion time, and total weighted tardiness. We use the least significant difference (LSD) test to identify robust heuristics that perform significantly better than others for a variety of parallel machine environments with these three performance measures. Computational results show that the proposed metaheuristic outperforms other existing heuristics for each of the three objectives when run with a parameter setting appropriate for the objective.     

基于改进蚁群算法的云计算任务调度

利用云中资源进行高效任务调度是保证云计算系统可靠运行的关键问题。提出一种基于改进蚁群优化算法的任务调度方法。算法采用蚂蚁系统的伪随机比例规则进行寻优,防止算法过快收敛到局部最优解,同时结合排序蚂蚁系统和最大最小蚂蚁系统的设计思想完成信息素更新,有效求解优化问题。实验结果显示,该算法具有很好的寻优能力,提高了云资源的利用率。     

云计算环境下基于路径优先级的任务调度算法

为了最小化云计算系统的任务调度长度,结合表启发式调度技术和任务复制的思想提出基于路径优先权的任务调度算法.采用一种新方法计算DAG图中任务节点及边的权值,从最高优先权的路径开始依次选择任务进行调度,并通过有选择性地复制任务节点的父任务来减少任务间信息传送的时间花费,最后将任务安排到使其执行完成时间最早的虚拟机上.通过随机产生的DAG图与HEFT算法进行对比分析,实验结果表明了该算法能获得较短的调度长度.     

Soft computing for scheduling with batch setup times and earliness-tardiness penalties on parallel machines

A model for scheduling grouped jobs on identical parallel machines is addressed in this paper. The model assumes that a set-up time is incurred when a machine changes from processing one type of component to a different type of component, and the objective is to minimize the total earliness-tardiness penalties. In this paper, the algorithm of soft computing, which is a fuzzy logic embedded Genetic Algorithm is developed to solve the problem. The efficiency of this approach is tested on several groups of random problems and shows that the soft computing algorithm has potential for practical applications in larger scale production systems.     

List scheduling with duplication for heterogeneous computing systems

Effective task scheduling is essential for obtaining high performance in heterogeneous computing systems (HCS). However, finding an effective task schedule in HCS, requires the consideration of the heterogeneity of computation and communication. To solve this problem, we present a list scheduling algorithm, called Heterogeneous Earliest Finish with Duplicator (HEFD). As task priority is a key attribute for list scheduling algorithm, this paper presents a new approach for computing their priority which considers the performance difference in target HCS using variance. Another novel idea proposed in this paper is to try to duplicate all parent tasks and get an optimal scheduling solution. The comparison study, based on both randomly generated graphs and the graphs of some real applications, shows that our scheduling algorithm HEFD significantly surpasses other three well-known algorithms.     

A semantic interoperability framework for software as a service systems in cloud computing environments

In cloud computing environments in software as a service (SaaS) level, interoperability refers to the ability of SaaS systems on one cloud provider to communicate with SaaS systems on another cloud provider. One of the most important barriers to the adoption of SaaS systems in cloud computing environments is interoperability. A common tactic for enabling interoperability is the use of an interoperability framework or model. During the past few years, in cloud SaaS level, various interoperability frameworks and models have been developed to provide interoperability between systems. The syntactic interoperability of SaaS systems have already been intensively researched. However, not enough consideration has been given to semantic interoperability issues. Achieving semantic interoperability is a challenge within the world of SaaS in cloud computing environments. Therefore, a semantic interoperability framework for SaaS systems in cloud computing environments is needed. We develop a semantic interoperability framework for cloud SaaS systems. The capabilities and value of service oriented architecture for semantic interoperability within cloud SaaS systems have been studied and demonstrated. This paper is accomplished through a number of steps (research methodology). It begins with a study on related works in the literature. Then, problem statement and research objectives are explained. In the next step, semantic interoperability requirements for SaaS systems in cloud computing environments that are needed to support are analyzed. The details of the proposed semantic interoperability framework for SaaS systems in cloud computing environments are presented. It includes the design of the proposed semantic interoperability framework. Finally, the evaluation methods of the semantic interoperability framework are elaborated. In order to evaluate the effectiveness of the proposed semantic interoperability framework for SaaS systems in cloud computing environments, extensive experimentation and statistical analysis have been performed. The experiments and statistical analysis specify that the proposed semantic interoperability framework for cloud SaaS systems is able to establish semantic interoperability between cloud SaaS systems in a more efficient way. It is concluded that using the proposed framework, there is a significant improvement in the effectiveness of semantic interoperability of SaaS systems in cloud computing environments.     

自愿计算环境下基于代理的自适应并行调度

描述了一个自愿计算环境下的基于代理的自适应并行调度模型,该调度代理处于服务器端与工作机端之间,可以缓解服务器端的访问竞争.在该调度模型中,服务器端直接把工作单元分配给调度代理,工作机从调度代理处获取工作单元;调度代理具有自适应并行性,高效率性,容错等特性.最后通过测试与性能分析验证了该调度模型的正确性与高效性.     

CloudChem—基于云计算的化学计量学软件服务

化学计量学被广泛应用于光谱、色谱及质谱数据处理,现有化学计量学软件都为串行单机程序,这将导致程序开发成本高、部署升级困难、可控制性差等缺点,难以胜任分析数据的成倍增长对快速分析和有效管理带来巨大的挑战。为了解决这些缺点,本文提出了CloudChem——1种基于云计算的化学计量学软件服务,它采用软件即服务的模式,使用浏览器/服务器结构来提供专业的化学计量学软件服务。系统的服务器端分为工作流层、业务层、计算层、数据层和Web层。数据层综合利用关系型数据库和分布式文件系统2种方法的优势来存储和组织数据;计算层使用并行计算来提升数据处理速度和规模;Web层使用Open API实现平台的数据资源共享功能。实验表明,平台上的并行交叉验证框架在四核CPU上加速比可以达到3.763倍。所以,CloudChem可以较好克服传统化学计量学软件的缺点,基于该方法的软件服务平台可实现光谱、色谱、核磁、质谱等数据的有效、高速、一体化的存储、分析、挖掘,最大限度减小用户在使用化学计量软件的基础设施成本和软件成本。     

Multi-objective metaheuristic algorithms for the resource-constrained project scheduling problem with precedence relations

This study addresses the resource-constrained project scheduling problem with precedence relations, and aims at minimizing two criteria: the makespan and the total weighted start time of the activities. To solve the problem, five multi-objective metaheuristic algorithms are analyzed, based on Multi-objective GRASP (MOG), Multi-objective Variable Neighborhood Search (MOVNS) and Pareto Iterated Local Search (PILS) methods. The proposed algorithms use strategies based on the concept of Pareto Dominance to search for solutions and determine the set of non-dominated solutions. The solutions obtained by the algorithms, from a set of instances adapted from the literature, are compared using four multi-objective performance measures: distance metrics, hypervolume indicator, epsilon metric and error ratio. The computational tests have indicated an algorithm based on MOVNS as the most efficient one, compared to the distance metrics; also, a combined feature of MOG and MOVNS appears to be superior compared to the hypervolume and epsilon metrics and one based on PILS compared to the error ratio. Statistical experiments have shown a significant difference between some proposed algorithms compared to the distance metrics, epsilon metric and error ratio. However, significant difference between the proposed algorithms with respect to hypervolume indicator was not observed.     

A hybrid genetic algorithm for the job shop scheduling problems

The Job Shop Scheduling Problem (JSSP) is one of the most general and difficult of all traditional scheduling problems. The goal of this research is to develop an efficient scheduling method based on genetic algorithm to address JSSP. We design a scheduling method based on Single Genetic Algorithm (SGA) and Parallel Genetic Algorithm (PGA). In the scheduling method, the representation, which encodes the job number, is made to be always feasible, the initial population is generated through integrating representation and G&T algorithm, the new genetic operators and selection method are designed to better transmit the temporal relationships in the chromosome, and island model PGA are proposed. The scheduling methods based on genetic algorithm are tested on five standard benchmark JSSP. The results are compared with other proposed approaches. Compared to traditional genetic algorithm, the proposed approach yields significant improvement in solution quality. The superior results indicate the successful incorporation of a method to generate initial population into the genetic operators.