A Caltech Library Service

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

Su, Yu and Ren, Xiaoqi and Vardi, Shai and Wierman, Adam (2020) Communication-Aware Scheduling of Precedence-Constrained Tasks on Related Machines. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Ren, Xiaoqi0000-0002-1121-9046
Record Number:CaltechAUTHORS:20200526-151456655
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:103474
Deposited By: Tony Diaz
Deposited On:26 May 2020 22:24
Last Modified:02 Jun 2023 01:05

Repository Staff Only: item control page