@inproceedings{c40e5fabcae1430ba0130e80677f53d7,
title = "A productive duplication-based scheduling algorithm for heterogeneous computing systems",
abstract = "The scheduling problem has been shown to be NP-complete in general cases, and as a consequence many heuristic algorithms account for a myriad of previously proposed scheduling algorithms. Most of these algorithms are designed for homogeneous computing systems. This paper presents a novel scheduling algorithm for heterogeneous computing systems. The proposed method is known as the Productive Duplication-based Heterogeneous Earliest-Finish-Time (PDHEFT) algorithm. The PDHEFT algorithm is based on a recently proposed list-scheduling heuristic known as the Heterogeneous Earliest-Finish-Time (HEFT) algorithm which is proven to perform well with a low time complexity. However, the major performance gain of the PDHEFT algorithm is achieved through its distinctive duplication policy. The duplication policy is unique in that it takes into account the communication to computation ratio (CCR) of each task and the potential load of processors. The PDHEFT algorithm performs very competitively in terms of both resulting schedules and time complexity. In evaluating the PDHEFT algorithm a comparison is made with another two algorithms that have performed relatively well, namely, the HEFT and LDBS algorithms. It is shown that the proposed algorithm outperforms both of them with a low time complexity.",
author = "Lee, \{Young Choon\} and Zomaya, \{Albert Y.\}",
year = "2005",
month = sep,
doi = "10.1007/11557654\_26",
language = "English",
isbn = "3540290311",
volume = "3726 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer, Springer Nature",
pages = "203--212",
editor = "Yang, \{Laurence T.\} and Rana, \{Omer F.\} and \{Di Martino\}, Beniamino and Jack Dongarra",
booktitle = "High Performance Computing and Communcations",
address = "United States",
note = "1st International Conference on High Performance Computing and Communcations, HPCC - 2005 ; Conference date: 21-09-2005 Through 23-09-2005",
}