GEN-HUEY CHENYur, Jyh-ShiarnJyh-ShiarnYur2020-05-042020-05-04199300200255https://www.scopus.com/inward/record.uri?eid=2-s2.0-0027812228&doi=10.1016%2f0020-0255%2893%2990110-8&partnerID=40&md5=25a853eccb4d2c9bc69386cf66264068We consider the problem of finding an optimal assignment of task modules with a precedence relationship in a distributed computing system. The objective of task assignment is to minimize the task turnaround time, i.e., the total time required to finish the execution of a task. This problem is known to be NP-complete for more than three processors. To solve the problem, a well-known state space reduction technique, branch-and-bound-with-underestimates, is applied, and two underestimate functions are defined. Through experiment, their effectiveness is shown by comparison with both Wang and Tsai's algorithm and the A* algorithm. Parameters considered in the experiment include the number of modules, the number of processors, the ratio of average intermodule communication time to average module execution time, and the shapes of task graphs. Statistical data about the number of search nodes, maximal queue length, and execution time are collected for performance evaluation. © 1993.Algorithms; Computer science; Information science; Execution time; Intermodule communication time; Maximal queue length; Optimal assignment; Task graphs; Task modules; Task turnaround time; Distributed computer systemsjournal article10.1016/0020-0255(93)90110-82-s2.0-0027812228https://doi.org/10.1016/0020-0255(93)90110-8