Approximation algorithms for scheduling to minimize the makespan of communicating processes on selected computer networks

Abstract

The problem addressed in this research is to determine how to efficiently schedule a task system, in which the precedence relation is a tree, on the processors of centralized and distributed-loop computer networks. In particular, the problem is investigated for the case in which there is a single task that must receive messages from all the other tasks before it can be executed. It is desired to find a schedule for which the makespan, the earliest time at which the tasks have completed execution, is minimal. Previous research [41] suggests this problem is NP-Hard in all but the most trivial cases, when the cost of transferring a message is negligible. It is shown in this research that the problem is also NP-Hard when the tasks all execute in unit time, the message costs are arbitrary, a "time-efficient" policy is used for routing message packets, and the network is a centralized, distributed-loop, or topologically distributed store-and-forward computer network. Because of the complexity of the problem, schedules which produce "almost" optimal solutions are regarded as satisfactory. Two approximation algorithms which produce such schedules are investigated for the cases in which the task system is executed on a centralized or distributed-loop computer network. These cases are in fact shown to be equivalent. An f(m)-approximation algorithm produces schedules whose makespan is no more than m times optimal, where m is the number of processors. This bound is the best possible when m = 2. For m [greater than or equal to] 3 examples exist for which this algorithm produces schedules in which the makespan approaches (2 m+1)/3 times optimal. Constant bounds of 2 and 3 times optimal are established for special cases. The algorithm is also investigated in isolated cases when the tasks are first sorted suboptimally. If n is the number of tasks the worst case time complexity of the algorithm may be expressed as 0(n log n + mn) when the tasks are first sorted. When sorting is not used this time complexity becomes 0(mn)...