网格环境下的高效动态任务调度算法

网格系统具有异构性、动态性和分布性，这使得网格中的任务调度变得十分复杂，要求调度算法具有动态性和自适应性．文中将群体智能技术引入网格的任务调度中，针对一组相互独立的任务调度问题，提出了一种新的动态任务调度算法．该算法利用蜂群与环境的交互模型来实现网格中动态的任务分配；同时根据蜂群的自组织社会层次的概念，解决了算法中出现的竞争问题．实验结果表明，相比于现有的方法，该算法对于网格中的动态环境具有更好的适应性，且调度性能更优．     

基于LBT的网格依赖任务调度算法

文章将任务调度分为资源分配和调度执行2个阶段,定义了网格环境下的调度执行最晚开始时间、调度执行开始时间和任务依赖图中边的权值;分析了任务图冻结消减和执行消减对任务图结构的影响;提出了基于LBT的网格依赖任务调度算法;实验表明该算法有效地减弱了网格动态性对调度结果的影响。     

基于约简任务资源分配图的网格依赖任务静态调度

网格资源环境的动态性和异构性对依赖任务的静态调度策略产生了极大的挑战.提出了一个能够更好地适应资源异构性,并完整支持调度、重调度的统一静态调度模型,即基于约简任务资源分配图(RT-RAG)的调度模型和调度算法.基于该模型的调度问题归结为RT-RAG的优化选取问题.实验分析表明,基于该模型的调度方法更好地适应了网格环境的动态性和异构性,使得静态调度策略与动态调度策略相比依然保持着较大的性能优势,并且也优于基于DAG任务图调度模型的AHEFT静态调度算法,特别是在资源差异较大的情况下.     

网格资源管理系统中的任务调度策略研究

网格计算是继Internet和Web技术之后，又一次信息技术浪潮。由于资源具有广域分布、异构、动态等特性，网格环境下的资源管理和调度是一个非常复杂且具有挑战性的问题。通过分析比较当前多种环境下任务调度策略的基础之上，提出了一种适用于网格资源管理系统的多次映射任务调度策略。该策略在追求最短任务完成时间的同时，兼顾到了不同用户的需求，从而更好的适应了网格资源动态变化的特性。     

基于资源融合的网格任务调度模型与算法

讨论了网格资源计算能力和网络通信速度异构的树型计算网格环境下独立任务的调度问题,为单层树型网格计算环境下的任务调度问题建立了整数线性规划模型,并采用资源融合方法将多层树型网格计算环境下的任务调度问题转化为单层树型网格计算环境下的任务调度问题,建立了相应的数学模型.基于所提出的模型构造了两个任务分配启发式算法OPCH和OPBH.实验结果表明,在异构的树型计算网格环境下实现独立任务调度时,文中提出的算法比FCFS、Min-min算法具有更好的性能.     

一种基于任务竞争力的工作流调度算法

网格计算聚集了大量的异构分布式的计算或存储资源,为科学研究提供了一个高性能环境.然而,网格资源的异构性和自治性特征使得任务调度变得极其复杂.针对DAG表示的科学工作流调度问题,根据任务可用资源率确定任务调度的优先级,以任务竞争力刻画任务对资源的最佳匹配度,基于分层调度策略提出了一种基于任务竞争力的工作流调度算法.采用GridSim模拟实验表明该算法相对于其他两个算法,具有更小的执行时间.     

网格环境下具有可靠性的任务调度策略

针对网格环境的动态性和异构性特点,该文提出了DHTS和RDHTS任务调度算法。在充分考虑任务间的依赖关系和通讯开销的动态变化的基础上,通过对任务执行次序优化设定和任务间空隙有效利用等方法,提高了协同任务的执行效率;通过分析网格中各结点自身中断事件发生次数的数学期望和方差,得出各结点的即时可靠性评价参数,从而增强了任务调度的可靠性。     

经济网格中基于剪枝策略的时间-费用优化任务调度

由于在经济网格环境下,存在着资源异构和分布的特征,网格任务调度变成了一个复杂的问题.为此,针对独立任务,在考虑用户的服务质量经济需求偏好的基础上,提出了一个优化用户时间和费用的任务调度方案选择算法.该算法首先将网格中兼顾时间和费用的任务调度方案形式化为一个n层m叉树,然后将调度方案的选择问题转化为树的遍历问题,最后利用剪枝方法避免无效路径的搜索,降低了时间复杂度,实现了任务的优化调度.结果表明该算法能按照用户的时限和费用需求偏好选择优化的调度方案,且在性能上优于传统的未剪枝算法.所以该算法是一种可行的任务调度算法.     

采用遗传-谐振算法求解网格依赖任务安全调度问题

针对异构网格环境下任务调度面临的安全性问题,考虑网格节点的系统安全控制策略与历史行为表现,构建了网格节点安全评估模型,并在此基础上提出了一种安全可信的网格依赖任务调度优化模型。为求解该模型,结合遗传算法全局寻优能力较强的特性,同时克服其局部寻优不足的缺点,引入谐振算法,从而设计了一种新的遗传-谐振算法(GASHO)。首先,针对DAG任务图基于启发式思想设计遗传进化算子和量子谐振算子等操作以产生任务调度优先队列,解决离散解非法的问题;然后,采用安全约束下的最早完成时间算子操作实现任务集到网格节点的映射,提高算法收敛效率;最后,对算法的时间复杂度和收敛性进行分析证明。仿真实验结果表明,在同等条件下与同类算法相比,GASHO算法在收敛性、调度长度、安全效益值等方面具有明显的优势。     

截止期约束下QoS导向的网格任务调度算法

网格系统具有异构性和动态性,同时运行在网格之上的任务对资源的需求也不同,从而使任务调度变得极其复杂.针对网格任务的资源QoS和截止时间QoS要求,提出一种截止期约束下的QoS导向的任务调度算法.采用GridSim模拟实验表明该算法相对于QoS-guided Min-min和MOR,任务完成比率得到了大幅度提高,同时能有效保证系统的负载均衡.     

An optimizing algorithm of static task scheduling problem based on hybrid genetic algorithm

To reduce resources consumption of parallel computation system,a static task scheduling optimization method based on hybrid genetic algorithm is proposed and validated,which can shorten the scheduling length of parallel tasks with precedence constraints.Firstly,the global optimal model and constraints are created to demonstrate the static task scheduling problem in heterogeneous distributed computing systems(HeDCSs).Secondly,the genetic population is coded with matrix and used to search the total available time span of the processors,and then the simulated annealing algorithm is introduced to improve the convergence speed and overcome the problem of easily falling into local minimum point,which exists in the traditional genetic algorithm.Finally,compared to other existed scheduling algorithms such as dynamic level scheduling(DLS),heterogeneous earliest finish time(HEFT),and longest dynamic critical path(LDCP),the proposed approach does not merely decrease tasks schedule length,but also achieves the maximal resource utilization of parallel computation system by extensive experiments.     

异构任务图的实现模型

任意异构程序映射到任意异松系统上执行,是并行程序计算最复杂的情况,为此提出了异构任务图的定义,它是异构程度直观和有效描述方法,还研究了异构任务图的实现模型,它是异构计算环境中软件和硬件的桥梁,分别给出了任务图的分簇算法、系统图的分簇算法和映射算法及应用实例,利用该模型可设计出可移植的并行程序,然后调度到可动态配置的异构计算机组织上运行。     

An improvement on algorithm of grid-workflow based on QoS

With the emergencc of grid computing. new challenges have arisen in workflow tasks scheduling. The goal of grid-workflow task scheduling is to achieve high system throughput and to match the application needs with the available computing resources. This matching of resources in a non-deterministically share heterogeneous environment leads to concerns on quality of service (QoS). Grid concept is presented in this paper, coupled with the QoS requirement of workflow task and an improved algorithm-ILGSS algorithm. has been brought out. The complexity of the improved sched uling algorithm has been analyzed. The experiment results show that the improved algorithm can lead to significant performance gain in various applicatkms. An important research domain adaptive workflow transaction in grid computing environment, has been explored and a new solution for the scheduling of distribute workflow has been hring forward in grid environment.     

基于动态任务优先级的网格任务调度算法研究

网格环境下的任务调度是一个NP完全问题.为了确保每一步都能优先调度影响调度长度最大的就绪任务,提出一种采用动态任务优先级策略的任务调度算法.在进行任务调度的过程中,通过动态计算任务图DAG的关键路径并有效地利用处理器的空闲时间段来复制任务,使任务节点之间的通信开销尽可能降低,进而缩短整个任务图的完成时间.大量的模拟实验结果表明,所提的算法在任务完成时间上明显优于HEFT算法和DDS算法.     

基于免疫遗传算法的网格任务调度

研究了网格环境下任务调度问题,提出了一个任务调度机制:基于任务图将每一个可能的任务调度方案表示成一个任务-资源分配图,将网格任务调度问题转化为任务-资源分配图优化选取问题.提出了一种基于免疫遗传算法的、实现任务-资源分配图优化选取的任务调度算法.该算法将任务-资源分配图的最长路径作为抗原,每一个任务-资源分配图对应一个抗体.实验结果表明这个算法在全局优化能力及收敛速度上均有显著提高.     

基于评价函数的动态协同任务调度算法

针对复杂网格环境中节点资源动态变化及大量任务协作访问的问题,提出一种基于评价函数的动态协作任务调度算法.该算法通过为网格中的协作任务与协作成员建立随时间变化的任务评价函数和协作成员评价函数,实现动态网格环境中的任务协同调度.理论分析与仿真实验表明：与基于合同网的分布式合作调度算法相比,本算法能够减小系统开销,提高资源分...     

有通信冲突的异构系统上的任务调度

在新的系统模型上，提出了一个任务调度算法．该系统模型考虑了通信冲突，即在任何时刻，一个处理器只能接收一条消息，发送一条消息．新的算法包括异构系统中任务优先级的高效排序和基于任务复制的处理器分配两部分．随机产生的任务图和一个具体应用的任务图进行调度试验的结果表明，该算法比已有调度算法的性能有了显著的提高．