基于强化蚁群算法的任务DAG在线网格集群资源调度

On-line Grid Cluster Resource Scheduling Based on Task DAG and Reinforcement Ant Colony Algorithm

摘要:

网格集群资源调度是一个NP难题,而现有的调度方法通常具有任务调度效率低和负载不均衡的问题,由此设计了一种基于强化学习算法和蚁群算法融合的协同依赖型任务调度方法；首先对基于DAG的网格集群协同调度数学模型进行了定义,然后,采用改进的一步TD算法即Q-Learning算法实现集群资源的初始分配,从而得到最优调度方案以及对应的Q值,在此基础上提出一种改进的蚁群算法实现网格集群资源到任务分配的进一步优化,将Q-Learning算法得到的分配方案的Q值用于初始化蚁群路径中的信息素,以避免蚁群的盲目搜索,同时将Q值引入路径概率函数中使得蚂蚁具有启发式的搜索能力,从而获得协同依赖多任务集群调度的最终方案；在Gridsim环境下进行仿真试验,结果表明文中方法能有效地实现网格集群调度,且较其它方法具有任务调度效率高、CPU利用率高和负载均衡的优点,具有较大的优越性。

Abstract:

Grid cluster resource scheduling is a NP problem, the given grid cluster resource scheduling method has the long scheduling time and unbalance system load, a cooperative dependent task scheduling method based on reinforcement learning and parallel ant colony algorithm is proposed. Firstly, the scheduling goal model based on DAG model is defined, then the improved one step TD algorithm such as Q-learning is used to allocate the task resource, and saving the Q value of scheduling schema. Then an improved ant colony algorithm is introduce to realize the allocation of task to the resource node. The Q value obtained from the Q-learning algorithm is used to initialize the pheromone of the route to avoid the search of the ant in ant colony. The Q value is also considered into the probability function to make it has the heuristic ability. The experiment is operated in the Gridsim environment, the result shows the method in this paper can realize the cooperative dependent task cluster scheduling, and compared with the other methods, it has the less task scheduling time and high load balance level, therefore, it is a feasible scheduling method suitable for grid environment with big priority.