Hsu, C.-C.C.-C.HsuSHENG-DE WANGKuo, T.-S.T.-S.Kuo2020-06-042020-06-04199002533839https://scholars.lib.ntu.edu.tw/handle/123456789/497306https://www.scopus.com/inward/record.uri?eid=2-s2.0-0025402184&doi=10.1080%2f02533839.1990.9677245&partnerID=40&md5=f3a64018e807602db77af9f7452560a9This paper addresses the problem of assigning a task with precedence constraints to a distributed computing system. A cost function considering communication overhead and idle time is adopted to measure the performance of the task assignment. The task assignment in this paper determines not only the assignment of modules but also the sequence of messages transmission to balance processor loading and diminish communication overhead. The search for the optimal task assignment with precedence constraints is known to be NP-complete [7] in the strong sense. A heuristic algorithm with polynomial time complexity is proposed in order to effectively solve the task assignment problem. The experimental results reveal that the proposed approach is able to obtain a near-optimal or even the optimal task assignment. © 1990 Taylor & Francis Group, LLC.Distributed computing system; Heuristic algorithm; Task assignmentjournal article10.1080/02533839.1990.96772452-s2.0-0025402184