云计算负载均衡任务调度问题的元胞自动机模型研究

Research on the Load Balancing Task Scheduling Algorithm Based on Cellular Automata in Cloud Computing

形式化描述了云计算环境下的负载均衡任务调度问题,借助动态规划方法推导了最早完成时间的启发式优先分配策略,进而基于该分配策略求得任务调度的初始解.针对云计算任务调度问题提出一种元胞自动机模型,其中元胞对应于任务调度问题中的任务,元胞的权值对应于任务的总指令长度,元胞的状态对应于任务所分配的虚拟机.引入了元胞对交换的收益值概念,采用贪心原则选择收益值大的元胞对进行交换,不仅优化了任务调度初始解的执行时间,并改善了相应的负载均衡性能.进行了顺序调度算法、Max-Min算法、Min-Min算法、Tabu智能算法和本文算法的对比实验,数据表明本文算法既能优化资源负载均衡性能,又能减少任务执行时间.

The formal description of load balancing task scheduling problem in cloud computing is presented. We make its formal deri- vation based on dynamic programming method and built the heuristic strategy of the earliest finish time （EFT） for task scheduling. The initial solution steps of task scheduling based on the EFT strategy are given. The cellular automata （ CA ） model for the problem are proposed, whose task can be considered as the cell, the instructions length of the task are denoted by the weight of the cell and each cell＇s state represents the virtual machine which the corresponded task belongs to. Furthermore, we propose the gain of cell swap and the load balancing task scheduling algorithm of cloud computing based on CA. The proposed algorithm has better improvement in terms of task completing time and load balance of the initial solution, which adopts the greedy strategy to swap cells. Finally, we car- ry out the comparative experiments among the sequential scheduling algorithm, Min-Min algorithm, Max-Min algorithm, Tabu algo- rithm and the proposed algorithm based on CloudSim simulation platform of cloud computing. The experiment and analysis show the proposed algorithm has better performance in terms of the decreasing the task completing time and the improvement of resource load balancing.