Scheduling \(UET\)-tasks on a star network: complexity and approximation
From MaRDI portal
Publication:538278
DOI10.1007/s10288-010-0127-7zbMath1217.68039MaRDI QIDQ538278
Rodolphe Giroudeau, B. Valery, Jean-Claude Konig
Publication date: 25 May 2011
Published in: 4OR (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10288-010-0127-7
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Erratum to ``Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks, Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks, Scheduling in the presence of processor networks : complexity and approximation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity and approximation for precedence constrained scheduling problems with large communication delays
- UET scheduling with unit interprocessor communication delays
- NP-complete scheduling problems
- On the complexity of scheduling with large communication delays
- Three, four, five, six, or the complexity of scheduling with communication delays
- Towards an Architecture-Independent Analysis of Parallel Algorithms
- On a routing problem
- Scheduling Precedence Graphs in Systems with Interprocessor Communication Times
- Complexity of Scheduling under Precedence Constraints
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- A Heuristic for a Scheduling Problem with Communication Delays
- The Parallel Evaluation of General Arithmetic Expressions
- Bounds for Certain Multiprocessing Anomalies
- An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays
