New complexity results on scheduling with small communication delays

DOI10.1016/0166-218X(94)00063-JzbMath0837.68009MaRDI QIDQ1894375

Christophe Picouleau

Publication date: 16 April 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

scheduling problemscommunication delays

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Scheduling in the presence of processor networks : complexity and approximation, Using duplication for scheduling unitary tasks on m processors with unit communication delays, Approximation algorithms for precedence-constrained identical machine scheduling with rejection, Complexity and approximation for precedence constrained scheduling problems with large communication delays, An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays, Scheduling unitary task systems with zero--one communication delays for quasi-interval orders

Cites Work

• Unnamed Item
• UET scheduling with unit interprocessor communication delays
• Task scheduling with interprocessor communication delays
• Tree scheduling with communication delays
• Towards an Architecture-Independent Analysis of Parallel Algorithms
• C.P.M. Scheduling with Small Communication Delays and Task Duplication