Performance of Coffman-Graham schedules in the presence of unit communication delays

DOI10.1016/S0166-218X(97)00077-2zbMath0894.68012OpenAlexW2061248501MaRDI QIDQ1382255

Claire Hanen, Alix Munier

Publication date: 25 March 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

CG-schedulesCoffman-Graham algorithm

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Parallel Machine Scheduling with Uncertain Communication Delays, Performance of Coffman-Graham schedules in the presence of unit communication delays, An EPTAS for scheduling fork-join graphs with communication delay, An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays, Combinatorial optimization models for production scheduling in automated manufacturing systems

Cites Work

• Unnamed Item
• Multiprocessor scheduling with communication delays
• UET scheduling with unit interprocessor communication delays
• Scheduling UET-UCT series-parallel graphs on two processors
• Performance of Coffman-Graham schedules in the presence of unit communication delays
• Optimal scheduling for two-processor systems
• Worst Case Analysis of Two Scheduling Algorithms
• The Complexity of Scheduling Trees with Communication Delays
• An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays