Scheduling Tasks with Small Communication Delays for Clusters of Processors

    loading  Checking for direct PDF access through Ovid

Abstract

We adopt the hierarchical communications model of (Bampis, Giroudeau, and König, 2000) and we present an approximation algorithm for the precedence constrained multiprocessor scheduling problem in the presence of small hierarchical communication delays (Chrétienne and Colin, 1991). Our algorithm is based on linear programming and rounding and has a performance guarantee of 12(Φ + 1)/({12Φ + 1}) where Φ ≥ 1 is the ratio of the smallest processing time of the tasks and of the maximum intercluster communication delay. This result generalizes the result of (Bampis, Giroudeau, and König, 2000) for the problem with unit execution times and unit intercluster communication delays.

Related Topics

    loading  Loading Related Articles