Hsu, C.-C.C.-C.HsuSHENG-DE WANGKuo, T.-S.T.-S.Kuo2020-06-042020-06-04198902533839https://scholars.lib.ntu.edu.tw/handle/123456789/497305https://www.scopus.com/inward/record.uri?eid=2-s2.0-0024664961&doi=10.1080%2f02533839.1989.9677166&partnerID=40&md5=84af4438ae77281042a195be834c8792In this paper, a cost function considering execution time, communication time and even idle time, is employed to measure the performance of task assignment in a distributed computing system. We successfully develop a new mathematical model to describe this kind of cost function. The task assignment problem is formulated as one of directed-to-undirected graph mapping (DU-mapping) which maps a directed acyclic task graph onto an undirected system graph. The search of optimal DU-mapping is NP-complete and is transformed into a state space search problem. Using an underestimation to A* algorithm, we can obtain an optimal DU-mapping and prune the most nodes in a state space tree. An alternative overestimation is applied to prune more nodes but also obtain a suboptimal DU-mapping. Results of a wide range of experiments reveal that both estimates perform very well due to close evaluation of the real cost. © 1989 Taylor & Francis Group, LLC.Critical sink estimate; Distributed computing system; DU- mappig; Task assignmentComputer Programming--Algorithms; Mathematical Models; Cost Accounting; Scheduling--Computer Applications; Critical Sink Estimate; State Space Search Problem; Task Assignment; Cost Function; Distributed Computing System; Task Turaround Time Computation; Computer Systems, Digitaljournal article10.1080/02533839.1989.96771662-s2.0-0024664961