An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications (Q1853631)

We study the problem of minimizing the makespan for the precedence multiprocessor constrained scheduling problem with hierarchical communications. We propose an \(\frac 85\)-approximation algorithm for the Unit Communication Time hierarchical problem with arbitrary but integer processing times and an unbounded number of biprocessor machines. We extend this result in the case where each cluster has \(m\) processors (where \(m\) is a fixed constant) by presenting a \((2-2/(2m+1))\)-approximation algorithm.