An EPTAS for scheduling fork-join graphs with communication delay

DOI10.1016/j.tcs.2021.02.011zbMath1497.68065OpenAlexW3127886951MaRDI QIDQ1998847

Oliver Sinnen, Huijun Wang, Klaus Jansen

Publication date: 9 March 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.02.011

zbMATH Keywords

schedulingapproximationparallel computingEPTASfork-join

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• UET scheduling with unit interprocessor communication delays
• On the complexity of scheduling with large communication delays
• Approximation algorithms for scheduling trees with general communication delays: Special issue on task scheduling problems for parallel and distributed systems
• Three, four, five, six, or the complexity of scheduling with communication delays
• 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
• Scheduling chain-structured tasks to minimize makespan and mean flow time
• A Linear Programming Approach to the Cutting-Stock Problem
• Scheduling Precedence Graphs in Systems with Interprocessor Communication Times
• Complexity of Scheduling under Precedence Constraints
• Worst Case Analysis of Two Scheduling Algorithms
• `` Strong NP-Completeness Results
• Scheduling Opposing Forests
• The Complexity of Scheduling Trees with Communication Delays
• Polynomiality for Bin Packing with a Constant Number of Item Types

This page was built for publication: An EPTAS for scheduling fork-join graphs with communication delay