Scheduling tasks with small communication delays for clusters of processors

We adopt the hierarchical communications model of Bampis, Giroudeau, and König, and we present an approximation algorithm for the precedence constrained multiprocessor scheduling problem in the presence of small hierarchical delays. 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, for the problem with unit execution times and unit intercluster communication delays.