Résumé
We study the problem of minimizing the makespan for the precedence multiprocessor constrained scheduling problem with hierarchical communications [1]. We propose an 8/5-approximation algorithm for the UET-UCT (Unit Execution Time Unit Communication Time) hierarchical problem with an unbounded number of biprocessor machines. Moreover, we extend this result in the case where each cluster has m processors (where m is a fixed constant) by presenting an ρ-approximation algorithm where ρ = (2−2/2m+1).