兼顾费用与公平的带通信开销的多有向无环图调度

针对云环境下多有向无环图(DAG)工作流的调度算法应考虑执行时间、费用开销、通信开销、公平性等多个指标的问题,在模型带通信开销的DAG(CA-DAG)的基础上结合公平性算法提出一种优化完成时间的后向求异(BD)原则与兼顾费用和公平的多DAG调度策略CAFS.CAFS调度策略分为两个阶段:预调度阶段利用带通信开销的工作流费用优化(CACO)算法在考虑通信开销的同时求解所有任务的最优服务并优化费用,采用fairness算法得到较公平的调度顺序;调度阶段采用BD原则,根据在预调度阶段得出的调度顺序进一步优化整体的完成时间并执行调度.实验结果表明,CAFS调度算法具有较好的公平性,在不提高费用的基础上时间减少19.82%.     

有期限约束的多DAG共享资源的调度及公平费用优化方法

随着网格和云计算工作流技术的发展,近来关于多DAG(Directed Acyclic Graph)共享资源调度的研究取得了一些进展,然而,关于具有最晚完成期限约束的多DAG共享一组有限异构资源的调度及其费用最低化等问题还有待进一步研究和解决.针对这些问题,文中首先提出了衡量DAG期限紧急水平的"相对严格程度"的新方法,并在此基础上提出了基于相对严格程度的调度算法MDRS(Scheduling for Multi-DAGs with Deadline based on Relative Stritness).该算法不仅能够合理处理多个DAG之间调度的紧急水平关系,也能对由于DAG期限过于严格而可能产生的"过饱和"情况进行探测和处理.一旦遇到"过饱和"情况,则采用"堆栈"与"调度回溯"相结合的机制尽可能少地丢弃其中的DAG,从而达到DAG吞吐量最大化调度目标.在MDRS算法的基础上,为了满足各DAG期限内完成约束条件,并尽可能公平地降低多个DAG执行的费用,又提出了基于单位相对严格程度变化量的费用降低率最大化方法的费用优化算法CDVRS(Cost Decrease based on Variance of the Relative Strictness).实验表明:这些方法及算法能够达到较好的性能.     

DAG分割模型下的云工作流调度策略

为了优化云工作流调度的经济代价和执行效率,提出一种基于有向无循环图（DAG）分割的工作流调度算法PBWS。以工作流调度效率与代价同步优化为目标,算法将调度求解过程划分为三个阶段进行：工作流DAG结构分割、分割结构调整及资源分配。工作流DAG结构分割阶段在确保任务间执行顺序依赖的同时求解初始的任务分割图;分割结构调整阶段以降低执行跨度为目标,在不同分割间对任务进行重分配;资源分配阶段旨在选择代价最高效的任务与资源映射关系,确保资源的总空闲时间最小。利用五种科学工作流DAG模型对算法进行了仿真实验。结果表明。PBWS算法仅以较小的执行跨度为开销,极大降低了工作流执行代价,实现了调度效率与调度代价的同步优化,其综合性能是优于同类型算法的。     

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

针对效用网格下的工作流时间约束-费用优化问题,分层算法将工作流进行分层并逐层进行优化调度,取得了良好效果.然而,这类分层算法由于缺乏更有效的截止时间确定策略来保证时间约束而使得算法的适用性受限.在已有算法截止期约束的逆向分层算法(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%。     

DAG多级相关节点聚类的多目标工作流调度

针对科学工作流的为多目标调度问题,将成本、时间和数据传输量作为基本优化目标,提出基于有向无环图(Directed Acyclic Graph,DAG)模型的多级相关节点聚类(Multi-level correlated Nodes Clustering,MNC)方法.首先,针对在连续级别上直接连接的Peer-to-Pe...     

基于改进优先级规则的工作流费用优化方法

效用网格下的工作流时间约束-费用优化调度是一个NP难问题,基于时间耦合强度(time-dependent coupling strength,TCS)的最适规则(best fit time-dependent coupling strength,BFTCS)将作业的资源特征与工作流的结构特征作为优先级规则的两个重要方面应用于迭代算法的改进阶段,取得了良好效果,然而,BFTCS忽略了工作流的时序特征.在已有工作的基础上,定义任务的时间灵活度(temporal mobility,TM)并设计基于时间耦合强度和时间灵活度的最适规则(best fit based on time-dependent coupling strength and temporal mobility,BFTCSTM).该规则在BFTCS规则的基础上选择TM较大的任务优先迭代,有效减缓了迭代过程中工作流长度的增长过程,使其他任务能进一步优化费用的机会增大,改善了工作流的费用优化效果.实验结果证明了BFTCSTM的优越性.     

基于任务概率聚簇的工作流云费用优化调度算法

由于云资源具有弹性伸缩、按使用量计费等优势,科研机构将工作流部署在云环境执行。工作流任务在云计算环境执行过程中会产生不可避免的系统开销。针对实际运行环境系统开销过大的问题,笔者提出基于聚簇概率的任务概率聚簇算法,平衡每层任务的资源需求,提高资源分配粒度,降低系统开销和降低公有云执行费用。实验表明,该算法能够有效降低公有云花费。     

云环境下基于多目标的多科学工作流调度算法

针对现有云环境下的多科学工作流调度算法中存在的未考虑安全调度问题,提出多科学工作流安全-时间约束费用优化算法MSW-SDCOA（Multi-Scientific Workflows Security-Deadline constraint Cost OptimizationAlgorithm）.首先MSW-SDCOA基于数据依赖关系压缩科学工作流,减少任务节点数从而节省了调度开销;并通过改进HEFT（Heterogeneous Earliest-Finish-Time）算法形成调度序列,以实现全局多目标优化调度;最后,通过优化ACO（Ant Colony Optimization）中信息素更新策略和启发式信息,进一步改善费用优化效果.仿真实验表明,MSW-SDCOA算法在费用优化效果上比MW-DBS算法提高了约14%.     

基于服务质量的云工作流调度优化算法

为满足云工作流实例的多样化需求,根据工作流的特点和云环境中资源部署结构,建立多服务质量指标的云工作流调度模型。对蚁群算法进行改进,解决其收敛速度慢、易陷入局部最优等缺点。利用用户对服务质量不同程度的偏好,引入云任务优先次序启发式规则,提出一种基于服务质量的云工作流调度算法(SPACO)。在Cloud Sim平台上,对云工作流调度模型和算法进行仿真分析,将仿真结果与基本蚁群算法(ACO)、改进的蚁群算法(PACO)进行比较,其结果表明该算法能缩短执行时间、降低能耗成本,验证了该模型的可行性和算法的有效性。     

服务工作流中基于用户需求的调度模型及算法研究

在前期研究的基础上,从工作流的实用性与用户的个性化需求出发,提出了一种基于用户需求的工作流调度模型,该模型由业务逻辑模型、用户个性化定制模型、服务组织模型、工作流调度模型、工作流执行模型等五部分组成;同时研究了一种按用户需求的工作流调度机制,该机制能实现高层用户逻辑向底层执行映射的动态服务绑定;最后分析了调度机制失效时的最小代价恢复策略.与同类成果相比,调度模型具有灵活地支持用户个性化需求,算法复杂度低,并能以最小代价快速失效恢复等优点.     

网格环境下基于QoS的协作型任务调度算法研究

在深入研究网格环境下任务调度算法的基础上,提出一种基于QoS的协作型任务调度遗传算法并通过引入协作型任务的形式化描述DAG图构造了QoS参数模型.该参数模型提出了任务完成时间、价格和可靠性三个QoS参数并将这些QoS参数引入遗传算法,实现了网格环境下协作型任务调度对服务质量的优化并保证了协作型任务之间的数据依赖.通过与DAG-MIN和DAG-GSA算法的对比实验表明,该算法能在保证较优调度性能的同时大幅度提高调度的服务质量.     

移动支持协议移动管理代价研究

针对移动支持协议的移动管理代价进行了研究,提出了一种合适的网络模型.在此网络模型的基础上,采用理论分析的方法分析了使用各移动支持协议时,为支持MH(mobile host)移动给网络带来的信令开销,并采用数值仿真的方法,对只使用移动IP协议和引入层次移动时的信令开销以及采用MIP-RR,CIP和HAWAII等不同微移动协议时的信令开销进行了比较.结果表明:引入层次移动与只使用移动IP相比,显著减少了网络的信令开销;在不同的微移动协议中,使用显式删除旧路径的路径维护策略与频繁发送周期性的刷新报文相比,给网络带来的信令开销较小;使用路径更新报文发送到交叉MRA(mobile routing Agent)的路径更新方法与路径更新报文发送到GW(gateway)相比,具有较小的网络信令开销.     

网格工作流的动态贪心调度算法

有向无环图描述的工作流时间费用优化问题是计算网格中的基本难题之一。针对该问题提出一种网格工作流的动态贪心调度算法(DGS-GW)。按用户提交的截止时间和偏好因子建立数学模型,利用DGS-GW求解该模型的次优解。实验结果证明了该算法的有效性。     

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

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

面向对象的流程工业系统有向无环图建模

提出流程工业系统中有向无环图的面向对象的建模方法。介绍使用面向对象的技术对流程工业系统模进行建模的关键要素的技巧,定义描述流程工业系统中有向无环图模型的建模机制,扩展流程工业系统模型所具有的特性。以流程工业系统出现异常时的诊断实例说明系统模型解决问题的有效性。     

基于云科学工作流调度的代价与能效优化算法

为了降低云环境中科学工作流调度的执行代价与数据中心能耗,提出了一种基于能效感知的工作流调度代价最优化算法CWCO-EA。算法在满足截止时间约束下,以最小化工作流执行代价与降低能耗为目标,将工作流的任务调度划分为四步执行。首先,通过代价效用的概念设计虚拟机选择策略,实现了子makespan约束下的任务与最优虚拟机间的映射;其次,通过串行与并行任务合并策略,同步降低了工作流的执行代价与能耗;然后,通过空闲虚拟机重用机制,改善了租用虚拟机的利用率,进一步提高了能效;最后,通过任务松驰策略实现了租用虚拟机的能力回收,节省了能耗。通过四种科学工作流的仿真实验,结果表明,CWCO-EA算法比较同类型算法,在满足截止时间的同时,可以同步降低工作流的执行代价与执行能耗。     

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

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