军事网格工作流调度算法研究

针对军事网格应用及工作流的特点,提出一种基于网格工作流分割的调度算法。采用基于有向无环图的工作流建模方法,对网格工作流的相关概念进行形式化定义。在确定基本工作流之间的复合关系后,对网格工作流中的任务实施调度。实例结果表明,该算法能减少网格工作流的任务执行时间,具有较好的调度性能。     

基于串归约的网格工作流费用优化方法

针对截止期限约束下有向无环图DAG(directed acyclic graph)表示的工作流费用优化问题,提出两个新的费用优化算法:时间约束的前向串归约算法FSRD(forward serial reduction within deadline)和时间约束的后向串归约算法BSRD(backward serial reduction within deadline).算法利用DAG图中串行活动特征给出串归约概念;基于分层算法对串归约组的时间窗口重定义,并提出动态规划的求解策略实现组内费用的最优化.两种归约算法综合考虑DAG图中活动的串并特征,改变分层算法中仅对单一活动的费用优化策略,实现了串归约组的时间收集和最优利用.模拟实验结果表明: BSRD和FSRD能够显著改进相应分层算法的平均性能,且BSRD优于FSRD.     

基于有向无环图网格独立任务调度算法*

提出了基于有向无环图多约束网格环境下独立任务的调度模型,为其建立多约束线性规划模型,通过求解模型节点的优先级,获得网格各计算节点最优任务调度数;然后基于多约束最优任务调度方案,提出多约束带宽优先启发式算法(MCOPBHATS)和多约束计算速度优先启发式算法(MCOPCHATS)。实验结果表明,在多约束异构的网格环境下实现大量独立任务调度时, MCOPBHATS和MCOPCHATS算法的性能优于基于多约束最优任务调度方案的MinMin 算法。     

QoS约束下基于双向分层的网格工作流调度算法

为使网格工作流的执行满足用户QoS要求,应用有向无环图描述工作流,并分析其中的关键活动,把用户对工作流的整体QoS约束分割为对单个任务的QoS约束.以此为基础,提出了一种基于双向分层的网格工作流调度算法Q-TWS.该算法通过对工作流正向分层和逆向分层,可以方便并准确找到任务之间的并行关系.Q-TWS可最大程度放松对任务执行时间的约束,在增加调度灵活性的同时又满足用户的QoS要求.实验表明,Q-TWS算法与TL算法相比,在同样的截止时间约束下,工作流执行时间较短,且工作流执行费用较小.     

基于有向无环图的成本-时间优化调度算法

网格计算环境下,基于有向无环图（DAG）的成本-时间优化调度算法运用经济规律把网格用户的任务映射到网格资源中运行。OGS算法考虑了任务间的优先关系,使得任务完成时间最小,但没考虑到在网格环境中所需的成本。Nimrod/G模型中提出基于时间和成本限制下的优化调度算法（DBC）考虑了时间和成本,但没考虑任务间的优先关系。本文综合考虑了成本-时间因素以及任务间的优先关系,在不增加完成时间的基础上,把任务映射到价格便宜的机器上,提出了基于有向无环图的成本-时间优化调度算法。通过仿真表明,相对OGS算法,该算法减少了所需成本。     

基于GA-SA算法的网格工作流调度

对用于网格工作流调度的遗传模拟退火(GA-SA)算法进行改进.在GA算法部分结合了基于阈值的动态交叉和变异概率, 并通过动态的调节近邻子集的大小,提高收敛速度,有效防止种群早熟现象,通过实验验证该算法的可行性和有效性.     

一种异构计算环境下基于复制的调度算法

提出了一种异构环境下的基于复制的调度算法（TDNH）,并与同为异构环境下的HEFT算法进行了比较,结果证明TDNH算法减小了时间跨度。最后通过实验证明了TDNH算法能够得到比较好的结果。     

网格工作流调度算法研究综述

作为一个NP完全问题,通常采用启发式算法来解决网格工作流调度。首先对网格工作流调度算法进 行了分类,然后对其典型算法进行了分析和讨论,并阐述了一些典型网格工作流调度系统,最后指出了现有算法 中的一些不足之处,展望了该领域的进一步研究方向。     

网格环境中的两阶段数据挖掘工作流调度模型

本文基于网络中的两层网格体系结构,提出了一个两阶段调度模型,即外部调度和内部调度的两阶段调度结构．这种方法采用局部处理和全局合成的计算范式。对分布式网络体系子DAG图的外部调度是通过密封式拍卖方法来实现的,在调度过程中,考虑通信的成本和IntraGrid的可信度。     

基于有向无环图的成本-时间优化调度算法

网格计算环境下,基于有向无环图(DAG)的成本-时间优化调度算法运用经济规律把网格用户的任务映射到网格资源中运行.OGS算法考虑了任务间的优先关系,使得任务完成时间最小,但没考虑到在网格环境中所需的成本.Nimrod/G模型中提出基于时间和成本限制下的优化调度算法(DBC)考虑了时间和成本,但没考虑任务问的优先关系.本文综合考虑了成本-时间因素以及任务间的优先关系,在不增加完成时间的基础上,把任务映射到价格便宜的机器上,提出了基于有向无环图的成本-时间优化调度算法.通过仿真表明,相对OGS算法,该算法减少了所需成本.     

基于逆向分层的网格工作流调度改进算法

通过对逆向分层DBL(Deadline Bottom level BL)算法的分析与研究,发现当截止期(δn)大于BLmin的情况下,其对逆向分层浮差(Tws)分配上有不足之处。为此该文提出了一种改进算法DBL-LC(DeadlineBottomlevel-lowercost)。改进算法使得对逆向分层浮差(Tws)的使用更加充分,减少了流时间碎片。实验证明,在相同的截止期下DBL-LC执行费用比DBL算法平均降低了14.52%。     

基于网格工作流的列表启发式算法研究

将用户定义的具体网格工作流抽象为DAG图,在DAG图中找到其关键路径,根据关键路径和用户的类型来计算任务的预测执行时间,确定任务的优先级,再比较若干候选资源,选择性价比较高的资源进行任务分配调度算法。     

成本约束的网格工作流时间优化方法

针对成本约束有向无环图DAG(directed acyclic graph)表示的网格工作流完工时间最小化问题,提出两个基于优先级规则的迭代启发算法.算法利用并行活动特征定义正向分层和逆向分层两个概念,将其分别引入最大收益规则MP(maximum profit),得到正分层最大收益规则MPTL(maximum profit with top level) 和逆分层最大收益规则MPBL(maximum profit with bottom level).两规则每次迭代尽量以完工时间的最小增加换取总费用的最大降低,逐步将分层初始解构造为满足成本约束的可行解.模拟结果表明,两规则在获得较少迭代次数和运行时间的同时,能显著改进MP规则的平均性能,且MPBL优于MPTL.     

基于时序一致的工作流费用优化方法

针对效用网格下的工作流时间约束-费用优化问题,分层算法将工作流进行分层并逐层进行优化调度,取得了良好效果.然而,这类分层算法由于缺乏更有效的截止时间确定策略来保证时间约束而使得算法的适用性受限.在已有算法截止期约束的逆向分层算法(deadline bottom level,DBL)的基础上,研究工作流的时序特征,并基于任务的一致性状态对费用进行优化,提出了基于时序一致的截止期约束逆向分层算法(temporal consistency based deadline bottom level,TCDBL).TCDBL通过一致性时间点来保证时间约束,解决了DBL的适用性受限问题;同时基于各层并行度分配冗余时间,基于宽松时间约束策略进行费用优化,达到了进一步减少工作流执行费用的目标.实验结果表明TCDBL的费用优化效果比DBL改进了约14%.     

基于路径平衡的工作流费用优化方法

针对效用网格下截止期约束的工作流费用优化问题,提出了路径平衡(path balance,简称 PB)算法,对工作流中各路径长度进行调整,并提出基于路径平衡的费用优化(path balance based cost optimization,简称PBCO)算法。 PBCO 基于 PB 的计算结果设置初始约束时间,充分利用了工作流的费用优化空间。同时,采用逆向分层策略对任务进行分层,并根据各层任务数按比例分配冗余时间,有效地增大了多数任务的费用优化空间,进一步改善了工作流的费用优化效果。实验结果表明,PBCO比另外几种著名算法(如DET,DBL等)改进了约35%。     

流程业务化定制中的工作流建模方法研究

针对流程业务化定制的需求,提出了一套面向业务人员的、直观易用的工作流建模方法.首先定义了一种基于有向图的工作流模型.在该模型的基础上,通过设置建模规则来规范业务人员的建模行为,使得无需模型验证就能够保证所建过程模型的正确性,从而回避了传统的有向图方法在模型分析方面的缺陷.最后将这套建模方法转化为Petri网的形式来描述,并利用Petri网的分析技术证明了该方法的可靠性.     

基于有向图的工作流模型的研究

工作流模型的建立是工作流管理系统中非常重要的一步,关系着工作流管理系统实施的成败。文中首先分析了基于IPO图的有向图工作流模型,并在其基础上运用面向对象的思想提出了基于活动节点和有向连接弧的有向图模型。接着分析了这种模型的特点,结合XML技术给出了该模型的XML文件定义,通过具体的实例说明了该种模型的可扩展性和可维护性,可以有效解决一些流程描述中的难点,并给出了流程描述难点如联合审批和回退机制的支持和解决方案。最后结合了电子文件的申请浏览流程的例子说明了该模型定义在实际流程的中的有效运用。     

基于图割的云环境中工作流调度改进算法

为提高云环境中工作流的执行效率,通过调整工作流引擎的调度策略,将MCGP（Multi Constraint Graph Partitioning）算法应用于工作流调度引擎,并对其不足,提出改进的MCGRP(Multi Constraint Graph Ratio Partitioning)算法。模拟实验表明,本文的调度算法有效地提高了系统的资源利用率和云环境中工作流的执行效率。