Scheduling \(UET\)-tasks on a star network: complexity and approximation

DOI10.1007/s10288-010-0127-7zbMath1217.68039OpenAlexW2076173115MaRDI QIDQ538278

B. Valery, Rodolphe Giroudeau, 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

zbMATH Keywords

schedulingapproximationnon-approximability

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

Scheduling in the presence of processor networks : complexity and approximation ⋮ 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

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

This page was built for publication: Scheduling \(UET\)-tasks on a star network: complexity and approximation