An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications (Q1853631)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications |
scientific article |
Statements
An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications (English)
0 references
21 January 2003
0 references
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.
0 references
scheduling
0 references
hierarchical communications
0 references
approximability
0 references