The Complexity of Scheduling Trees with Communication Delays

DOI10.1006/JAGM.1996.0007MaRDI QIDQ4864438zbMATH OpenOpenAlexFDO

Authors Marinus Veldhorst, Jan Karel Lenstra, Bart Veltman

Publication date 20 February 1996

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1996.0007

zbMATH Keywords

minimum-length schedule

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The complexity of scheduling problems with communication delays for trees
• Publication:4489234
• Scheduling trees with large communication delays on two identical processors
• Three, four, five, six, or the complexity of scheduling with communication delays
• Tree scheduling with communication delays

Cited in

(28)

• Scheduling tree-structured tasks with restricted execution times
• On the complexity of scheduling with large communication delays
• Minimizing the overhead for some tree-scheduling problems
• Approximation algorithms for scheduling trees with general communication delays: Special issue on task scheduling problems for parallel and distributed systems
• Scheduling inverse trees under the communication model of the LogP-machine
• On the minimum number of processors for scheduling problems with communication delays
• Tree scheduling with communication delays
• Three, four, five, six, or the complexity of scheduling with communication delays
• Scheduling complete intrees on two uniform processors with communication delays
• Performance of Coffman-Graham schedules in the presence of unit communication delays
• Scheduling UET-UCT outforests to minimize maximum lateness
• Scheduling unitary task systems with zero--one communication delays for quasi-interval orders
• Unconstrained static scheduling with communication weights
• Scheduling tree-like task systems with non-uniform deadlines subject to unit-length communication delays
• An EPTAS for scheduling fork-join graphs with communication delay
• Scheduling trees with large communication delays on two identical processors
• scientific article; zbMATH DE number 1472179 (Why is no real title available?)
• Scheduling UET Trees with Communication Delays on two Processors
• scientific article; zbMATH DE number 2086776 (Why is no real title available?)
• A linear time algorithm for scheduling outforests with communication delays on three processors
• Parallel Machine Scheduling with Uncertain Communication Delays
• scientific article; zbMATH DE number 1439425 (Why is no real title available?)
• The complexity of scheduling problems with communication delays for trees
• Scheduling 2-dimensional grids with large communication delays
• Performance of critical path type algorithms for scheduling on parallel processors
• Scheduling interval ordered tasks with non-uniform deadlines
• Scheduling jobs with shared additional operations on parallel identical machines
• Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay.

This page was built for publication: The Complexity of Scheduling Trees with Communication Delays

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