基于不同分配策略的云计算任务调度性能比较与分析

THE COMPARISON AND ANALYSIS OF TASK SCHEDULING PERFORMANCE IN CLOUD COMPUTING BASED ON DIFFERENT ALLOCATION STRATEGIES

形式化描述了云计算环境下的负载均衡任务调度问题,借助动态规划方法形式化推导了最早完成时间的启发式优先分配策略,给出了基于先易后难优先分配策略、先难后易优先分配策略的启发式云计算任务调度算法。阐述了基于顺序调度策略、先易后难优先分配策略、先难后易优先分配策略等启发式任务调度算法和基于禁忌搜索策略、元胞演化策略等智能任务调度算法。针对不同分配策略的云计算任务调度进行性能比较与分析,提出了完成时间可改进百分比和资源负载平衡因子的调度性能评价指标,实验数据对比充分表明:与启发式调度算法相比,智能调度算法能减少任务执行时间,优化资源负载均衡性能。

The formal description of load balancing task scheduling problem in cloud computing is presented. We make its formal derivation based on dynamic programming method and built the heuristic scheduling strategy of the earliest finish time（EFT） for task scheduling. Furthermore, we propose the priority-to-easy scheduling strategy and priority-to-difficult scheduling strategy for task scheduling in cloud computing based on the EFT strategy. We present the heuristic scheduling algorithm based on the sequential scheduling strategy, the priority-to-easy scheduling strategy and priority-to- difficult scheduling strategy. We also present the intelligence task scheduling algorithm based on the tabu search scheduling strategy and the cellular automata scheduling strategy. Then, we propose two evaluation factors of scheduling performance analysis, which are the improvement percent of the latest time and the load balancing factor. Finally, we carry out the comparative experiments of scheduling performance under the Cloud Sim simulation platform of cloud computing based on five allocation strategies, which are the sequential scheduling strategy, the priority-to-easy scheduling strategy, priority-todifficult scheduling strategy, the tabu search scheduling strategy and the cellular automata scheduling strategy. The experiment and analysis show that intelligence scheduling strategy has better performance in comparison with the heuristic scheduling strategy in terms of the decreasing the task completing time and the improvement of resource load balancing.