https://scholars.lib.ntu.edu.tw/handle/123456789/497306
Title: | Task assignment with precedence relations in distributed computing systems | Authors: | Hsu, C.-C. SHENG-DE WANG Kuo, T.-S. |
Keywords: | Distributed computing system; Heuristic algorithm; Task assignment | Issue Date: | 1990 | Journal Volume: | 13 | Journal Issue: | 2 | Start page/Pages: | 177-187 | Source: | Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an | Abstract: | This 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. |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/497306 https://www.scopus.com/inward/record.uri?eid=2-s2.0-0025402184&doi=10.1080%2f02533839.1990.9677245&partnerID=40&md5=f3a64018e807602db77af9f7452560a9 |
ISSN: | 02533839 | DOI: | 10.1080/02533839.1990.9677245 |
Appears in Collections: | 電機工程學系 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.