Precedence-Constrained Scheduling with Minimum Time and Communication

摘要

This document considers task systems modeled by directed acyclic graphs in which nodes represent tasks and arcs express precedence constraints, and each task can be computed by a processor in one unit of time. It is known that if there are only two processors or if the graph is a tree, then there are polynormal time algorithms for scheduling the graph in minimum time, but in general the minimum time scheduling problem is NP-complete. The communication cost of a schedule is the number of pairs (p ,x) such that processor p does not compute task x but computes an immediate successor of x ; that is, the result of x must be communicated to p. I consider the problem of finding schedules that minimize finishing time and among those, finding schedules that minimize communication. That the problem with two processors on an arbitrary graph is NP-complete. The problem with arbitrarily many processors on a tree is also NP-complete. The case of two processors on a tree is open in general, but tight bounds for two processors on the indirected complete ternary tree of height k : for minimum time, communication k-log3k + 3 is achievable, and communication k-log3k + 1 is necessary.