# Communication-Aware Scheduling of Precedence-Constrained Tasks on Related Machines

arXiv: https://arxiv.org/abs/2004.14639 · HTML: https://mlsanity.com/paper/2004.14639/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2020.

## Built on by (most cited first, 1 of 1)

- [Moirai: Towards Optimal Placement for Distributed Inference on Heterogeneous Devices](https://mlsanity.com/paper/2312.04025/) (2023)

## Abstract (arXiv)

Scheduling precedence-constrained tasks is a classical problem that has been studied for more than fifty years. However, little progress has been made in the setting where there are communication delays between tasks. Results for the case of identical machines were derived nearly thirty years ago, and yet no results for related machines have followed. In this work, we propose a new scheduler, Generalized Earliest Time First (GETF), and provide the first provable, worst-case approximation guarantees for the goals of minimizing both the makespan and total weighted completion time of tasks with precedence constraints on related machines with machine-dependent communication times.