An effective scheduling algorithm for homogeneous system

Yipeng Zhou, Guangzhong Sun, Yunlian Jiang, Yinlong Xu

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

1 Citation (Scopus)


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.
Original languageEnglish
Title of host publicationGrid and Cooperative Computing, 2006. GCC 2006. Fifth International Conference
Number of pages7
Publication statusPublished - 2006
Externally publishedYes


  • task scheduling
  • homogeneous
  • heuristic algorithm
  • task duplication

Fingerprint Dive into the research topics of 'An effective scheduling algorithm for homogeneous system'. Together they form a unique fingerprint.

Cite this