论文部分内容阅读
云计算灵活的资源配置和现收现付的付费模式为执行大规模的科学和经济问题提供了一个高效、经济的分布式计算平台。大规模的科学和经济问题通常被建模成工作流模型,这些工作流上的应用程序不断增长的数据和计算需求使如何在云计算平台上高效的调度和部署这些应用程序的研究受到广泛关注。从用户的角度,最大完成时间和总花费是两个重要的服务质量指标,他们希望工作流应用程序可以尽可能快的完成,同时期望降低付出的总花费。然而,如何解决IaaS云环境下的多个工作流调度问题仍存在各种挑战,特别是针对多个相互冲突的目标的最优调度问题,仍有待妥善解决。现有的云工作流-多目标优化调度方法在很多方面仍然存在局限性,如在处理动态调度问题时编码受到先验或后验专家知识的限制,严重影响调度的性能。针对上述问题,本文重点研究了在不需要大量的专家知识和人为干预的情况下,同时优化最大完成时间和总花费的多工作流调度方法。在本文中,我们首先分析了云工作流调度问题的最小化最大完成时间和总成本的双目标优化问题的形式化建模。为了优化多个工作流的最大完成时间和用户成本,我们考虑了一个以工作流应用程序和异构云主机的数量为状态输入,以最大完成时间和成本为奖励的马尔可夫博弈模型,通过合适的选择机制以及奖励函数的设计使博弈模型的解收敛于相关均衡。然后本文在多智能体学习场景中运用Deep-Q-network模型求解该马尔可夫博弈模型,以指导IaaS云上的多工作流调度。该方法将两个优化目标抽象成两个智能体,并考虑了一个随机的、动态交互的环境,旨在使智能体之间通过相互协作以及与环境的交互学习基于相关均衡的动态调度策略。为了验证本文提出的模型和方法,我们基于多个著名的科学工作流模板以及Amazon EC2云实例进行了广泛的案例研究,并与传统算法,如多目标粒子群优化算法、非主导排序遗传算法-II和基于博弈理论的贪心算法进行对比实验。实验结果表明,我们提出的算法在生成调度计划的最大完成时间的最优性方面明显优于传统算法,最低水平差值优势超过53.4%,而总成本相较于对比算法的差值比率最高不超过9.9%。