loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Fifth International Conference on Grid and Cooperative Computing (GCC'06)
An Effective Scheduling Algorithm for Homogeneous System
Hunan, China
October 21-October 23
ISBN: 0-7695-2694-2
Yipeng Zhou, University of Science and Technology of China, China
Guangzhong Sun, University of Science and Technology of China, China
Yunlian Jiang, University of Science and Technology of China, China
Yinlong Xu, University of Science and Technology of China, China
Efficient application scheduling is critical for achieving high performance in homogeneous computing environment. The application scheduling problem has been shown to be NP-complete. However, because of its key importance, this problem has been extensively studied and various algorithms have been proposed in the literatures. In this paper we present a novel algorithm based on list-scheduling and taskduplication on a bounded number of fully connected homogeneous machines. The algorithm is called Fast Duplication based on Earliest Finish Time (FDEFT). In order to provide a robust and unbiased comparison with the related work, a parametric graph generator was designed to generate weighted directed acyclic graphs with various characteristics. The comparison study, based on both randomly generated graphs and the graphs of Gaussian Elimination, shows that our scheduling algorithm significantly outperform on average all other excellent algorithms.
Index Terms:
task scheduling, homogeneous, heuristic algorithm, task duplication
Citation:
Yipeng Zhou, Guangzhong Sun, Yunlian Jiang, Yinlong Xu, "An Effective Scheduling Algorithm for Homogeneous System," gcc, pp.71-77, Fifth International Conference on Grid and Cooperative Computing (GCC'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.