New complexity results on scheduling with small communication delays

DOI10.1016/0166-218X(94)00063-JMaRDI QIDQ1894375zbMATH OpenFDO

Authors Christophe Picouleau

Publication date 16 April 1996

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

zbMATH Keywords

communication delaysscheduling problems

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)

Recommendations

• Publication:4489234
• Three, four, five, six, or the complexity of scheduling with communication delays
• scientific article; zbMATH DE number 798656
• Scheduling with duplication on \(m\) processors with small communication delays
• The complexity of scheduling problems with communication delays for trees

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• C.P.M. Scheduling with Small Communication Delays and Task Duplication
• Task scheduling with interprocessor communication delays
• Towards an Architecture-Independent Analysis of Parallel Algorithms
• Tree scheduling with communication delays
• UET scheduling with unit interprocessor communication delays

Cited in

(10)

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

This page was built for publication: New complexity results on scheduling with small communication delays

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894375)