An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays

DOI10.1016/S0166-218X(00)00179-7zbMath0967.68021MaRDI QIDQ5929309

Claire Hanen, Alix Munier

Publication date: 4 April 2001

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

zbMATH Keywords

scheduling; makespan

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Related Items

Scheduling \(UET\)-tasks on a star network: complexity and approximation, Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays, Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks, Cyclic multiple-robot scheduling with time-window constraints using a critical path approach, Bicriteria approximation algorithms for scheduling problems with communications delays, Complexity and approximation for precedence constrained scheduling problems with large communication delays, High-multiplicity cyclic job shop scheduling, The complexity of a cyclic scheduling problem with identical machines and precedence constraints, Petri nets for the design and operation of manufacturing systems, Performance of Coffman-Graham schedules in the presence of unit communication delays, Using duplication for scheduling unitary tasks on m processors with unit communication delays, Minimizing flow time in cyclic schedules for identical jobs with acyclic precedence: The bottleneck lower bound., A genetic approach to solving the problem of cyclic job shop scheduling with linear constraints, The basic cyclic scheduling problem with linear precedence constraints

Cites Work

• Unnamed Item
• Multiprocessor scheduling with communication delays
• UET scheduling with unit interprocessor communication delays
• Three, four, five, six, or the complexity of scheduling with communication delays
• A study of the cyclic scheduling problem on parallel processors
• Performance of Coffman-Graham schedules in the presence of unit communication delays
• New complexity results on scheduling with small communication delays
• Optimal scheduling for two-processor systems
• Scheduling Precedence Graphs in Systems with Interprocessor Communication Times
• A Heuristic for a Scheduling Problem with Communication Delays
• Bounds on Multiprocessing Timing Anomalies