基于纳什议价解的多目标合作博弈云任务调度

作者:刘雨潇; 王毅; 袁磊; 吴钊
来源:计算机工程与设计, 2017, 38(12): 3316-3323.
DOI:10.16208/j.issn1000-7024.2017.12.022

摘要

针对云任务调度优化问题,提出一种基于纳什议价解的多目标合作博弈调度算法NBS-EATS。基于纳什议价解NBS,将多约束条件下云任务调度形式化为合作博弈模型,模型以任务截止时间和任务结构需求为约束,将主机能耗与任务执行跨度Makespan同步最小化定义为多目标函数,通过求解模型NBS得到最优任务映射方案。数学分析结果表明,合作博弈是有解的,在求解产生Pareto最优解的NBS时,时间复杂度为O(nmlog(m))(n为任务数量,m为主机数量);仿真结果表明,与同类算法Greedy和LR相比,NBS-EATS算法在总体能耗和平均执行跨度上分别低24.4%、50.7%和22.8%、29.6%,验证了该算法的可行性。

  • 出版日期2017
  • 单位湖北文理学院

全文