基于离散粒子群算法的工作流任务调度研究

工作流系统可以实现企业的业务过程的自动化,好的调度算法可以提高整个工作流系统的执行效率.对工作流任务调度的研究具有重要的意义.离散粒子群优化算法是一种收敛速度快、调整参数少、易实现及理解的优化算法.结合工作流特点,通过置换因子的概念,将离散粒子群算法与工作流任务调度相结合,给出了基于离散粒子群算法的工作流任务调度的定义.并结合保险理赔处理进行实验,得到了良好的效果,验证了应用的有效性和可行性.     

基于代价优化的云工作流调度改进PSO算法

云计算可以通过即付即用的方式向用户工作流提供资源。为了解决资源服务代价异构环境下的云工作流任务调度代价问题,提出一种基于改进粒子群算法的云工作流任务调度算法WSA-IPSO。通过综合考虑任务的执行代价和依赖任务间发生数据传输时的通信代价,算法将总代价优化问题形式化为有向无环图DAG中的任务调度模型,并提出基于改进粒子群算法的优化模型对其进行求解。通过改进传统粒子群算法的粒子速度更新策略和惯性权重更新策略,算法可以以更快的收敛速度得到代价最小化的调度方案。通过仿真实验,与MCT算法及标准粒子群算法进行性能比较。实验结果表明,WSA-IPSO算法在降低总代价、任务分布的负载均衡以及算法收敛性方面比较同类算法均表现出更好的性能。     

基于粒子群优化的异构多处理器任务调度算法

为提高异构多处理器任务调度的执行效率,充分发挥多处理器并行性能,提出一种基于粒子群优化的异构多处理器任务调度算法——FPSOTTS算法。该算法以求得任务最短完成时间为目标,首先通过建立新的编码方式和粒子更新公式实现粒子搜索空间到离散空间的映射,使连续的粒子群优化算法适用于离散的异构多处理器任务调度问题;同时通过引入禁忌算法进行局部搜索,克服粒子群算法的早熟收敛现象,避免陷入局部最优。实验结果表明,FPSOTTS算法的执行效率优于Min-min算法和遗传算法,有效地降低任务的执行时间。FP-SOTTS算法很好地解决了异构多处理器任务调度问题,并且适合于大规模并行任务调度。     

一种粒子群优化的异构多处理器任务调度算法

为提高异构多处理器任务调度的执行效率,充分发挥多处理器并行性能,提出一种基于粒子群优化的异构多处理器任务调度算法-PSOASA算法.PSOASA算法以求得任务最短完成时间为目标,首先采用整数矩阵对粒子进行编码,并定义交换操作更新粒子状态,实现粒子搜索空间到离散空间的映射,使连续的粒子群优化算法适用于离散的异构多处理器任务调度问题,同时引入模拟退火算法,克服粒子群算法的“早熟”收敛现象,避免求得的解陷入局部最优.实验结果表明,PSOASA算法的执行效率优于目前广泛采用的遗传算法,有效地降低任务执行时间,减少了迭代次数,适用于异构多处理器环境大规模任务调度.     

云工作流系统中能耗感知的任务调度算法*

云工作流系统研究集中在工作流任务执行的时间效率优化,然而时间最优的任务调度方案可能存在不同能耗,因此,文中求解满足时间约束时能耗最优的调度方案。首先改进任务执行能耗模型,设计适用于评价任务调度方案执行能耗的适应度计算方法。然后基于精准调整粒子速度的自适应权重,提出解决任务调度能耗优化问题的自适应粒子群算法。实验表明,文中算法收敛稳定,调度方案执行能耗较低。     

基于 DPSO 的云工作流任务自适应调度策略

云工作流系统中的任务调度问题属于典型的NP难题,同时由于计算资源异构性、复杂性及用户需求的动态性可能导致系统过载。为了解决或避免此类问题的发生,本文提出一种带动态反馈机制的任务自适应分配方法,并结合离散粒子群优化算法（ Discrete Particle Swarm Optimization ,DPSO）,利用任务预测执行时间模型来优化任务分配方案。仿真实验表明该方法可保证系统负载平衡,当任务数大于150时能够使任务调度时间最短。     

基于粒子群优化算法的异构多处理器任务调度

为提高异构多处理器任务调度的执行效率,充分发挥多处理器并行性能,提出一种基于粒子群优化的异构多处理器任务调度算法-PSOASA算法.PSOASA算法以求得任务最短完成时间为目标,首先通过建立新的编码方式和粒子更新公式实现粒子搜索空间到离散空间的映射,使连续的粒子群优化算法适用于离散的异构多处理器任务调度问题,同时通过引入模拟退火算法,克服粒子群算法的“早熟”收敛现象,避免求得的解陷入局部最优.实验结果表明,PSOASA算法的执行效率优于目前广泛采用的遗传算法,有效地降低任务的执行时间,减少了迭代次数,适用于异构多处理器环境大规模任务调度.     

选煤厂信息物理系统任务调度研究

建立了选煤厂信息物理系统模型,将动态联盟思想引入选煤厂信息物理系统任务调度中,并提出了一种基于改进离散粒子群优化算法的选煤厂信息物理系统任务调度算法。该算法首先采用离散粒子群优化算法进行全局寻优,然后采用禁忌搜索算法进行局部搜索,求得全局最优解。仿真结果表明,该算法提高了任务调度的收敛速度、精度以及处理器的平均利用率。     

基于改进离散粒子群禁忌算法的并行测试任务调度

针对并行测试任务调度问题特点,提出了一种解决并行测试任务调度的离散粒子群禁忌算法,设计了符合并行测试任务调度特点的粒子初始化编码方式、粒子位置转移公式以及禁忌搜索邻域。通过与禁忌搜索相结合,避免了离散粒子群算法早熟问题。通过实验以及算法对比,表明提出的算法是快速有效的,能够很好地解决并行测试任务调度问题,求得测试总时间最短的任务调度序列。     

基于离散粒子群优化算法的网格资源分配研究

资源分配和任务调度是网格计算中关键的问题之一。本文提出一种基于离散粒子群优化算法的网格资源分配算法。该算法通过对粒子群算法中粒子的位置与速度进行重新定义,以及重新设计粒子的位置与速度的变换规则,使粒子群算法适用于网格资源分配和任务调度。理论分析及模拟实验表明,该算法具有良好的性能。     

基于混合GA算法的工作流作业调度队列优化

工作流作业的调度效率是评价工作流管理系统整体表现的重要指标。众所周知,工作流作业的调度问题是一个NP-hard问题,而异构的计算环境使得问题更加棘手。分层基因算法LGA将启发式算法与GA算法相结合,利用GA算法来优化经过正向分层之后的工作流作业调度队列,显著地减少了工作流作业的执行时间。该算法根据作业的分层优先级来产生作业队列,把队列中的同层作业从整体上看作是一位基因来处理,有效地对算法的进化方向进行规划,并通过对杂交和变异流程的改进,增强算法的搜索深度和广度。实验表明,相比于其他混合GA算法,经LGA算法优化之后的工作流作业调度队列,所需的执行时间更少。     

云中截止时间动态分配的工作流调度成本优化算法

现如今,如何在满足截止时间约束的前提下降低工作流的执行成本,是云中工作流调度的主要问题之一。三步列表调度算法可以有效解决这一问题。但该算法在截止时间分配阶段只能形成静态的子截止时间。为方便用户部署工作流任务,云服务商为用户提供了的三种实例类型,其中竞价实例具有非常大的价格优势。为解决上述问题,提出了截止时间动态分配的工作流调度成本优化算法(S-DTDA)。该算法利用粒子群算法对截止时间进行动态分配,弥补了三步列表调度算法的缺陷。在虚拟机选择阶段,该算法在候选资源中增加了竞价实例,大大降低了执行成本。实验结果表明,相较于其他经典算法,该算法在实验成功率和执行成本上具有明显优势。综上所述,S-DTDA算法可以有效解决工作流调度中截止时间约束的成本优化问题。     

基于动态有色Petri网的网格服务工作流模型的研究

在深入了解网格技术、网格服务和网格工作流的概念、特点及其应用的基础上,提出了一种可行的网格服务工作流系统模型,重点介绍了动态优化建模技术、动态调度算法的实现思想.定义了一种动态有色Petri网作为服务工作流的建模工具,支持服务工作流的动态优化建模和动态调度,并为服务工作流模型提供性能评价依据.验证表明采用该模型能够很好地满足用户的QoS要求,并且有助于提高资源利用率.     

一种多重约束下确保成功率的云工作流调度方法

为提高多重约束下的调度成功率,提出一种满足期限和预算双重约束的云工作流调度算法.将可行工作流调度方案求解分解为工作流结构分层、预算分配、期限分配、任务选择和实例选择.工作流结构分层将所有工作流任务划分层次形成包任务,以提高并行执行程度;预算分配对整体预算在层次间进行分割;期限分配将全局期限在不同层次间分割;任务选择基于...     

基于多QoS目标的工作流任务调度算法

根据工作流任务的结构特点对其进行分区,按照任务量和通信量将总工作流截止日期和总工作流花费分为每个任务分区上的子截止日期和子花费,在考虑用户多个QoS要求及工作流任务间通信时间的基础上,提出基于信任与花费的综合效益函数,给出信任与花费权值的确定方法以及一个以综合效益最优为目标的调度算法——TCD,算法通过追求局部最优达到全局多目标优化调度。与其他算法的比较表明,该算法服务拒绝率最多可降低15%,能较好地满足用户多QoS要求。     

A rotary chaotic PSO algorithm for trustworthy scheduling of a grid workflow

In this paper, a rotary chaotic particle swarm optimization (RCPSO) algorithm is presented to solve trustworthy scheduling of a grid workflow. In general, the grid workflow scheduling is a complex optimization problem which requires considering various scheduling criteria so as to meet a wide range of QoS requirements from users. Traditional researches into grid workflow scheduling mainly focus on the optimization constrained by time and cost. The key requirements for reliability, availability and security are not considered adequately. The main contribution of this study is to propose a new approach for trustworthy workflow scheduling in a large-scale grid with rich service resources, and present the RCPSO algorithm to optimize the scheduling performance in a multi-dimensional complex space. Experiments were done in two grid applications with at most 120 candidate services supplied to each task of various workflows. The results show better performance of the RCPSO in solving trustworthy scheduling of grid workflow problems as compared to GA, ACO and other recent variants of PSO.     

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.     

An Effective Cloud Workflow Scheduling Approach Combining PSO and Idle Time Slot-Aware Rules

Workflow scheduling is a key issue and remains a challenging problem in cloud computing.Faced with the large number of virtual machine(VM)types offered by cloud providers,cloud users need to choose the most appropriate VM type for each task.Multiple task scheduling sequences exist in a workflow application.Different task scheduling sequences have a significant impact on the scheduling performance.It is not easy to determine the most appropriate set of VM types for tasks and the best task scheduling sequence.Besides,the idle time slots on VM instances should be used fully to increase resources'utilization and save the execution cost of a workflow.This paper considers these three aspects simultaneously and proposes a cloud workflow scheduling approach which combines particle swarm optimization(PSO)and idle time slot-aware rules,to minimize the execution cost of a workflow application under a deadline constraint.A new particle encoding is devised to represent the VM type required by each task and the scheduling sequence of tasks.An idle time slot-aware decoding procedure is proposed to decode a particle into a scheduling solution.To handle tasks'invalid priorities caused by the randomness of PSO,a repair method is used to repair those priorities to produce valid task scheduling sequences.The proposed approach is compared with state-of-the-art cloud workflow scheduling algorithms.Experiments show that the proposed approach outperforms the comparative algorithms in terms of both of the execution cost and the success rate in meeting the deadline.