| A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid |
| |
| 作者姓名： | Li-Na Ni Jin-Quan Zhang Chun-Gang Yan and Chang-Jun Jiang |
| |
| 作者单位： | [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 |
| |
| 基金项目： | 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）. |
| |
| 摘 要： | 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.
|
| 关 键 词： | 启发式算法 任务调度 负载平衡 网格 |
| 收稿时间： | 15 May 2006 |
| 修稿时间： | 2006-05-15 |
A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid |
| |
| Li-Na Ni,Jin-Quan Zhang,Chun-Gang Yan,and Chang-Jun Jiang.A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid[J].Journal of Computer Science and Technology,2006,21(4):559-564. |
| |
| 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 等数据库收录！ |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载全文 |
