An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications
type: Item
instance of: scholarly article
title: An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications
zbMATH Open document ID: 1023.68009
DOI: 10.1016/S0304-3975(02)00328-6
author: Evripidis Bampis
author: Rodolphe Giroudeau
author: Jean-Claude König
published in: Theoretical Computer Science
publication date: 2003-01-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68M20
zbMATH DE Number: 1857143
zbMATH Keywords: scheduling
zbMATH Keywords: hierarchical communications
zbMATH Keywords: approximability
MaRDI profile type: Publication
cites work: On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
cites work: Q4247460
cites work: Q4338954
cites work: Q4198056
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: Three, four, five, six, or the complexity of scheduling with communication delays
cites work: A Heuristic for a Scheduling Problem with Communication Delays
cites work: Q5286651
description: scientific article; zbMATH DE number 1857143