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

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

基于均衡适应度的云工作流调度算法

针对工作流任务调度优化问题,提出一种云工作流任务调度遗传算法。为了寻找工作流执行时间与执行代价的同步最优解,建立了遗传调度模型。在个体编码方面,采用了一种二维排列编码方法,可以更好地展现工作流任务间的执行次序;综合考虑任务执行代价与最早完成时间两个因素,设计了一种均衡适应度函数;为了丰富种群个体多样性,引入三种遗传交叉操作和两种遗传变异操作,以产生新的个体,增加了最优解的求解概率。通过数值仿真实验,在多个性能指标上对算法进行分析。结果表明,该调度算法能更好地平衡执行代价与调度效率,性能优于同类算法。     

不确定性云环境工作流调度多目标优化

云计算弹性的资源提供和虚拟机性能的不稳定性使得工作流的执行面临诸多不确定性.针对此问题,考虑执行时间具有不确定性,基于执行时间和代价的同步优化,提出同步满足健壮性的三目标优化工作流调度算法.以满足帕累托最优的均衡最优解集的形式进行建模,以启发式方式对模型求解.为衡量均衡解的质量,设计基于超体积的评估机制,得到冲突目标的均衡调度解,比原始双目标优化对执行时间的波动具有更小敏感性.实验结果表明,比较未考虑不确定性的双目标优化,该算法求解质量更高,均衡度更好,更符合不确定性实时云工作流调度.     

云环境中基于混合多目标粒子群的科学工作流调度算法

为了更高效地实现科学工作流任务的调度,研究了云环境中的工作流调度多目标优化问题,提出了一种基于非占优排序的混合多目标粒子群优化的工作流调度算法HPSO。首先,建立了截止时间与预算约束下工作流调度的多目标优化模型,模型引入三目标最优化,包括工作流执行跨度、执行代价及执行能耗;其次,设计了一种混合粒子群算法对相互冲突的三目标最优化进行求解,算法通过非占优排序的形式可以得到满足Pareto最优的工作流调度解集合;最后,通过3种科学工作流案例的仿真实验,与同类多目标调度算法NSGA-II,MOPSO和ε-Fuzzy进行了性能比较。实验结果表明,HPSO得到的调度解不仅收敛性更好,而且调度解的空间分布更加一致,更符合云环境中的工作流调度优化。     

置换流水车间调度问题的两阶段分布估计算法

针对置换流水车间调度问题,以最小化总流水时间为目标,提出了一种新颖的两阶段分布估计算法。第一阶段先利用NEH（Nawaz-Enscore-Ham,NEH）启发式构造一个较优的初始个体,然后随机生成初始种群,为保留种群的多样性,提出一种择优机制来选择个体并建立概率模型,同时在当代种群中利用精英机制保留当代种群中的最优解,最后利用概率模型采样并生成下一代种群。第二阶段采用插入、互换操作算子对第一阶段得到的最优解进行邻域搜索,来提高分布估计算法的全局搜索能力,阻止其陷入局部最优解。通过对算例进行实验、对比和分析,证明该算法的可行性和有效性。     

网格计算中工作流调度的非合作博弈优化*

在异构网络计算问题中,网格计算方法通过引入资源共享机制,可解决复杂的计算任务。然而在网格环境中,需要对网络可获得的资源进行合理调度和协调,才可以获得良好的网络工作流,以及合适的网络性能和网络响应时间。为了提高网格计算方法的任务调度和资源分配的能力和性能,提出了一种基于非合作博弈方式的博弈模型。该模型通过设定使用户的资源分配所需时间和代价降低的解来增加代理的利润,激励资源代理使用一种优化调度算法,使资源调度的时间和代价都最小。仿真结果表明了该模型的可行性和适用性,并且基于该模型的遗传算法是最好的资源调度算法。     

一种改进樽海鞘群算法及其多目标云工作流调度应用

为了优化云工作流应用的调度效率与代价，提出基于改进樽海鞘群算法的工作流调度策略。建立截止时间与预算约束的多目标优化模型，利用樽海鞘觅食的位置变化对工作流调度进行编解码，设计融合执行跨度与执行代价的权重适应度函数。为了增强樽海鞘群的寻优性能，引入基于疯狂算子的领导者更新模式，通过疯狂变量，减少领导者更新的停滞早熟现象；引入遗传算子的追随者更新模式，利用个体交叉和变异使樽海鞘群具有更均衡的搜索全局性和个体多样性，避免陷入局部最优。结果证明，改进樽海鞘群算法可以有效提升计算精度和收敛速度；应用于工作流调度求解后，其调度解收敛性更好，调度解集空间分布更加一致。     

多目标最优化云工作流调度进化遗传算法

为了实现云环境中科学工作流调度的执行跨度和执行代价的同步优化,提出了一种多目标最优化进化遗传调度算法MOEGA。该算法以进化遗传为基础,定义了任务与虚拟机映射、虚拟机与主机部署间的编码机制,设计了满足多目标优化的适应度函数。同时,为了满足种群的多样性,在调度方案中引入了交叉与变异操作,并使用启发式方法进行种群初始化。通过4种现实科学工作流的仿真实验,将其与同类型算法进行了性能比较。结果表明,MOEGA算法不仅可以满足工作流截止时间约束,而且在降低任务执行跨度与执行代价的综合性能方面也优于其他算法。     

虚拟网格服务工作流的调度算法研究

对虚拟网格服务工作流的调度算法进行了研究,提出了最小计算时间(MCT)、最小传输时间(MTT)、最小执行时间(MET)3种虚拟网格服务工作流的调度算法.在满足给定假设的情况下,MCT、MTT、MET的调度分别能保证目标工作流获得最小计算时间、最小传输时间、最小执行时间.在描述了调度算法之后,证明了算法调度的正确性.对几种算法的调度性能进行实验模拟,并分析和比较了它们的实现代价和时间、空间复杂度,从而给出各算法的适用情况.     

满足帕累托最优的多目标云工作流调度算法

为了同步考虑用户的任务QoS需求和云资源提供方的收益,提出一种云环境中满足帕累托最优的多目标最优化DAG(Directed Acyclic Graph)粒子群算法MODPSO(Multi-objective DAG Particle Swarm Optimization)。综合考虑任务执行跨度、执行代价与执行能耗的三目标同步最优化,设计基于DVFS的离散PSO调度优化方法。重新定义PSO的种群粒子进化过程和更新规则,进而得到多目标优化工作流调度解。通过人工合成工作流和现实科学工作流进行仿真测试,并对算法性能进行分析。结果表明,该算法可以通过非支配集的方式实现冲突多目标的调度优化求解。在满足用户QoS的同时,得到最优解的Pareto边界集,实现调度性能与系统能耗的均衡。