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

✍ Scribed by Evripidis Bampis; Rodolphe Giroudeau; Jean-Claude König

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 153 KB
• Volume: 290
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00328-6

✦ Synopsis

We study the problem of minimizing the makespan for the precedence multiprocessor constrained scheduling problem with hierarchical communications (Parallel Process. Lett. 10(1) (2000) 133). We propose an 8 5 -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 ÿxed constant) by presenting a (2 -2=(2m + 1))-approximation algorithm.