基于改进NSGA-Ⅱ的云服务PDTs调度算法

基于多目标优化的云计算PDTs调度是一个NP问题,考虑云计算用户的服务质量(Qo S)要求,将处理PDTs的成本和时间要求作为目标,提出一种基于改进NSGA-Ⅱ的云服务PDTs调度算法.采用相似任务序列交叉(STOX)操作加快进化,而采用位移变异避免算法过早收敛,此外,还利用一个拥挤距离自适应算子(SCD)来改善Pareto最优前沿的个体多样性.仿真结果表明该算法在云PDTs调度中保持Pareto最优解的多样性和分布性方面优于NSGA-Ⅱ算法.

An Scheduling Algorithm for Cloud Service PDTs Based on Improved NSGA-II

Partly dependent tasks （PDTs） scheduling with multi-objective optimization in cloud computing is an NP-hard problem. Taking the quality of service （QoS） requirements of users that use cloud computing into account, we set the cost and time requirements of handling the PDTs as the multiple objectives and propose an improved algorithm based on the non-dominated sorting genetic algorithm-II （NSGA-II） to find the Pareto optimal set of the PDTs scheduling. In this paper, the similar task order crossover （STOX） operator is applied to make the evolution more efficient while the shift mutation operator is applied in the process of evolution to avoid the premature convergence. In addition, we propose a new method named self-adapting crowding distance （SCD） operator, which can improve the diversity of individuals in the Pareto-optimal front. The simulation results and analysis show that the proposed algorithm outperforms NSGA-Ⅱ in maintaining the diversity and the distribution of the Pareto-optimal solutions in the cloud PDTs scheduling.