一种改进的网格任务调度算法

摘要

任务调度算法是网格计算中研究的热点问题之一.其中,Min-Min调度算法是一个简单、快速、有效经典的任务调度算法,但该算法存在着负载不均衡的缺陷.针对此缺陷,在Min-Min算法的基础上提出了一种新的任务调度算法,该算法定义了一个向量RT={rt1,rt2,…,rti,…rtn},rti代表第i个资源已经分配任务运行时间之和,并根据未被调度的任务数所占的比例,把任务分成两部分调度,不同的部分使用不同的规则进行调度.最后对改进的算法进行了有效性和合理性验证.%Task scheduling algorithm is one of the hottest issues in grid computing.Min-Min scheduling algorithm is a simple,fast and efficient classical task scheduling algorithm,but the algorithm has the defect of load imbalance.Based on the Min-Min algorithm,this paper proposes a new task scheduling algorithm.It defines a vector RT={rt1,rt2… rti… rtn},and rti represents the running time sum of the first i resource that have been allocated to tasks.And according to the proportion of the number of non-scheduled tasks,a task is divided into two parts to schedule,different parts use different rules for scheduling.Finally,the validity and rationality of the improved algorithm are verified.