A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid

作     者：倪丽娜 张金泉 闫春钢 蒋昌俊 

作者机构：Department of Computer Science Tongji University Shanghai 200092 P.R. China College of Information Science & Engineering Shandong University of Science & Technology Qingdao 266510 P.R. China 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2006年第21卷第4期

页      面：559-564页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：This work is supported by the National Natural Science Foundation of China (Grant Nos. 90412013  60473094 and 60534060)  the National Basic Research 973 Program of China (Grant Nos. 2003CB316902 and 2004CB318001-03)  and the Shanghai Science &: Technology Research Plan (Grant Nos. 04XD14016 and 05DZ15004) 

主　　题：heuristic algorithm task scheduling load balancing knowledge grid 

摘      要：Efficient task scheduling is critical to achieving high performance on grid computing environment. The task scheduling on grid is studied as optimization problem in this paper. A heuristic task scheduling algorithm satisfying resources load balancing on grid environment is presented. The algorithm schedules tasks by employing mean load based on task predictive execution time as heuristic information to obtain an initial scheduling strategy. Then an optimal scheduling strategy is achieved by selecting two machines satisfying condition to change their loads via reassigning their tasks under the heuristic of their mean load. Methods of selecting machines and tasks are given in this paper to increase the throughput of the system and reduce the total waiting time. The efficiency of the algorithm is analyzed and the performance of the proposed algorithm is evaluated via extensive simulation experiments. Experimental results show that the heuristic algorithm performs significantly to ensure high load balancing and achieve an optimal scheduling strategy almost all the time. Furthermore, results show that our algorithm is high efficient in terms of time complexity.