Hsu, Chiun-ChiehChiun-ChiehHsuSHENG-DE WANGKuo, Te-SonTe-SonKuo2009-02-042018-07-062009-02-042018-07-061991-0100207721http://ntur.lib.ntu.edu.tw//handle/246246/120930https://www.scopus.com/inward/record.uri?eid=2-s2.0-84950962014&doi=10.1080%2f00207729008910562&partnerID=40&md5=84a0f4acb7457a8eada2f314f95c034bThe problem is addressed of assigning a task with a precedence constraint to a distributed computing system. Task turnaround time with regard to communication overhead and idle time is adopted to measure the performance of task assignment. The assignment of the module is determined as is the sequence of message transmission to balance the processor load and reduce communication overhead. The search for the optimal task assignment with a precedence constraint is known to be NP-complete (Garey et al. 1979) in the strong sense. A heuristic algorithm with polynomial time complexity is then proposed in order to solve the task-assignment problem effectively. Experimental results show that the proposed approach produces a near-optimal or even optimal task assignment. © 1990 Taylor & Francis Group, LLC.en-USCombinatorial optimization; Heuristic algorithms; Optimization; Polynomial approximation; Communication overheads; Distributed computing systems; Message transmissions; Near-optimal; Polynomial time complexity; Precedence constraints; Processor loads; Task assignment; Distributed computer systemsjournal article10.1080/002077290089105622-s2.0-84950962014