Scheduling in the presence of processor networks : complexity and approximation

DOI10.1051/ro/2012005zbMath1242.90075OpenAlexW2017534641MaRDI QIDQ2893338

Rodolphe Giroudeau, Vincent Boudet, Jean-Claude Konig, Johanne Cohen

Publication date: 20 June 2012

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/222495

zbMATH Keywords

schedulingnon-approximabilityprocessor network model

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling \(UET\)-tasks on a star network: complexity and approximation
• UET scheduling with unit interprocessor communication delays
• On the complexity of scheduling with large communication delays
• Three, four, five, six, or the complexity of scheduling with communication delays
• New complexity results on scheduling with small communication delays
• On a routing problem
• Scheduling Precedence Graphs in Systems with Interprocessor Communication Times
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Complexity of Task Graph Scheduling with Fixed Communication Capacity
• A Heuristic for a Scheduling Problem with Communication Delays
• Bounds for Certain Multiprocessing Anomalies

This page was built for publication: Scheduling in the presence of processor networks : complexity and approximation