Complexity and approximation for precedence constrained scheduling problems with large communication delays

DOI10.1016/j.tcs.2008.03.027zbMath1143.90012OpenAlexW2005955982MaRDI QIDQ935152

Rodolphe Giroudeau, Farida Kamila Moulai, Jean-Claude Konig, Jérôme Palaysi

Publication date: 31 July 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.03.027

zbMATH Keywords

approximationnon-approximabilityscheduling with large communication delays

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (4)

Some complexity and approximation results for coupled-tasks scheduling problem according to topology ⋮ Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks ⋮ Scheduling \(UET\)-tasks on a star network: complexity and approximation ⋮ Scheduling 2-dimensional grids with large communication delays

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• UET scheduling with unit interprocessor communication delays
• On the complexity of scheduling with large communication delays
• Approximation algorithms for scheduling trees with general communication delays: Special issue on task scheduling problems for parallel and distributed systems
• Three, four, five, six, or the complexity of scheduling with communication delays
• Using duplication for scheduling unitary tasks on m processors with unit communication delays
• New complexity results on scheduling with small communication delays
• Towards an Architecture-Independent Analysis of Parallel Algorithms
• On a routing problem
• C.P.M. Scheduling with Small Communication Delays and Task Duplication
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A Heuristic for a Scheduling Problem with Communication Delays
• An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays

This page was built for publication: Complexity and approximation for precedence constrained scheduling problems with large communication delays