IMPROVED LOWER BOUNDS ON TIME AND PROCESSORS FOR SCHEDULING PRECEDENCE GRAPHS ON MULTICOMPUTER SYSTEMS

This paper improves lower bounds on the minimum number of processors a nd minimum time to execute a given directed acyclic task graph with co mmunication delays. The given task graph is partitioned into a number of independent task graphs to arrive at sharper bounds. A drawback of the earlier best method is pointed out and corrected. The time taken t o calculate the bounds is also less in comparison to the corrected met hod. These bounds are useful in comparing heuristic algorithms used fo r scheduling directed acyclic task graphs and as compiler tools in sta tic scheduling-on parallel computers. (C) 1995 Academic Press, Inc.