A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid |
| |
Authors: | Li-Na Ni Jin-Quan Zhang Chun-Gang Yan Chang-Jun Jiang |
| |
Affiliation: | (1) Department of Computer Science, Tongji University, Shanghai, 200092, P.R. China;(2) College of Information Science & Engineering, Shandong University of Science & Technology, Qingdao, 266510, P.R. China |
| |
Abstract: | 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. |
| |
Keywords: | heuristic algorithm task scheduling load balancing knowledge grid |
本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录! |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载免费的PDF全文 |