An Extension of Edge Zeroing Heuristic for Scheduling Precedence Constrained Task Graphs
Year: 2011
Journal of Information and Computing Science, Vol. 6 (2011), Iss. 2 : pp. 83–96
Abstract
Sarkar's edge zeroing heuristic for scheduling precedence constrained task graphs on parallel systems can be viewed as a priority based algorithm in which the priority is assigned to edges. In this algorithm, the priority is taken as the edge weight. This can also be viewed as a task dependent priority function that is defined for pairs of tasks. We have extended this idea in which the priority is a cluster dependent function of pairs of clusters (of tasks). Using this idea we propose an algorithm of complexity O(|V||E|(|V|+|E|)) and compare it with some well known algorithms.
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/2024-JICS-22681
Journal of Information and Computing Science, Vol. 6 (2011), Iss. 2 : pp. 83–96
Published online: 2011-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 14