云计算中一种基于遗传算法与效益驱动的任务调度算法

发布时间：2019-09-28 16:23

【摘要】：针对云计算的任务调度问题,提出了一种基于遗传算法与效益驱动的任务调度算法.在满足任务QoS约束的前提下,对计算开销、服务收益、延迟赔偿等因素进行了综合考虑,对任务调度问题进行了数学建模,同时采用遗传算法对目标函数进行求解.仿真表明,与Min-Min算法和QoS Min-Min算法相比,所提算法能够明显地减少任务调度完成时间,更好地均衡负载,提高单位计算开销效益.
【图文】：

＿ｂｅｎｅｆｉｔＣｏｍｐ＿ｃｏｓ（）ｔ，ｓ．ｔ．Ｔ＿ｆｉｎｉｓｈｉ＜Ｌ＿ｌｉｎｅｉ．（３）从上述分析可以看出，对于ｍ个待调度任务和ｎ个计算资源，，调度方式共有ｎｍ种，而要在多项式时间内得到公式（３）的最优解是不可能的．２基于遗传算法与效益驱动的任务调度算法任务调度问题是ＮＰ－ｈａｒｄ问题［９］，本文利用启发式算法ＢＴＳＡＧＡ来进行求解．图１中求解调度目标使用遗传算法［１０］，其过程如图２所示．图１ＢＴＳＡＧＡ流程图图２遗传算法求解调度问题的流程图Ｆｉｇ．１ＦｌｏｗｃｈａｒｔｏｆＢＴＳＡＧＡＦｉｇ．２Ｆｌｏｗｃｈａｒｔｏｆｓｏｌｖｉｎｇｔｈｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｂｙｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ图１给出了ＢＴＳＡＧＡ的工作流程．从图１可以看出，客户首先向预处理单元提交任务调度请求，预处理单元根据任务的属性和ＱｏＳ对任务的规模进行预估，然后向调度器发送任务注册请求，同时把任务的相·２５８·

＿ｂｅｎｅｆｉｔＣｏｍｐ＿ｃｏｓ（）ｔ，ｓ．ｔ．Ｔ＿ｆｉｎｉｓｈｉ＜Ｌ＿ｌｉｎｅｉ．（３）从上述分析可以看出，对于ｍ个待调度任务和ｎ个计算资源，调度方式共有ｎｍ种，而要在多项式时间内得到公式（３）的最优解是不可能的．２基于遗传算法与效益驱动的任务调度算法任务调度问题是ＮＰ－ｈａｒｄ问题［９］，本文利用启发式算法ＢＴＳＡＧＡ来进行求解．图１中求解调度目标使用遗传算法［１０］，其过程如图２所示．图１ＢＴＳＡＧＡ流程图图２遗传算法求解调度问题的流程图Ｆｉｇ．１ＦｌｏｗｃｈａｒｔｏｆＢＴＳＡＧＡＦｉｇ．２Ｆｌｏｗｃｈａｒｔｏｆｓｏｌｖｉｎｇｔｈｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｂｙｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ图１给出了ＢＴＳＡＧＡ的工作流程．从图１可以看出，客户首先向预处理单元提交任务调度请求，预处理单元根据任务的属性和ＱｏＳ对任务的规模进行预估，然后向调度器发送任务注册请求，同时把任务的相·２５８·
【作者单位】： 河北政法职业学院计算机系;
【基金】：河北省高等学校科学技术研究青年基金项目(QN2014308)
【分类号】：TP18;TP3

【相似文献】

相关期刊论文 前10条

1 杨丽;武小年;商可e

本文编号：2543417